An alert fires at 2 AM. The database is slow. I have one question: who owns this service, which runbook fixes it, and what is the shortest path from the alert to the root cause. The answer is not in my head. It is in four structures. A queue holds the alerts in order. A hash table names the owner in one step. A sorted list finds the runbook in ten steps instead of a thousand. A graph with Dijkstra finds the shortest path to the database. Pick the wrong structure and the same question takes a hundred times longer. That is the whole lesson. Data structures are shelves. Algorithms are the habit of reaching for the right shelf first.
Difficulty: Intermediate · Know this first: Lesson 73, Lesson 153
By the end of this lesson you will have run one alert through four structures and three algorithms, and you will have the code to run them again. First, a demo script that builds a queue, a hash table, a binary search, a sort, a binary search tree, a stack, and Dijkstra over a small dependency graph, and prints the exact output for each one. Second, a hash table built by hand, so you can see a collision happen and see what the load factor means. Third, a Big-O count for your own list size, so you can say before you build whether the search will cost ten steps or ten thousand. You will also know why a sorted list is a habit, not a chore, and why the first question in an interview about this topic is always which structure fits the question.
What you need: Python 3 on your own machine. Standard library only. Nothing in this lesson runs against a live system from this page. The scripts are real and their outputs are shown exactly as they ran. Your list sizes will differ. The shapes will not.
An alert is a question with a clock on it. The database is slow, the severity is 1, and the night is short. I need three facts: who owns the service, which runbook fixes it, and what the shortest path is from the alert to the root cause. Each fact lives on a different shelf, and each shelf has its own habit for reaching it.
The queue is the first shelf. Alerts arrive faster than humans read them, so they wait in line, first in and first out. The hash table is the second shelf. The service name goes in, the owner comes out, in one step. The sorted list is the third shelf. Binary search halves the list until the runbook is in hand, ten steps for a thousand ids. The graph is the fourth shelf. Nodes are services, edges are dependencies, and Dijkstra walks the cheapest edges first to the root cause.
Here is the whole trip in one table. Read it before you run the diagram. Each hop is one structure doing the job it is good at, and the ms column is the teaching example for 1,000 items.
| Hop | Structure or algorithm | What it does | Cost at 1,000 items |
|---|---|---|---|
| Alert queue | Queue | Holds alerts in arrival order | 3 ms |
| Hash lookup | Hash table | Names the owner in one step | 1 ms |
| Tree search | Binary search / binary search tree | Finds the runbook in a sorted list | 3 ms |
| Sort results | Sorting | Orders the candidates worst first | 10 ms |
| Graph walk | Graph | Visits each neighbour once | 5 ms |
| Dijkstra path | Dijkstra | Finds the cheapest path to the root cause | 8 ms |
| Stack unwind | Stack | Unwinds the fix in reverse | 4 ms |
Two things in that table catch people out. First, the hash table is the cheapest hop and the sort is the dearest hop in the good trip, and that is normal. Finding one fact by name is cheap. Putting a thousand facts in order is dear. Second, binary search and the tree both need the list sorted. The sort is not a separate chore. It is the price of the ten-step search. Pay it once, when the list is built, and every search after it is cheap. Pay it never, and every search is a scan.
Write down the numbers 1 to 1,000. Pick a number and find it by halving the list. Count the halves. You will reach it in ten steps or fewer. Now find the same number by reading from the top. Count the reads. That gap, ten against up to a thousand, is Big-O. It is the whole lesson in one exercise, and it costs you two minutes and a pencil.
The diagram above follows one alert through the four shelves. These four paths are the same idea drawn four ways. One alert, answered. One alert, lost in an unsorted list. One Big-O trail, counted step by step. One night at spike, mostly waiting. Run each path. One run takes 7.2 seconds across the path, so you can watch each hop light up in turn.
The return rule: the green dot only starts moving after the orange dot reaches the data hop. A return with no request is a lie. The diagram never draws one. The failure replay at the end of Run all four shows the other side of the rule. Run it and watch the orange dot stop at the tree search and never come back.
One alert walks the design from the story. Queue, hash lookup, tree search, sort, Dijkstra path. The path to the database is found at cost 6, and the answer starts back. The stack unwind and the verdict happen around it, and they are in the main diagram.
Not run yet.
Same alert, same design. The runbook list was never sorted, so binary search cannot run and the search falls back to a scan. The scan times out at the tree search. The sort never runs. The answer never exists. The alert waits, and the database stays slow.
Not run yet.
The same design, counted step by step for 1,000 items. Each hop shows its step count, not its time. A linear scan costs 1,000 steps. Binary search costs 10. A hash lookup costs 1. Sorting costs 9,965 comparisons. Dijkstra costs 4,000 steps. The trail adds up to 14,976 steps. The sort is the big line. The hash is the small one.
Not run yet.
The same alert at spike, with ten thousand alerts at once. Each hop shows its time. The queue wait grows to 21 ms and Dijkstra grows to 220 ms. The rest of the hops barely move. The spike is a graph problem and a queue problem, and the diagram shows it in two hops.
Not run yet.
Every hop charges rent in milliseconds. The bar below is a worked example for one alert through the four shelves, not a measurement from a live system, but the shape is honest. The sort hop is different from the others in one way: it is the dearest hop in the good trip, at 10 ms for 1,000 items, and it grows the fastest when the list grows. At the simulator defaults the total is 36 ms. Move a simulator slider and watch the queue, tree, sort, graph, and Dijkstra hops move with it. Switch the scenario and watch the tree hop or the Dijkstra hop change instead.
The budget bar above shows three fixed stories. This simulator lets you write your own. It answers the trade-off at the heart of this lesson: the list size and the graph density decide the cost, and the sorted index decides whether the search costs ten steps or ten thousand. You set how many items are in the list, how many edges each node has, how many alerts wait in the queue, and whether the sorted index is on. Move a slider and watch the queue hop, the tree hop, the sort hop, the graph hop, the Dijkstra hop, and the budget total change. The numbers are a teaching example, built from the formulas below, not live measurements. The shape is the lesson: the hash stays flat, the search stays logarithmic, and the sort and Dijkstra grow with the list.
How many runbook ids are in the list. One hundred is a small team. Ten thousand is a platform. The search, the sort, and Dijkstra all feel this number.
How many dependencies each service has. Three is a tidy service. Ten is a service that talks to everyone. The graph walk and Dijkstra both feel this number.
How many alerts wait in the queue ahead of this one. One is a quiet night. One hundred is a spike. The queue hop is the only hop that feels this number.
Whether the runbook list is kept sorted. On means binary search runs, ten steps for a thousand ids. Off means the search falls back to a scan of the whole list.
Try this: (1) At the defaults, 1,000 items, 3 edges per node, 10 alerts, sorted index on, the queue hop is 3 ms, the tree hop is 3 ms, the sort hop is 10 ms, the graph hop is 5 ms, and the Dijkstra hop is 8 ms. The budget total is 36 ms. A linear scan would take up to 1,000 steps, and binary search takes 10. (2) Drop to 100 items, 1 edge per node, 1 alert, sorted index on. The queue hop falls to 1.2 ms, the tree hop to 2 ms, the sort hop to 0.7 ms, the graph hop to 3 ms, and the Dijkstra hop to 0.4 ms. The budget total is 14.3 ms. Small lists are cheap in every hop at once. (3) Push to 10,000 items, 10 edges per node, 100 alerts, sorted index off. The queue hop grows to 21 ms, the tree hop to 50 ms, the sort hop to 132.9 ms, the graph hop to 12 ms, and the Dijkstra hop to 220 ms. The budget total is 442.9 ms. From the defaults, the big unsorted spike costs 406.9 ms more per alert, and the Dijkstra hop alone costs 212 ms more. That is the trade, priced.
Formulas, in plain terms. Queue hop = 1 ms plus 0.2 ms per concurrent alert. Tree hop = log2 of the item count times 0.3 ms when the sorted index is on, and the item count times 0.005 ms when it is off. Sort hop = items times log2 of the item count times 0.001 ms. Graph hop = 2 ms plus the edges per node. Dijkstra hop = items times one plus edges per node times 0.002 ms. Hash hop is 1 ms, stack hop is 4 ms, verdict hop is 2 ms, and the request hop is 0 ms. The budget total is the sum of all nine hops. Linear scan steps = the item count. Binary search steps = log2 of the item count, rounded up. All hop values are rounded to one decimal. The numbers are a teaching example, not live measurements. The shape will not change.
Do this now, on your own machine. You will run one script that builds every structure in this lesson, break the search on purpose, and count Big-O by hand for your own list size. The Python parts run on this machine and their outputs are shown exactly as they ran. Nothing here runs against a live system. Your list sizes will differ. The shapes will not.
Save this file as dsa_demo.py. It builds the queue, the hash lookup, the binary search, the sort, the binary search tree, the stack, and Dijkstra, all in one script. Run it and check the output line by line.
"""Data structures and algorithms, one alert at a time.
Standard library only. Every structure below is the one the lesson
walks through: a queue for incoming alerts, a dict for the owner
lookup, a sorted list for binary search, a small binary search tree,
a stack for unwinding the fix, and Dijkstra over a dependency graph.
Run it and check the output against the lesson.
"""
from collections import deque
import bisect
import heapq
# --- 1. Queue: first alert in is the first alert out ---
alerts = deque(["db-slow", "disk-full", "cert-expiring"])
alerts.append("queue-growing")
print("queue:", list(alerts))
print("first out:", alerts.popleft())
print("queue now:", list(alerts))
# --- 2. Hash table: the owner lookup is one step, not a scan ---
owners = {"db-slow": "data-team", "disk-full": "platform-team",
"cert-expiring": "platform-team", "queue-growing": "data-team"}
print("owner of db-slow:", owners["db-slow"])
# --- 3. Binary search vs linear scan, on 1,000 sorted runbook ids ---
runbooks = list(range(0, 10000, 10)) # 1,000 ids, sorted
target = 7420
steps = 0
lo, hi = 0, len(runbooks) - 1
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if runbooks[mid] == target:
break
if runbooks[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print("binary search found", target, "in", steps, "steps")
print("linear scan would take up to", len(runbooks), "steps")
print("bisect agrees:", runbooks[bisect.bisect_left(runbooks, target)])
# --- 4. Sort: worst first, so the worst alert gets the human first ---
sev = [("disk-full", 2), ("db-slow", 1), ("cert-expiring", 3)]
print("sorted by severity:", sorted(sev, key=lambda item: item[1]))
# --- 5. Binary search tree: inorder walk comes out sorted ---
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(root, out):
if root is None:
return
inorder(root.left, out)
out.append(root.key)
inorder(root.right, out)
root = None
for key in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, key)
order = []
inorder(root, order)
print("tree inorder (sorted):", order)
# --- 6. Stack: unwind the fix in reverse, last step first ---
fix = []
for step in ["stop the deploy", "drain the target", "restart the app"]:
fix.append(step)
print("fix steps, unwound:", [fix.pop() for _ in range(len(fix))])
# --- 7. Dijkstra: shortest path from the alert to the root cause ---
graph = {
"alert": [("api", 4), ("queue", 2)],
"api": [("db", 5), ("cache", 1)],
"queue": [("db", 8), ("worker", 3)],
"cache": [("db", 2)],
"worker": [("db", 1)],
"db": [],
}
def dijkstra(graph, start, goal):
dist = {node: float("inf") for node in graph}
prev = {}
dist[start] = 0
heap = [(0, start)]
while heap:
cost, node = heapq.heappop(heap)
if cost > dist[node]:
continue
if node == goal:
break
for nxt, w in graph[node]:
new = cost + w
if new < dist[nxt]:
dist[nxt] = new
prev[nxt] = node
heapq.heappush(heap, (new, nxt))
path = [goal]
while path[-1] != start:
path.append(prev[path[-1]])
return dist[goal], list(reversed(path))
cost, path = dijkstra(graph, "alert", "db")
print("shortest path alert to db:", " -> ".join(path), "cost", cost)
python3 dsa_demo.py
Expected output, exactly as it ran on this machine:
queue: ['db-slow', 'disk-full', 'cert-expiring', 'queue-growing']
first out: db-slow
queue now: ['disk-full', 'cert-expiring', 'queue-growing']
owner of db-slow: data-team
binary search found 7420 in 10 steps
linear scan would take up to 1000 steps
bisect agrees: 7420
sorted by severity: [('db-slow', 1), ('disk-full', 2), ('cert-expiring', 3)]
tree inorder (sorted): [20, 30, 40, 50, 60, 70, 80]
fix steps, unwound: ['restart the app', 'drain the target', 'stop the deploy']
shortest path alert to db: alert -> queue -> worker -> db cost 6
Read the Dijkstra line twice. The path is alert, queue, worker, database, cost 6. The direct edge from alert to API costs 4, and the API to the database costs 5, so that road costs 9. The queue road costs 2 plus 3 plus 1, which is 6. Dijkstra found the cheaper road. That is the whole algorithm in one line.
Change the sorted list in step 3 to an unsorted one. Replace runbooks = list(range(0, 10000, 10)) with a shuffled copy, then run the script again. Binary search will miss the target or report the wrong step count, because it halves a list that is not in order. That is the failure mode from the unsorted scenario, and you just made it happen on your own machine. Change it back when you are done.
Now change one edge cost in the graph. Change the queue to worker edge from 3 to 30 and run it again. The shortest path changes, because Dijkstra reads the edge costs. A stale cost sends the path down the expensive road. That is why the check in the Dijkstra hop says to verify the costs before you trust the path.
Run this on your own machine. Change the 1000 to your own list size and read the counts.
python3 -c "import math; n=1000; print('linear scan steps:', n); print('binary search steps:', math.ceil(math.log2(n))); print('hash lookup steps:', 1); print('sort comparisons:', int(n*math.log2(n))); print('dijkstra steps:', n + 3*n)"
Expected output, exactly as it ran on this machine:
linear scan steps: 1000 binary search steps: 10 hash lookup steps: 1 sort comparisons: 9965 dijkstra steps: 4000
That is the same 9,965 comparisons and the same 4,000 Dijkstra steps from traffic path 3. Two different paths, one number. When two paths agree, the number is worth trusting. Now change n to 10000 and run it again. The scan grows ten times. The binary search grows from 10 to 14. That gap is the lesson.
Point the binary search at the unsorted list from step 1 and explain, in one sentence, why the answer is wrong. Then answer this: your list grows from 1,000 to 10,000 items. Which hop grows ten times, which hop grows from 10 to 14 steps, and which hop does not grow at all. If you can answer that without looking, the lesson is yours.
Delete nothing. The scripts live on your machine, and you can run them again on the next list. Nothing in this lab touched a live system, so there is nothing to destroy.
Three questions. No score is saved anywhere. This is just you against the material.
Picking the right structure is not one skill. It is four levels of the same job, and every team I have worked with sits on one of them. The levels are not about how many structures you can name. They are about whether the question gets answered before the night gets long. Read them in order. Each level fixes the failure that hurt the most at the level below it.
At the basic level, you keep one list and you search it by reading from the top. It works for ten items. It breaks at a thousand, and the break is silent, because the answer still arrives. It just arrives late, and late looks like a slow system when it is really a slow search. The failure that ends this level is the second list. Two lists searched by eye is two piles, and a pile is not a shelf.
Do this: run step 0 of the lab. Read the binary search line and the linear scan line. Ten steps against up to a thousand. Write both numbers down. Then find one runbook id by eye in the demo list and count the reads. Two numbers, one lesson.
At the intermediate level, the question names the structure. Owner by name means a hash table. Runbook by id means a sorted list and binary search. Alerts in order means a queue. Fix steps in reverse means a stack. Cheapest path means a graph and Dijkstra. You stop reaching for the list for every question, because the list is the slowest shelf for most of them. The failure that ends this level is the unsorted list. The search is only as good as the habit that keeps the list sorted.
Do this: run step 1 of the lab. Break the sort and watch binary search miss. Then fix it and run it again. Write down the one habit that keeps the list sorted and who owns it. A habit with no owner is a habit nobody keeps.
At the advanced level, you count the growth before you feel it. You read the Big-O table for your own list size and you say out loud what the search will cost at 10x. A sort per alert is fine at a hundred items and a fire at ten thousand. A Dijkstra walk on a dense graph is fine at a thousand nodes and the dearest hop at ten thousand. The design names the cost up front, and the simulator in this lesson is the tool for it. Move the sliders, read the budget, and write the number down before the spike writes it for you.
Do this: run step 2 of the lab with your own list size. Write down the scan steps, the binary search steps, and the sort comparisons. Then answer this: which hop in your design grows ten times when the list does, and what is the plan for it.
At the master level, the sorted index is a habit the team keeps, not a chore one person remembers. The index builds on a schedule, the graph is cached, the edge costs refresh on a schedule, and the queue is sharded by service when the depth passes the humans. The alert router from the design exercise runs inside its 100 ms budget at the spike, not just on a quiet night, because the expensive work happens before the alert arrives. The team still holds a review every quarter. The review reads the simulator numbers. It does not start from zero.
Do this: write one rule for one structure. The runbook index rebuilds every night at 2 AM. The graph cache refreshes every hour. The queue shards by service when the depth passes 50. Put the rule in the runbook, with the owner next to it. A structure with no rule will drift. A structure with a rule will hold.
Big-O is a promise about growth, not a stopwatch reading. It says what happens when n grows. Here is the table for n = 1,000 and n = 10,000, counted the same way as the lab. Read the columns, not the rows. The scan grows ten times. The binary search grows from 10 to 14. The hash does not grow at all.
| Operation | Big-O | n = 1,000 | n = 10,000 |
|---|---|---|---|
| Linear scan | O(n) | 1,000 steps | 10,000 steps |
| Binary search | O(log n) | 10 steps | 14 steps |
| Hash lookup | O(1) | 1 step | 1 step |
| Sort | O(n log n) | 9,965 comparisons | 132,877 comparisons |
| Dijkstra, 3 edges per node | O((n + e) log n) | 4,000 steps | 40,000 steps |
The sort row is the one to remember. Sorting 10,000 items costs 132,877 comparisons, which is thirteen times the 1,000-item cost, not ten times. That extra growth is the log n factor. It is also why sorting per alert is the most expensive habit in this lesson. Sort once, keep the index, and every search after it is ten steps.
A hash table is buckets and a hash function. The function picks a bucket, and the key lands in it. Two keys in one bucket is a collision, and the lookup walks the chain in that bucket. The load factor is keys divided by buckets. When it passes about 0.7, grow the table and rehash. This script builds an 8-bucket table with 6 keys, so you can see the collision happen.
"""A hash table, built by hand, so the load factor is visible.
A dict hides this. Eight buckets, six keys, one tiny hash function.
Watch bucket 1: two keys land there. That is a collision, and a
collision is the tax a hash table pays. More keys in the same buckets
means longer chains and slower lookups.
"""
def tiny_hash(key, buckets):
return sum(ord(c) for c in key) % buckets
buckets = 8
table = [[] for _ in range(buckets)]
for key in ["db-slow", "disk-full", "cert-expiring", "queue-growing", "api-5xx", "mem-leak"]:
table[tiny_hash(key, buckets)].append(key)
for i, chain in enumerate(table):
print(f"bucket {i}: {chain}")
print("load factor:", 6 / buckets)
print("longest chain:", max(len(chain) for chain in table))
Expected output, exactly as it ran on this machine:
bucket 0: ['db-slow'] bucket 1: ['cert-expiring', 'mem-leak'] bucket 2: [] bucket 3: ['disk-full'] bucket 4: ['api-5xx'] bucket 5: [] bucket 6: [] bucket 7: ['queue-growing'] load factor: 0.75 longest chain: 2
Bucket 1 holds two keys: cert-expiring and mem-leak. That is the collision. The load factor is 0.75, past the 0.7 line, so this table is ready to grow. A real dict grows itself. This one shows you the moment it should.
Breadth-first search is right when every edge costs the same. It finds the fewest hops, and the fewest hops is the cheapest path when the hops are equal. Dijkstra is right when the edges cost different amounts. It walks the cheapest edges first, and the path it returns is the cheapest one, even if it has more hops. Pick BFS for an unweighted graph. Pick Dijkstra for a weighted one. Picking Dijkstra on an unweighted graph still works. It just does extra work for a question BFS answers cheaper.
At 10x the list, the sort and Dijkstra hops dominate the trip, and the fix is to sort once and keep the index, not sort per alert. The graph is cached, and the edge costs refresh on a schedule. At 100x the list, the queue is the bottleneck, and the fix is sharding the queue by service, not a faster sort. A faster sort on a queue that is drowning is a faster way to watch the humans drown. The structures do not change at scale. The place the time goes does, and the simulator shows you where before the spike does.
The runbook list was a shared doc, not a sorted index, and nobody owned keeping it sorted. An alert fired for a service nobody had touched in months. The on-call engineer searched the doc by eye, top to bottom, and the runbook was near the bottom. Forty minutes passed before the right runbook was open. The fix was a three-line change. The search was the incident.
Two things. First, the runbook list became a sorted index with one owner, and the index rebuilds every night. A search that took forty minutes now takes ten steps. Second, the on-call check now includes searching for a runbook nobody has used in a month. A list nobody sorts is a pile, and a pile is not a shelf. The fix was three lines. The habit is the part that stays.
Design an alert router for 10,000 alerts a day. Each alert names a service. The router must name the owner, find the runbook, and find the shortest path from the alert to the root cause, and it must answer in under 100 ms per alert. Name the structure for each job, size the work, and name the trade-offs.
Score it first. Hash table for the owner, O(1), one step. Sorted list plus binary search for the runbook, 14 steps for 10,000 ids, and the index is built once a day, not per alert. Sort the candidates once per alert, n log n on the matches only, not on the whole list. Dijkstra on the dependency graph, and the graph is cached with edge costs refreshed hourly.
Then the sizing. 10,000 alerts a day is about one alert every 9 seconds on average, and the spike is the real number, so size the queue for the spike, not the average. At the simulator defaults the trip costs 36 ms, inside the 100 ms budget, and the big point costs 442.9 ms, outside it, so the spike needs the sorted index kept and the graph cached, not a faster machine. The budget is the test. The simulator is how you run it before the spike does.
Then the failures. The first failure is the unsorted index. One missed rebuild and every search is a scan. The second failure is a stale graph. One changed dependency and Dijkstra walks a dead road. The third failure is the queue. One spike and the humans are behind, and no structure fixes that except sharding the queue by service. Fix the index first, then the graph, then the queue. In that order, because the index is the cheapest fix and the queue is the dearest.
Trade-offs to name. A hash table is fast and forgets order, so keep a separate sorted list for browsing. Dijkstra is exact and slow on a dense graph, so cache the graph and refresh the costs on a schedule. The queue is fair and slow under a spike, so shard it by service when the depth passes the humans. Sorting once a day is cheap and sorting per alert is dear, so the schedule is the trade-off, and it goes in writing.
Saved in this browser, so the Lessons index can show your progress across the course.