Capstone

Data Structures in Practice

Chapter 10 · Capstone: Choosing for Real Problems

Nine chapters have given you a toolbox: lists, tuples, sets, dicts, stacks, queues, linked lists, heaps, trees, graphs and hash tables. Real problems do not arrive labelled with the right one. This final chapter turns the toolbox into a habit: a short decision guide you can run in your head, then three worked case studies that each combine two or three structures from earlier chapters.

What was run, and what was not

Every snippet was run and the output shown is exactly what it printed. The examples use small, fixed inputs and logical timestamps instead of the real clock, so the results are the same on every machine. No timings are quoted.

The Decision Guide

Do not start from the structure. Start from the operations your program performs most often, and ask what each must cost. Four questions settle most choices:

How will items be found? By position, by exact key, by range or prefix, or by "the smallest/largest one"?
Where do items enter and leave? Only at the ends, anywhere, or in priority order?
Does order matter? Insertion order, sorted order, or none at all?
Are there relationships between items? If items point at other items, you have a graph, whatever you call it.

You mostly need to...	Reach for	Why
Keep items in order, read by position, append	`list`	Constant-time index and amortised append (Data Structures in Practice 2)
Look up by exact key	`dict`	Average constant-time lookup (Data Structures in Practice 9)
Ask "have I seen this?" or remove duplicates	`set`	Constant-time membership and set algebra (Data Structures in Practice 3)
Take from one end, add to the other	`deque`	Constant-time at both ends; a list is slow at the front (Data Structures in Practice 4)
Undo, or walk back through history	list used as a stack	Last in, first out with `append` and `pop`
Always take the smallest or largest next	`heapq`	Logarithmic push and pop (Data Structures in Practice 6)
Search sorted data, or find by range or prefix	sorted list with `bisect`	Logarithmic search on sorted data (Data Structures in Practice 1)
Follow links, find routes, order dependencies	dict of neighbours (graph)	Adjacency lists with BFS or DFS (Data Structures in Practice 8)
Fixed records, usable as keys	`tuple`	Immutable and hashable (Data Structures in Practice 3)

Two habits worth keeping

First, start with the simplest structure that is correct (usually a list or a dict) and change it only when you can name the operation that is too slow and how many items it runs on. Ten items never need a heap. Second, combine structures: most real designs are a dict for finding things plus something else for ordering them. The three case studies are all of that kind.

Case Study 1: A Rate Limiter

The problem. Allow each user at most 3 requests in any 10-unit window, and refuse the rest. The operations: find a user's recent requests by key (a dict), add a request at the newest end, and discard requests that have aged out from the oldest end. Items leave from the opposite end to where they enter, which is exactly a queue, so each user gets a deque of timestamps held in a dict.

from collections import deque, defaultdict

class RateLimiter:
    def __init__(self, limit, window):
        self.limit = limit
        self.window = window
        self.hits = defaultdict(deque)       # user -> timestamps, oldest first

    def allow(self, user, now):
        q = self.hits[user]
        while q and q[0] <= now - self.window:
            q.popleft()                      # forget requests outside the window
        if len(q) >= self.limit:
            return False
        q.append(now)
        return True

rl = RateLimiter(limit=3, window=10)
for t in [0, 1, 2, 3, 9, 10, 11, 12, 13]:
    print(t, rl.allow("ann", t))
print(rl.allow("bob", 3), len(rl.hits))
    

True
True
True
False
False
True
True
True
False
True 2
    

Requests at 0, 1 and 2 fill the allowance; 3 and 9 are refused, and the refused ones are not recorded. At time 10 the request from time 0 has aged out (0 <= 10 - 10), freeing one place, then 11 and 12 free the next two. Bob has his own deque, so Ann's traffic never affects him. Each timestamp is added once and removed once, so the cost per request is constant on average, however many requests a user has made in total. A list would work too, but pop(0) shifts every item (Data Structures in Practice 2).

Case Study 2: A Task Scheduler with Cancellation

The problem. Run tasks lowest priority number first, breaking ties by arrival order, and allow a task to be cancelled by name before it runs. A heap gives the next task cheaply, but a heap cannot remove an arbitrary item cheaply. The standard answer is lazy deletion: keep a dict from name to heap entry, and on cancellation just blank the entry's name. The heap discards blanked entries when they surface. A counter in the middle of each entry preserves arrival order for ties and stops Python ever comparing the names.

import heapq, itertools

class Scheduler:
    def __init__(self):
        self.heap = []
        self.live = {}                       # name -> its entry in the heap
        self.counter = itertools.count()     # tie-breaker: arrival order

    def add(self, name, priority):
        entry = [priority, next(self.counter), name]
        self.live[name] = entry
        heapq.heappush(self.heap, entry)

    def cancel(self, name):
        entry = self.live.pop(name, None)
        if entry is None:
            return False
        entry[2] = None                      # leave it in the heap, marked dead
        return True

    def pop(self):
        while self.heap:
            priority, _, name = heapq.heappop(self.heap)
            if name is not None:
                del self.live[name]
                return name
        return None

s = Scheduler()
for name, pr in [("email", 3), ("backup", 5), ("alert", 1), ("report", 3), ("cleanup", 4)]:
    s.add(name, pr)
print(s.cancel("backup"), s.cancel("backup"), s.cancel("nothing"))
out = []
while True:
    n = s.pop()
    if n is None:
        break
    out.append(n)
print(out)
    

True False False
['alert', 'email', 'report', 'cleanup']
    

The first cancellation succeeds; cancelling again, or cancelling a name that never existed, reports False. The run order is by priority, with email ahead of report because it arrived first, and the cancelled backup never appears. The dead entry stayed in the heap until it reached the top and was skipped, so cancellation is constant time and each entry is still pushed and popped once. The price is a little wasted memory until dead entries surface, a trade worth knowing: sometimes the cheap fix is to delay the clean-up rather than do it immediately.

Case Study 3: Shortest Route

The problem. Given a set of two-way roads between named places, find a route with the fewest hops between two of them, or report that none exists. The relationships between places are the point, so this is a graph (Data Structures in Practice 8): a dict mapping each place to the set of its neighbours. Breadth-first search explores in rings of increasing distance, so the first time it reaches the goal it has used the fewest hops. A queue holds the frontier, and a dict doubles as the "already visited" set and the record of where each place was reached from, which lets the route be rebuilt backwards.

from collections import deque, defaultdict

roads = [("A", "B"), ("B", "C"), ("A", "D"), ("D", "E"),
         ("E", "C"), ("C", "F"), ("G", "H")]
graph = defaultdict(set)
for a, b in roads:
    graph[a].add(b)
    graph[b].add(a)                          # two-way roads

def shortest_route(start, goal):
    prev = {start: None}                 # visited places, and how we got there
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = prev[node]
            return path[::-1]
        for nxt in sorted(graph[node]):
            if nxt not in prev:
                prev[nxt] = node
                queue.append(nxt)
    return None

print(shortest_route("A", "F"))
print(shortest_route("A", "A"))
print(shortest_route("A", "H"))
    

['A', 'B', 'C', 'F']
['A']
None
    

There are two ways from A to C: through B (two hops) or through D and E (three). The search finds the shorter one first. Asking for a route to the place you are already at returns just that place, and asking for a route to an unconnected pair of places (G and H are an island) returns None after exploring everything reachable, visiting each place and road once. Without the prev check, the loop A, B, C, E, D, A would run forever; a visited record is what makes graph searches terminate.

One More Pattern: Prefix Search

A short coda showing the guide's "range or prefix" row. A hash table finds only exact keys, so it cannot answer "everything starting with p". Sorted data can, because all matches sit together, and bisect finds both ends of that block in logarithmic time.

import bisect

words = ["pear", "apple", "fig", "kiwi", "plum", "lime", "date", "cherry"]
index = sorted(words)

def starts_with(prefix):
    lo = bisect.bisect_left(index, prefix)
    hi = bisect.bisect_left(index, prefix + chr(0x10FFFF))   # just past every match
    return index[lo:hi]

print(starts_with("p"), starts_with("ch"), starts_with("z"))
    

['pear', 'plum'] ['cherry'] []

The price is that the list must stay sorted: inserting a new word costs a linear shift. A read-heavy index suits this; a constantly changing one may want a different design. Every choice in this chapter is a trade of this kind.

Mistakes the case studies avoid

Using a list as a queue (slow at the front); keeping a graph with no visited record (endless loops); deleting from the middle of a heap (not supported, so mark and skip instead); and comparing entries whose later fields cannot be compared (the counter in the scheduler guarantees ties never reach the name).

What the Course Gave You

You can now count the work a piece of code does, read the cost off the structure rather than guess, and build the structure from first principles when you need to understand it. The rule that runs through all ten chapters is the same: name the operations, find the structure that makes them cheap, and prefer the simplest one that does.

Challenges

Exercise 1

Build an LRUCache with a fixed capacity: get returns the stored value (or a default) and counts as a use, put adds or updates and counts as a use, and when the cache is over capacity the least recently used key is dropped. Both operations must take constant time. Show the key order after a sequence of gets and puts that includes a read, an overflow and an update of an existing key.

📄 View solution

Exercise 2

A leaderboard receives thousands of (score, name) results and only ever needs the best k. Write a TopK class that never holds more than k items, using a heap. Test it on a small hand-checked list including a tie, then on 5,000 random results, confirming the answer equals both a full sort and heapq.nlargest.

📄 View solution

Exercise 3

Write build_order(tasks), where tasks maps each task to the list of tasks that must finish first, returning a valid order to run them in. Use a dict of waiting counts and a queue of ready tasks. Raise ValueError naming the tasks involved if there is a cycle. Test a task chain with a shared step, a single dependency that is not itself listed as a task, an empty input, and a loop.

📄 View solution

Quick Reference

Start from operations: how items are found, where they enter and leave, whether order matters, whether items relate to each other
Simplest first: a list or dict until a named operation on a large input is too slow
Queue-shaped traffic: a deque, one per key in a dict (rate limiter)
Always the next best: a heap; cancel with lazy deletion and use a counter for ties
Relationships: a dict of neighbour sets; BFS for fewest hops; always record visited places
Exact keys: hash table. Ranges and prefixes: sorted list with bisect
Combine structures: a dict to find things plus another structure to order them

Course complete

That is all ten chapters of Data Structures in Practice. Well done: the best next step is to take a program you have already written and ask of each loop which operation dominates and whether a different structure would make it cheaper.