14. DSA in Real Software

How Data Structures Map to Engineering Problems

This chapter connects each data structure to the real systems and components you'll build or encounter as a software engineer.

14.1 Databases

DSA concept	Where it appears
B-Tree / BST	Database indexes (PostgreSQL, MySQL) — fast range queries
Hash map	Hash indexes — exact-match lookups in $O(1)$
Heap	`ORDER BY LIMIT k` queries — finds top-k rows efficiently
Trie	Full-text search prefix matching
Graph	Graph databases (Neo4j), foreign key relationships

14.2 Operating Systems

DSA concept	Where it appears
Stack	Call stack — each function call pushes a frame, return pops it
Queue	CPU scheduling — process queue, I/O request queue
Heap	Memory allocator — free memory blocks managed as a heap
Hash map	Page table — virtual address → physical address translation
Linked list	Free list in memory management

14.3 Networking & Web

DSA concept	Where it appears
Trie	IP routing — longest-prefix matching in routing tables
Graph	Internet topology, BGP routing, CDN path selection
Queue	Message queues (Kafka, RabbitMQ) — async task processing
Hash map	DNS cache, HTTP cache headers, session stores
Bloom filter (probabilistic set)	Checking if a URL has been crawled

14.4 Common SWE Problem Patterns

# --- LRU Cache (Least Recently Used) ---
# Used in: database query caches, browser page caches, CPU caches
# Evicts the least recently accessed item when capacity is full
# Implementation: doubly linked list + hash map → all operations O(1)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()   # maintains insertion order

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict least recently used (front)

lru = LRUCache(3)
lru.put(1, 10); lru.put(2, 20); lru.put(3, 30)
lru.get(1)      # access 1 → moves to end (recently used)
lru.put(4, 40)  # evicts 2 (least recently used)
print(list(lru.cache.keys()))   # [3, 1, 4]

# --- Rate Limiter (sliding window) ---
# Used in: API gateways, CDNs, auth systems
import time
from collections import deque

class RateLimiter:
    """Allow at most max_requests per window_seconds."""
    def __init__(self, max_requests: int, window_seconds: float):
        self.max_requests = max_requests
        self.window = window_seconds
        self.timestamps: deque[float] = deque()

    def allow(self) -> bool:
        now = time.time()
        # Remove timestamps outside the window
        while self.timestamps and self.timestamps[0] < now - self.window:
            self.timestamps.popleft()
        if len(self.timestamps) < self.max_requests:
            self.timestamps.append(now)
            return True
        return False   # too many requests

# --- Task Scheduler with priority ---
# Used in: job queues, OS schedulers, workflow engines
import heapq
from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class Job:
    priority: int
    task: Any = field(compare=False)

class Scheduler:
    def __init__(self):
        self._heap: list[Job] = []

    def submit(self, priority: int, task) -> None:
        heapq.heappush(self._heap, Job(priority, task))

    def run_next(self):
        if self._heap:
            job = heapq.heappop(self._heap)
            print(f"Running [priority={job.priority}]: {job.task}")
            return job.task

sched = Scheduler()
sched.submit(3, "send_newsletter")
sched.submit(1, "process_payment")    # highest priority (lowest number)
sched.submit(2, "generate_report")
sched.run_next()   # process_payment
sched.run_next()   # generate_report
sched.run_next()   # send_newsletter

# --- Dependency resolver (topological sort) ---
# Used in: package managers (pip, npm), build tools (make, gradle)
def install_order(packages: dict[str, list[str]]) -> list[str]:
    """
    packages = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}
    means A depends on B and C, B depends on D, etc.
    Returns install order starting from dependencies.
    """
    from collections import deque
    in_degree = {pkg: 0 for pkg in packages}
    for pkg, deps in packages.items():
        for dep in deps:
            in_degree[pkg] += 1   # this package depends on 'dep'

    # Recalculate: count how many packages depend on each
    in_degree = {pkg: 0 for pkg in packages}
    reverse_deps: dict[str, list[str]] = {pkg: [] for pkg in packages}
    for pkg, deps in packages.items():
        for dep in deps:
            reverse_deps[dep].append(pkg)
            in_degree[pkg] += 1

    queue = deque(pkg for pkg in packages if in_degree[pkg] == 0)
    order = []
    while queue:
        pkg = queue.popleft()
        order.append(pkg)
        for dependent in reverse_deps[pkg]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                queue.append(dependent)
    return order if len(order) == len(packages) else []   # [] = circular dep

pkgs = {"app": ["db", "cache"], "db": ["driver"], "cache": [], "driver": []}
print(install_order(pkgs))   # ['cache', 'driver', 'db', 'app'] (one valid order)

14.5 Choosing the Right Data Structure

Use this guide when designing a component:

Need fast lookup by key?
  → dict (hash map)   O(1) average

Need unique items / fast membership test?
  → set               O(1) average

Need ordered items with fast access by position?
  → list              O(1) index, O(n) search

Need frequent insert/delete at both ends?
  → deque             O(1) both ends

Need always process the highest/lowest priority item next?
  → heapq (heap)      O(log n)

Need range queries (sum/min/max of a[l..r])?
  → prefix sum (static) or segment tree (dynamic)

Need prefix-based string search / autocomplete?
  → Trie              O(L) per operation

Need to model relationships/connections?
  → dict of lists (adjacency list)

Need to sort a group once and then query?
  → sorted list + bisect   O(n log n) build, O(log n) query

Need to track connected components dynamically?
  → Union-Find        O(α(n)) ≈ O(1) per operation

14.6 Complexity Quick Reference

Structure	Access	Search	Insert	Delete	Space
`list`	$O(1)$	$O(n)$	$O(1)$ †	$O(n)$	$O(n)$
Sorted `list`	$O(1)$	$O(\log n)$	$O(n)$	$O(n)$	$O(n)$
`dict` / `set`	$O(1)$	$O(1)$	$O(1)$ †	$O(1)$	$O(n)$
`deque`	$O(n)$	$O(n)$	$O(1)$ ends	$O(1)$ ends	$O(n)$
Heap	$O(1)$ min	—	$O(\log n)$	$O(\log n)$	$O(n)$
BST (balanced)	—	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Trie	—	$O(L)$	$O(L)$	$O(L)$	$O(n \cdot L)$

† Amortised

End of Python DSA for Software Engineers — August 2026

← Previous
13. Tries Done →
All tracks