Shelf · DSA Patterns · Chapter 6

Chapter 6: Tree & graph patterns

Trees and graphs are where "loop over the data" stops working, because the data points at itself. This chapter gives you six reusable templates with the state each one must carry, the input each one silently fails on, and the cost statement to say aloud.

Difficulty
Priority
dsa-06-01Card 1 of 6

DFS templates and traversal state

MediumP2 · Very likelyKnow cold8 min
dfsrecursionvisitedstack

Why you care

Dependency trees, org charts, folder walks and lineage graphs all arrive as "node plus its neighbours". The job bug is state: a missing visited set that loops for ever on one cyclic row, or a recursive walk that dies on the one deep chain in production. Interviewers ask for DFS because every mistake is visible. This card owns the template later cards reuse.

Explain like I'm 5

You explore a cave with a ball of thread and a piece of chalk. At each junction you take the first unmarked tunnel until a dead end, then follow the thread back to the last junction with an unexplored tunnel. Chalk means "been here". The thread is the stack. Forget the chalk and a loop in the cave walks you in circles.

Core concept

The rule: mark a node when you enter it, finish its neighbours, then mark it done.

  • Entry work (record preorder, mark in progress) happens before the neighbour loop; exit work (record postorder, mark done) after it.
  • A general graph needs a visited set. A rooted tree with downward edges does not. An undirected tree stored with edges both ways needs a parent skip instead.
  • Disconnected input needs an outer loop over every node.
  • Recursion costs one Python frame per level. The default recursion limit is 1000 (check sys.getrecursionlimit()). An explicit stack of (node, iterator) pairs removes it.
  • Adjacency list cost: O(V + E) time; the visited set is O(V) and the stack up to O(V). On a tree, recursion uses O(height).

Use DFS for entry/exit order, cycle detection and "everything below this node". Use BFS (BFS, level-order and grid traversal) for fewest edges; a DFS path is valid, not shortest.

Minimal example Visited makes a cycle and an island safe

PythonRecursive DFS over a graph with a cycle and a disconnected noderuns
graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"], "e": []}
order, seen = [], set()

def dfs(n):
    seen.add(n); order.append(n)
    for m in graph[n]:
        if m not in seen:
            dfs(m)

for n in graph:
    if n not in seen:
        dfs(n)
print(order, len(seen))
Output
['a', 'b', 'd', 'c', 'e'] 5

In production Iterative DFS with entry, exit and back edges

Pinterest-style category data has missing parents and the odd loop. This version uses three states (absent, 1 = in progress, 2 = done) and an explicit stack.

PythonIterative DFS over every component, no recursion limitruns
import sys

def dfs_all(graph):
    color, pre, post, back = {}, [], [], []
    for root in graph:
        if root in color:
            continue
        color[root] = 1; pre.append(root)
        stack = [(root, iter(graph.get(root, ())))]
        while stack:
            node, it = stack[-1]
            for nxt in it:
                state = color.get(nxt)
                if state is None:
                    color[nxt] = 1; pre.append(nxt)
                    stack.append((nxt, iter(graph.get(nxt, ()))))
                    break
                if state == 1:
                    back.append((node, nxt))   # edge into an ancestor: a cycle
            else:
                color[node] = 2; post.append(node); stack.pop()
    return pre, post, back

def recursive_visit(graph, n, seen):
    seen.add(n)
    for m in graph.get(n, ()):
        if m not in seen:
            recursive_visit(graph, m, seen)

g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"], "e": ["e"], "f": ["ghost"]}
print(dfs_all(g))
print(dfs_all({}))
print(dfs_all({"x": []}))
chain = {i: [i + 1] for i in range(5000)}
pre, post, back = dfs_all(chain)
print(len(pre), len(post), back, sys.getrecursionlimit())
try:
    recursive_visit(chain, 0, set())
except RecursionError:
    print("RecursionError on a 5000-deep chain")
Output
(['a', 'b', 'd', 'c', 'e', 'f', 'ghost'], ['d', 'b', 'c', 'a', 'e', 'ghost', 'f'], [('d', 'a'), ('e', 'e')])
([], [], [])
(['x'], ['x'], [])
5001 5001 [] 1000
RecursionError on a 5000-deep chain

See it happen One walk, one back edge, one new component

abcde (new component)
  1. Enter a: it is marked in progress before any neighbour is looked at.
  2. Follow a to b, then b to d; all three are now in progress and sit on the stack.
  3. d looks at a, finds it still in progress, and records a back edge: that is the cycle.
  4. d and then b exit and are marked done; the stack unwinds to a.
  5. a takes its second edge to c; c finds d already done, so it does not walk into d again.
  6. The outer loop reaches e, which nothing points to, and starts a second walk there.
Notice: the cycle is an edge into a node still in progress, not an edge into any seen node.
Scenario A

In your world

The situation

Your Jenkins job rebuilds a lineage table from a parent_id column in Postgres. Each row is walked upward with a recursive helper.

What actually breaks

One bad load writes a row whose parent is its own grandchild. The helper never ends; Jenkins times out after 60 minutes with 0 rows written. On another night a chain is 1,400 deep and the job dies with RecursionError, though every 6-level test passed.

What you'd do on Monday

Walk with an explicit stack and treat a back edge as bad data to report.

PythonReport cycles instead of walking them (needs the Postgres extract)
parents = {row["id"]: row["parent_id"] for row in extract}
children = {}
for child, parent in parents.items():
    children.setdefault(parent, []).append(child)
pre, post, cycles = dfs_all(children)      # template from the production block
if cycles:
    raise SystemExit(f"{len(cycles)} cyclic edges, first: {cycles[0]}")
Scenario B

Imagine you work at Pinterest

2M-node taxonomy

The numbers

Illustrative: 2,000,000 nodes, 5,000,000 edges, one chain 50,000 deep. A set of 2M ints measured 67 MB for the table alone (sys.getsizeof), before the int objects; a bytearray(2_000_000) of state flags is 2 MB. Time is V + E = 7M steps, seconds in Python.

What the Scenario-A answer does here

The Scenario A fix still works: explicit stack, same output. It gets heavy because each worker holds a set per walk.

What flips at this scale

Number the nodes 0..V-1 once and keep state in a bytearray (0 new, 1 in progress, 2 done): 67 MB becomes 2 MB, over 30x less, and components can be split across workers. The state representation changes, not the algorithm.

The trade-off you'd defend

I would defend dense integer ids and a flag array over a set of string ids, trading a one-off id-mapping pass for a visited structure over 30x smaller.

Illustrative figures to show the arithmetic; not Pinterest-published. The 67 MB is a local sys.getsizeof of a 2M-int set on CPython 3.11.

Gotchas

Cycle makes the walk run for ever

Symptom

The job never finishes; with a counter it hits the cap you set.

Cause

No visited set, or marking after the neighbour loop, on a graph with a cycle.

Fix

Mark on entry. The demo stops itself after 100 calls.

Pythonruns
g = {"a": ["b"], "b": ["a"]}
calls = 0

def walk(n):
    global calls
    calls += 1
    if calls > 100:
        raise RuntimeError("cap hit: cycle with no visited set")
    for m in g[n]:
        walk(m)

try:
    walk("a")
except RuntimeError as e:
    print(calls, e)
Output
101 cap hit: cycle with no visited set

Undirected tree reports a cycle that is not there

Symptom

A clean tree is rejected as cyclic.

Cause

Each edge is stored twice, so every child sees its parent as in progress.

Fix

Pass the parent down and ignore exactly that neighbour.

Pythonruns
tree = {"r": ["x", "y"], "x": ["r"], "y": ["r"]}

def has_cycle(n, parent, state):
    state[n] = 1
    for m in tree[n]:
        if m == parent:
            continue
        if state.get(m) == 1 or (m not in state and has_cycle(m, n, state)):
            return True
    return False

def naive(n, state):
    state[n] = 1
    return any(state.get(m) == 1 or (m not in state and naive(m, state)) for m in tree[n])

print("no parent check:", naive("r", {}), "| parent check:", has_cycle("r", None, {}))
Output
no parent check: True | parent check: False

Recursive walk dies on one deep chain

Symptom

RecursionError on production data only, shown in the production block.

Cause

One frame per level against a default limit of 1000.

Fix

Explicit stack. Raising sys.setrecursionlimit can crash the interpreter instead.

Tricky questions

DFS finds a path from a to b. Is it the shortest?
Most people say

Yes, it reached b, so it is a valid shortest path.

Actually

It is a path, not the one with fewest edges: with a-b and a-c-b, DFS may take the long way. Use BFS for hop counts.

Scenario question

You're handed a Postgres table of 3 million (id, parent_id) rows and asked for every node's depth and subtree size, rejecting bad data.

Model answer

I'd build a children map and run an iterative DFS with three states, taking depth at entry and subtree size at exit; a back edge is bad data. It is O(V + E) with O(V) state. The trade-off is RAM: when the map no longer fits in memory I would use a recursive CTE.

Interview corner

CommonWrite DFS for a graph. What state does it need?
“I'd keep a visited set, mark on entry, recurse over unvisited neighbours and loop over all nodes for disconnected parts. It is O(V + E) with O(V) extra space.”
TrickHow do you detect a cycle in a directed graph with DFS?
“I'd use three states. An edge into a node still in progress is a back edge, so a cycle. An edge to a finished node is fine, which is why a plain seen set gives false positives.”
Experience checkHave you hit a recursion limit in real code?
“Yes, a lineage walk on a deep parent chain raised RecursionError. I moved it to an explicit stack and added a 5,000-deep test, because small fixtures never find it.”

Memory hook

A cave, chalk and a thread: chalk on entry, thread back on exit.

If you remember only one thing:

Mark on entry, finish on exit, loop over every node, and use an explicit stack when depth is unbounded.

Self-check

  1. Which edge shows a cycle in a directed DFS?

    An edge to a node that is still in progress.

  2. Why does a disconnected graph need an outer loop?

    One walk only reaches its own component.

  3. Time and extra space of DFS on an adjacency list?

    O(V + E) time; O(V) for visited and up to O(V) for the stack.

Prove it

Time dfs_all on chains of 5,000, 20,000 and 100,000 nodes. Paste the three timings and the line where the recursive version raises RecursionError at 5,000.

dsa-06-02Card 2 of 6

BFS, level-order and grid traversal

MediumP2 · Very likelyKnow cold8 min
bfsqueuelevel-ordergridmulti-source

Why you care

Questions phrased "fewest steps", "nearest" or "level by level" are queue walks: nearest driver, fewest service hops, a route across a warehouse floor. The bug is quiet: discovery marked at the wrong moment inflates counts, and a missing bounds check wraps around in Python and returns plausible numbers. Interviewers ask for grid BFS because bounds, obstacles, visited ownership and level counts all show in 25 lines.

Explain like I'm 5

Drop a stone in a pond. The ripple reaches everything one step away, then two steps away, in rings. You walk the ring with a clipboard and tick each name the instant you see it, so nobody lands on two rings. The ring is the queue.

Core concept

The rule: enqueue the start marked as discovered; repeatedly take from the front and discover its undiscovered neighbours, marking each when you enqueue it.

  • Use collections.deque; popleft() is O(1), while list.pop(0) shifts every element.
  • Discovery on enqueue puts each node in the queue once. Marking on dequeue lets several parents queue it.
  • Set dist[v] = dist[u] + 1 at discovery; the first discovery is the fewest-edge distance.
  • Level snapshot: read n = len(queue) at the top of each round and process exactly n items. That n is the frontier size.
  • Multi-source: enqueue every source at distance 0 first; one pass gives distance to the nearest source.
  • Grid: check bounds before indexing, skip blocked cells, and let the distance table be the visited set.
  • Cost: O(V + E); a four-neighbour rectangular grid is O(rows × columns).

Use BFS for fewest hops in an unweighted graph. Weighted edges need Dijkstra (Dijkstra with explicit heap assumptions).

Minimal example Distance is set when a node is first discovered

PythonDiamond graph: d is reached by two parents but queued onceruns
from collections import deque
g = {"a": ["b", "c"], "b": ["d"], "c": ["d", "e"], "d": [], "e": []}
dist, q, sizes = {"a": 0}, deque(["a"]), []
while q:
    sizes.append(len(q))
    for _ in range(sizes[-1]):
        u = q.popleft()
        for v in g[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
print(dist, sizes)
Output
{'a': 0, 'b': 1, 'c': 1, 'd': 2, 'e': 2} [1, 2, 2]

In production Multi-source BFS on a city grid

An Ola-style dispatch map: D is a driver, # a blocked block, . open road. Every cell gets the steps to its nearest driver from one pass.

PythonNearest-driver steps, frontier sizes, and the awkward inputsruns
from collections import deque

def nearest_driver_steps(grid):
    rows = len(grid)                            # rows must be equal length
    cols = len(grid[0]) if rows else 0
    dist = [[-1] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "D":
                dist[r][c] = 0                  # discovered on enqueue
                q.append((r, c))
    sizes = []
    while q:
        sizes.append(len(q))                    # one whole level
        for _ in range(sizes[-1]):
            r, c = q.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] != "#" and dist[nr][nc] < 0):
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))
    return dist, sizes

def show(grid, dist):
    for r, row in enumerate(grid):
        print("".join("#" if ch == "#" else ("x" if dist[r][c] < 0 else str(dist[r][c]))
                      for c, ch in enumerate(row)))

grid = ["D..#.", ".#.#.", "...#D", ".#.#.", "..#.."]
dist, sizes = nearest_driver_steps(grid)
show(grid, dist)
print(sizes)
print(nearest_driver_steps([]))
print(nearest_driver_steps(["..."]))
print(nearest_driver_steps(["D"]))
Output
012#2
1#3#1
234#0
3#5#1
45#32
[2, 4, 4, 4, 2, 2]
([], [])
([[-1, -1, -1]], [])
([[0]], [1])

See it happen Frontier by frontier, one discovery per node

queuedddist of a, b, c, d, e011--
  1. Start: a enters the queue and is marked distance 0 in the same step.
  2. Level 1 has size 1: a is taken out, b and c are marked 1 as they are queued.
  3. Level 2 has size 2: b is taken and d is marked 2 on enqueue.
  4. c is taken: it sees d already marked and skips it, then marks e as 2.
  5. Level 3 has size 2: d and e find nothing new and the queue empties.
  6. The wrong version marks on dequeue: b and c both queue d before either is taken, so d sits in the queue twice.
Notice: the duplicate d in the last frame is exactly what marking on enqueue prevents.
Scenario A

In your world

The situation

Your Jenkins job assigns each warehouse pick-up point to its nearest depot using a floor grid in a JSON file, running one search per point.

What actually breaks

With 4,000 pick-up points on a 400 × 300 grid (120,000 cells), each search can touch every cell. At about 2.5 µs per cell (0.1 s per 40,000 cells, measured), that is 0.3 s per search and 4,000 × 0.3 s = 1,200 s, 20 minutes, against a 5-minute window. A teammate's version also skips the bounds check; row -1 is valid in Python, so edge cells read the bottom row.

What you'd do on Monday

Start one search from all depots at once and read every point from the table.

PythonSame pass, all depots (needs the JSON floor map)
dist, _ = nearest_driver_steps(grid)              # template from the production block
assignments = {p: dist[p[0]][p[1]] for p in pickup_points}
Scenario B

Imagine you work at Ola

40,000-cell city grid

The numbers

Illustrative: 20 km × 20 km at 100 m cells is 200 × 200 = 40,000 cells. One full BFS measured about 0.1 s in CPython. Per-rider searches for 10,000 open requests: 10,000 × 0.1 s = 1,000 s ≈ 17 minutes. One multi-source pass from the drivers: 0.1 s.

What the Scenario-A answer does here

The Scenario A fix is still correct. What breaks is refresh rate: drivers move every few seconds and 10,000 per-rider searches cannot fit.

What flips at this scale

Seed the queue with every driver once and answer every rider by table lookup. Cost no longer depends on rider count: 0.1 s for 10,000 riders, a 10,000x cut. At 2,000 × 2,000 (4M cells, 100x more) a pass is about 10 s, so partition by zone.

The trade-off you'd defend

I would defend one multi-source pass per refresh over per-rider searches, trading the early exit each search could take for a flat cost shared by all requests.

Illustrative; not Ola-published. The 0.1 s per 40,000 cells is a local measurement on CPython 3.11.

Gotchas

Marking after dequeue duplicates nodes and frontier counts

Symptom

Frontier sizes larger than the node count allows; a node expanded twice.

Cause

A node queued by two parents before either is dequeued, with the mark placed at dequeue time.

Fix

Set the mark when you append.

Pythonruns
from collections import deque
g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}

def levels(mark_on_enqueue):
    seen, q, sizes, expanded = {"a"}, deque(["a"]), [], 0
    while q:
        sizes.append(len(q))
        for _ in range(sizes[-1]):
            u = q.popleft(); expanded += 1
            if not mark_on_enqueue:
                seen.add(u)
            for v in g[u]:
                if v not in seen:
                    if mark_on_enqueue:
                        seen.add(v)
                    q.append(v)
    return sizes, expanded

print(levels(True), levels(False))
Output
([1, 2, 1], 4) ([1, 2, 2], 5)

Negative grid index reads the far edge

Symptom

Top-row cells get a neighbour above that does not exist; distances look plausible and are wrong.

Cause

grid[-1] is the last row, so a missing 0 <= nr check never raises.

Fix

Bound both ends before indexing.

Pythonruns
grid = ["..", ".#"]
r, c = 0, 0
print(grid[r - 1][c], "<- reads the bottom row for 'above (0,0)'")
print(0 <= r - 1 < len(grid))
Output
. <- reads the bottom row for 'above (0,0)'
False

BFS on weighted edges returns the wrong route

Symptom

The route has fewest hops but a larger total cost.

Cause

BFS counts edges and never looks at weights.

Fix

Use Dijkstra when costs differ.

Pythonruns
w = {("a", "t"): 10, ("a", "b"): 1, ("b", "t"): 1}
print("BFS picks a->t, hops 1, cost", w[("a", "t")])
print("cheaper a->b->t, hops 2, cost", w[("a", "b")] + w[("b", "t")])
Output
BFS picks a->t, hops 1, cost 10
cheaper a->b->t, hops 2, cost 2

Tricky questions

In level-order BFS, why read len(queue) before the inner loop?
Most people say

It does not matter; while queue handles levels automatically.

Actually

while queue cannot tell where a level ends. Reading the length first freezes the frontier size; read inside the loop it grows as children are appended.

Scenario question

You're handed a 500 × 500 maze file with walls, several exits and a start, and asked for the steps to the nearest exit, or "no exit".

Model answer

I'd run BFS from the start with the distance table as visited, returning when I first pop an exit, else "no exit". It is O(rows × columns), 250,000 cells, well under a second. The trade-off: with many starts I would search from the exits instead.

Interview corner

CommonWhy does BFS give the shortest path in an unweighted graph?
“I'd say the queue releases nodes in non-decreasing distance order, so the first discovery of a node uses the fewest edges. DFS has no such ordering.”
TrickWhere do you mark visited, and does it matter?
“On enqueue. If I mark on dequeue, a node can be queued several times, the frontier counts inflate and work repeats, though final distances can still look right.”
Experience checkHave you replaced many searches with one?
“I changed a per-item search into one pass seeded with every source, then looked up each item. Cost went from items times cells to cells, and I checked identical answers on a sample.”

Memory hook

A pond ripple: tick each name the instant you see it, and each ring is a queue snapshot.

If you remember only one thing:

Mark on enqueue, read the queue length once per level, and check both bounds.

Self-check

  1. Where is the distance set?

    When the node is first discovered, at enqueue.

  2. How do you start a multi-source BFS?

    Enqueue every source at distance 0 before the loop.

  3. Cost of BFS on an R × C grid with four neighbours?

    O(R × C).

Prove it

Build a 200 × 200 open grid with 5 drivers. Time one multi-source pass against 5 single-source passes, and paste both timings plus the assertion that the multi-source table equals the elementwise minimum of the five.

dsa-06-03Card 3 of 6

Backtracking with reversible state

MediumP3 · Role-dependentKnow cold8 min
backtrackingrecursionpruningundo

Why you care

Some jobs need every valid combination: which discount stacks are legal, which config sets pass a rule. The failures are state leaking between branches (a result full of the same empty list) and pruning that silently drops valid answers. Interviewers ask to see whether you can state the undo step, the base case and the real cost.

Explain like I'm 5

You pick a dinner menu one dish at a time. After trying a plate you put it back on the shelf before the next, or you carry every earlier plate. Over budget already? Stop and put it back.

Core concept

The rule: choose, apply, recurse, undo. State changed on the way in is restored on the way out.

  • Keep one shared path and shared counters; change them in place, revert after the call.
  • Base condition: decide what counts as an answer and record a copy, list(path). Storing path stores one list that ends up empty.
  • Pruning is sound only if no discarded branch could hold an answer. Breaking when a total passes a cap needs totals that never fall back (non-negative values) and sorted candidates.
  • Path-local state (groups used on this branch) is undone. Graph-traversal visited (DFS templates and traversal state) is not; route enumeration needs the first, reachability the second.
  • Cost: the search-tree size, up to branching^depth, plus the copy of each answer. n independent choices can give 2^n answers; just writing them out costs that.

Use it to enumerate or search a constrained space small enough to list. For one best value use a state table instead (Define a sufficient DP state).

Minimal example Apply, copy, recurse, undo

PythonCombinations of weights with total at most 5runs
weights = [1, 2, 3, 4]
out, path = [], []

def go(start, total):
    for i in range(start, len(weights)):
        if total + weights[i] > 5:
            break
        path.append(weights[i])        # apply
        out.append(list(path))         # copy, not the live list
        go(i + 1, total + weights[i])
        path.pop()                     # undo

go(0, 0)
print(out)
print(path)
Output
[[1], [1, 2], [1, 3], [1, 4], [2], [2, 3], [3], [4]]
[]

In production Legal discount stacks with a cap

Shopify-style rules: any number of codes, at most one per group, total percentage at most the cap. The result is checked against brute force.

PythonBacktracking with group exclusion, a sound prune and a brute-force checkruns
from itertools import combinations

def stacks(coupons, cap):
    if any(pct < 0 for _, _, pct in coupons):
        raise ValueError("pruning needs non-negative percentages")
    items = sorted(coupons, key=lambda c: c[2])      # ascending, so break is sound
    out, path, groups = [], [], set()

    def go(start, total):
        for i in range(start, len(items)):
            code, group, pct = items[i]
            if group in groups:
                continue
            if total + pct > cap:
                break
            path.append(code); groups.add(group)     # apply
            out.append(list(path))
            go(i + 1, total + pct)
            groups.discard(group); path.pop()        # undo

    go(0, 0)
    return out

def brute(coupons, cap):
    out = []
    for k in range(1, len(coupons) + 1):
        for combo in combinations(coupons, k):
            if len({g for _, g, _ in combo}) == k and sum(p for *_, p in combo) <= cap:
                out.append(sorted(c for c, _, _ in combo))
    return sorted(out)

cs = [("SAVE5", "seasonal", 5), ("VIP10", "loyalty", 10), ("SHIP", "freight", 0),
      ("FLASH15", "seasonal", 15), ("TWIN10", "loyalty", 10), ("BIG20", "bulk", 20)]
got = stacks(cs, 25)
print(len(got), sorted(sorted(s) for s in got) == brute(cs, 25))
print(stacks([], 25), stacks(cs, 0))
print(len(stacks([("A", "g", 5)] * 3, 100)))
try:
    stacks([("X", "g", -5)], 10)
except ValueError as e:
    print(f"ValueError: {e}")
Output
21 True
[] [['SHIP']]
3
ValueError: pruning needs non-negative percentages

See it happen Two sibling branches, apply then undo

pathgroups in userecorded answerspathpathpath
  1. Start: path and groups are empty and nothing is recorded.
  2. Apply SAVE5: it goes on the path, its group is marked in use, and a copy is recorded.
  3. Recurse and apply VIP10: path and groups both grow, and a second copy is recorded.
  4. Undo VIP10: path and groups shrink back to exactly what they were before that apply.
  5. Undo SAVE5 and start the sibling branch: VIP10 begins from a clean state, with no seasonal group left over.
  6. The bug: recording the live path instead of a copy, so every recorded answer points at the same emptied list.
Notice: undo restores state exactly, so the second branch never sees the first branch's marks.
Scenario A

In your world

The situation

Your Jenkins job generates test-data variants for a settlement rule engine: each of 14 optional flags on or off, filtered by a validity rule.

What actually breaks

Variant 1,200 passes while variant 1,201 shows the same flags. The generator appends its working list instead of a copy, so every stored variant is the final, empty list: 16,383 variants (2^14 - 1) all identical. The suite is green because identical variants all pass.

What you'd do on Monday

Copy at the base case, undo after each call, and compare the count with a brute-force count on 6 flags.

PythonCopy and undo (needs the rule engine to consume variants)
def variants(flags, valid):
    out, path = [], []
    def go(i):
        if i == len(flags):
            if valid(path):
                out.append(list(path))       # copy
            return
        for on in (False, True):
            path.append((flags[i], on)); go(i + 1); path.pop()
    go(0)
    return out
Scenario B

Imagine you work at Shopify

30 stackable codes

The numbers

Illustrative: 30 codes, each in its own group, so any subset is legal. Stacks = 2^30 - 1 ≈ 1.07 billion. Measured here: 1.0 µs per stack at 16 codes and 2.0 µs at 20, so use 2 µs: 1.07B × 2 µs ≈ 2,150 s ≈ 36 minutes. A stored 15-item list is about 180 bytes, so 1.07B × 180 B ≈ 193 GB.

What the Scenario-A answer does here

The Scenario A fix works for 14 flags (16,383 stacks, milliseconds). At 30 codes the answer itself is 1.07B items, so no pruning saves you from holding it.

What flips at this scale

Stop materialising. Checkout wants the best stack or the first that meets a goal. Make the walk a generator and stop at the first hit, or use a table over the cap (30 codes × 100 percent points = 3,000 states). Enumeration is for small spaces and tests.

The trade-off you'd defend

I would defend a lazy generator for audit tools and a table-based best stack for checkout, trading some code in the checkout path for latency that does not grow with 2^n.

Illustrative; not Shopify-published. The per-stack times and 180 B are local measurements on CPython 3.11.

Gotchas

The result is a list of empty lists

Symptom

[[], [], [], ...] where combinations were expected.

Cause

out.append(path) stores the one live list, later emptied.

Fix

out.append(list(path)) or path[:].

Pythonruns
out, path = [], []
def go(i):
    if i == 3:
        out.append(path); return
    path.append(i); go(i + 1); path.pop()
    go(i + 1)
go(0)
print(out)
Output
[[], [], [], [], [], [], [], []]

A global visited set finds one path instead of all

Symptom

Counting routes returns 1 where 2 exist.

Cause

Traversal visited is never undone; route enumeration needs path-local state that is.

Fix

Add on the way in, remove on the way out.

Pythonruns
g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}

def count(n, goal, seen, undo):
    if n == goal:
        return 1
    total = 0
    for m in g[n]:
        if m not in seen:
            seen.add(m)
            total += count(m, goal, seen, undo)
            if undo:
                seen.discard(m)
    return total

print(count("a", "d", {"a"}, True), count("a", "d", {"a"}, False))
Output
2 1

Pruning with negative values drops valid answers

Symptom

The fast version returns fewer results than brute force: 0 against 1 below.

Cause

break assumes totals only rise, so a prefix over the cap is hopeless. With negatives a later item can bring it back under.

Fix

Validate input, or use continue and drop the prune.

Pythonruns
vals = [-5, -4, -3]        # sorted ascending, cap -10
cap = -10
def fast(start, total, path, out):
    for i in range(start, len(vals)):
        if total + vals[i] > cap:
            break              # unsound here: -5 alone is over the cap
        out.append(path + [vals[i]])
        fast(i + 1, total + vals[i], path + [vals[i]], out)
out = []
fast(0, 0, [], out)
brute = sum(1 for m in range(1, 8) if sum(v for i, v in enumerate(vals) if m >> i & 1) <= cap)
print(len(out), "found; brute force finds", brute)
Output
0 found; brute force finds 1

Tricky questions

Backtracking loops over n items, so is it O(n)?
Most people say

Yes, one loop of n items at each level.

Actually

The loop sits inside a recursion up to n deep, so work is about the node count of the search tree, up to branching^depth, plus the copy cost of each recorded answer.

Scenario question

You're handed 18 optional pricing rules and asked to list every combination without two conflicting rules.

Model answer

I'd backtrack with a conflict set undone after each call and a copy at the base case. Worst case is 2^18 = 262,144 combinations, fine to print. I'd first ask how many rules there will be, because at 40 the output is the problem. The trade-off: listing is simple and testable, but I'd switch to a generator if the count could outgrow memory.

Interview corner

CommonWhat are the steps of a backtracking template?
“I'd say choose, apply, recurse, undo, with a base case that records a copy. The undo must exactly reverse the apply so sibling branches start clean.”
TrickWhy does my result list contain the same list many times?
“I'd check whether I appended the live path. It is one object mutated across branches, so I copy at the base case.”
Experience checkWhen did enumeration get too big?
“I had a test generator over 14 flags that was fine at 16,383 cases. When we added 10 more flags it became 16 million, so I switched the large set to sampling.”

Memory hook

Put the plate back before the next try, and photograph the plate, not the plate itself.

If you remember only one thing:

Copy the answer, undo the move, and prune only when a discarded branch cannot hold an answer.

Self-check

  1. What does undo have to restore?

    Every piece of shared state changed by apply, in reverse order.

  2. Why list(path) and not path?

    path is one live list that is mutated later.

  3. What bounds the time?

    Search-tree size (branching^depth) plus the copy cost of recorded answers.

Prove it

Run stacks on 10, 15 and 20 singleton-group codes with cap 10,000. Paste the counts (expected 2^n - 1) and timings, and extrapolate the time for n = 30 from the measured rate per stack.

dsa-06-04Card 4 of 6

Topological sort and dependency cycles

MediumP3 · Role-dependentKnow cold8 min
topological-sortkahndependenciesdag

Why you care

Every orchestrator, build tool and migration runner asks one question: in what order can these run so nothing starts before what it needs? A cycle there is a deadlock, not a slowdown. In ETL it is the Airflow or Jenkins job graph. Interviewers ask because the edge cases (disconnected jobs, duplicate dependencies, cycles) separate someone who has run it from someone who memorised it.

Explain like I'm 5

You are getting dressed. Socks before shoes, shirt before jacket, but shirt and socks ignore each other. Each item has a tag counting what it still waits for. Anything with a zero tag can go on now, and dressing it lowers the tag on whatever waited for it. If clothes remain on the hanger and no tag is zero, two items wait for each other.

Core concept

The rule: an order exists only if the directed graph has no cycle, and usually many orders are valid.

  • Kahn: count incoming dependencies per node, queue the zeros, pop one, append it, decrement its dependents and queue those reaching zero.
  • Cycle check: if the order is shorter than the node count, the missing nodes are in or behind a cycle.
  • DFS alternative: walk along "needs" edges and append a node on exit; a back edge means a cycle. Along "unlocks" edges, reverse the finishing order.
  • Duplicate edges: count and decrement the same collection, or de-duplicate first. Mixing the two leaves the node waiting for ever.
  • Disconnected jobs have count 0; a self-loop is a cycle.
  • No unique answer: tests should assert every edge goes forward, not one fixed order.
  • Cost: O(V + E) for both.

Use it for "what is a valid order" and "is there a cycle". It does not apply to undirected graphs.

Minimal example DFS finishing order, and a cycle caught

PythonDependencies first, then a loop in the needsruns
needs = {"deploy": ["test", "lint"], "test": ["build"], "build": [], "lint": []}
order, state = [], {}
def visit(j):
    if state.get(j) == 1: raise ValueError(f"cycle through {j}")
    if state.get(j) == 2: return
    state[j] = 1
    for d in needs[j]: visit(d)
    state[j] = 2; order.append(j)
for j in needs: visit(j)
print(order)
needs["build"] = ["deploy"]; order, state = [], {}
try: visit("deploy")
except ValueError as e: print(f"ValueError: {e}")
Output
['build', 'test', 'lint', 'deploy']
ValueError: cycle through deploy

In production Kahn with a verifier and a cycle report

GitHub Actions-style needs: a job waits for the jobs it lists. Duplicates collapse, an unknown job is an error, and leftovers are reported.

PythonKahn's algorithm with the cases that biteruns
from collections import deque
class CycleError(Exception):
    pass
def run_order(needs):
    deps = {job: set(ds) for job, ds in needs.items()}      # duplicates collapse
    for job, ds in deps.items():
        for d in ds:
            if d not in deps:
                raise KeyError(f"{job} needs unknown job {d!r}")
    waiting = {job: len(ds) for job, ds in deps.items()}
    children = {job: [] for job in deps}
    for job, ds in deps.items():
        for d in ds:
            children[d].append(job)
    ready = deque(job for job, n in waiting.items() if n == 0)
    order = []
    while ready:
        job = ready.popleft(); order.append(job)
        for ch in children[job]:
            waiting[ch] -= 1
            if waiting[ch] == 0:
                ready.append(ch)
    if len(order) < len(deps):
        raise CycleError(sorted(set(deps) - set(order)))
    return order
def edges_go_forward(needs, order):
    pos = {j: i for i, j in enumerate(order)}
    return all(pos[d] < pos[j] for j, ds in needs.items() for d in ds)
cases = {
    "plain": {"deploy": ["test", "lint"], "test": ["build"], "build": [], "lint": [], "docs": []},
    "dup": {"b": ["a", "a"], "a": []},
    "empty": {},
    "self": {"x": ["x"], "y": []},
    "cycle": {"p": ["q"], "q": ["p"], "r": ["q"], "s": []},
    "unknown": {"m": ["ghost"]},
}
for name, needs in cases.items():
    try:
        order = run_order(needs)
        print(name, order, edges_go_forward(needs, order))
    except (CycleError, KeyError) as e:
        print(name, type(e).__name__, e)
Output
plain ['build', 'lint', 'docs', 'test', 'deploy'] True
dup ['a', 'b'] True
empty [] True
self CycleError ['x']
cycle CycleError ['p', 'q', 'r']
unknown KeyError "m needs unknown job 'ghost'"

See it happen Waiting counts drive the order

lintbuildtestdeploy (done)
  1. Count what each job waits for: lint 0, build 0, test 1, deploy 2. The two zeros are ready.
  2. Run lint first: deploy's count drops from 2 to 1.
  3. Run build next: test drops to 0 and joins the ready queue.
  4. Run test: deploy drops to 0 and becomes ready.
  5. Run deploy. All four jobs are in the order, so processed equals total and there is no cycle.
Notice: the order is complete only because every count reached zero; a cycle leaves counts stuck above zero.
Scenario A

In your world

The situation

Your Jenkins pipeline has 40 stages defined as a Python dict of depends_on lists, and runs them in dict order, which happened to be right when the file was written.

What actually breaks

Someone inserts a stage mid-dict. load_orders now runs before extract_orders, finds an empty staging table and loads 0 rows with a green build. Later a copy-paste makes two stages depend on each other and Jenkins waits 90 minutes on a stage that can never start.

What you'd do on Monday

Compute the order, fail fast on a cycle, and test that every edge goes forward rather than one fixed order.

PythonGate the pipeline (needs the real stage config)
order = run_order({s["name"]: s.get("depends_on", []) for s in stages})   # production block
for name in order:
    run_stage(name)
Scenario B

Imagine you work at GitHub

2M workflow runs per day

The numbers

Illustrative: 2,000,000 runs a day, each averaging 40 jobs and 80 dependency edges. One sort is V + E = 120 steps; 2M × 120 = 240M steps a day, and 240M ÷ 86,400 ≈ 2,800 steps per second. Trivial for one process.

What the Scenario-A answer does here

The Scenario A fix works, and the arithmetic says compute is not the problem. What breaks: one static order runs parallelisable jobs serially, and a cycle found at run start wastes the slot.

What flips at this scale

Keep the waiting counts live. Store a count per job in a shared store; when a job finishes, decrement its dependents and start those reaching 0 in parallel. Validate the graph when the workflow is saved, so cycles are rejected before any run exists. This is Kahn's counters held as durable state.

The trade-off you'd defend

I would defend live indegree counters in a shared store over a precomputed linear order, trading one extra write per dependency edge on completion for parallelism and crash recovery.

Illustrative; not GitHub-published. The per-day and per-job averages are assumed to show the arithmetic.

Gotchas

Duplicate dependency leaves a job waiting for ever

Symptom

Processed count is below total on an acyclic graph, reported as a cycle.

Cause

The waiting count came from the raw list (2) but the dependents list holds the edge once, so it is decremented once.

Fix

Count and decrement the same collection, or de-duplicate first.

Pythonruns
needs = {"b": ["a", "a"], "a": []}
waiting = {j: len(ds) for j, ds in needs.items()}                 # raw: b waits for 2
children = {"a": ["b"], "b": []}                                  # built from a set: one edge
for ch in children["a"]:
    waiting[ch] -= 1
print(waiting, "-> b is stuck at", waiting["b"], "although there is no cycle")
Output
{'b': 1, 'a': 0} -> b is stuck at 1 although there is no cycle

Reported "cycle members" include innocent jobs

Symptom

The error lists jobs that are not in any loop: r in the production output.

Cause

The leftover set holds the cycle and everything waiting behind it.

Fix

Say "blocked by a cycle"; run DFS on the leftovers if exact members matter.

Test pins one exact order

Symptom

A green test goes red after a harmless refactor.

Cause

Several valid orders exist, and dict or set iteration changes the choice.

Fix

Assert that every dependency precedes its dependent.

Pythonruns
needs = {"c": ["a", "b"], "a": [], "b": []}
for order in (["a", "b", "c"], ["b", "a", "c"]):
    print(order, all(order.index(d) < order.index(j) for j, ds in needs.items() for d in ds))
Output
['a', 'b', 'c'] True
['b', 'a', 'c'] True

Tricky questions

The sort returns fewer nodes than exist. Is it a bug?
Most people say

Yes, some nodes were skipped by mistake.

Actually

On a directed graph it means a cycle, or a duplicate-edge accounting bug. Compare processed to total and treat the difference as the signal.

Scenario question

You're handed 300 SQL scripts with a -- depends_on: comment each and asked to run them safely with maximum parallelism.

Model answer

I'd parse the edges, reject unknown names, then run Kahn in waves: everything at count 0 runs together, then I decrement and take the next wave. A leftover set means a cycle and the run aborts before starting. The trade-off: waves wait for the slowest script; per-job counters use workers better at the price of a real scheduler.

Interview corner

CommonHow do you detect a cycle with Kahn's algorithm?
“I'd compare the number of nodes I emitted with the total. If fewer, some nodes never reached zero, so a cycle blocks them. It costs nothing extra.”
TrickIs the topological order unique?
“No, whenever two nodes are unordered by the edges they can swap, so I test that edges go forward and never compare to one fixed list.”
Experience checkWhen did dependency order bite you?
“A stage list in a dict ran a load before its extract after someone inserted a stage. I replaced the implicit order with a computed one and a test that checks every edge.”

Memory hook

Clothes with tags: zero means go, and a hanger that never empties means two items wait for each other.

If you remember only one thing:

Emitted count against total is the cycle test; assert edges go forward, never one fixed order.

Self-check

  1. How does Kahn's algorithm signal a cycle?

    Fewer nodes emitted than exist.

  2. Why can two correct implementations return different orders?

    Independent nodes can appear in either order.

  3. What is the cost?

    O(V + E).

Prove it

Build a random 1,000-node DAG (edges only from lower to higher index), shuffle the dict, and assert edges_go_forward on Kahn and DFS output. Add one back edge and paste the CycleError.

dsa-06-05Card 5 of 6

Union-find for changing connectivity

MediumP3 · Role-dependentTalk about it8 min
union-finddisjoint-setcomponentsconnectivity

Why you care

"Are these two things in the same group?" while new links keep arriving is a connectivity question, and a graph walk per question is the slow way. Customer de-duplication and merging records that share an email or phone are this. The failure is cost (a walk per query) or semantics (using it where direction or deletion matters). Interviewers ask to see whether you know what it cannot answer.

Explain like I'm 5

Everyone at a party wears a badge naming a group leader. When two groups merge, the smaller group's leader gets a badge pointing at the bigger group's leader. To ask "same group?", follow badges to the top person and compare. When you walk a long chain, cross out the middle badges and write the leader's name directly.

Core concept

The rule: keep a parent pointer per element; the root names the group; merge by hanging one root under the other.

  • find(x) follows parents to the root; path compression (or halving) re-points visited nodes higher.
  • union(a, b) finds both roots; if equal it does nothing and reports it; else it attaches the smaller tree under the larger (union by size) and decrements the component count.
  • Both optimisations together give O(alpha(V)) amortized per operation (inverse Ackermann, below 5 for any real input). Say "amortized".
  • Without union by size, a chain of unions can build a tree V deep, and one find costs O(V).
  • It answers "are a and b connected in the undirected graph so far?" and "how many groups?". It cannot answer directed reachability, paths, or anything after deleting an edge.

Use it for streaming edges plus connectivity or component counts. Use BFS/DFS (DFS templates and traversal state) for the path, direction or a one-off answer on a fixed graph.

Minimal example Same group after a chain of merges

PythonRoots decide membershipruns
parent = {x: x for x in "abcde"}

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

for u, v in [("a", "b"), ("b", "c"), ("d", "e")]:
    parent[find(u)] = find(v)
print(find("a") == find("c"), find("a") == find("d"), len({find(x) for x in parent}))
Output
True False 2

In production Groups with size, halving and a component count

Meta-style friend groups: edges arrive one at a time, and after each we want the number of groups.

PythonUnion-find with union by size and path halvingruns
class Groups:
    def __init__(self):
        self.parent, self.size, self.count = {}, {}, 0

    def add(self, x):
        if x not in self.parent:
            self.parent[x], self.size[x] = x, 1
            self.count += 1

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]     # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        self.add(a); self.add(b)
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

    def connected(self, a, b):
        if a not in self.parent or b not in self.parent:
            return a == b
        return self.find(a) == self.find(b)

g = Groups()
stream = [("u1", "u2"), ("u3", "u4"), ("u2", "u3"), ("u1", "u4"), ("u5", "u5"), ("u6", "u7")]
for a, b in stream:
    merged = g.union(a, b)
    print(f"{a}-{b} merged={merged} groups={g.count}")
print(g.connected("u1", "u4"), g.connected("u1", "u6"), g.connected("zz", "zz"), g.connected("zz", "u1"))
print(g.count, len(g.parent), g.size[g.find("u1")])
Output
u1-u2 merged=True groups=1
u3-u4 merged=True groups=2
u2-u3 merged=True groups=1
u1-u4 merged=False groups=1
u5-u5 merged=False groups=2
u6-u7 merged=True groups=3
True False True False
3 7 4
Scenario A

In your world

The situation

Your Jenkins job de-duplicates customers: two rows are the same person if they share an email or a phone. It loops over all pairs of rows in Python.

What actually breaks

With 60,000 rows that is 60,000 × 59,999 / 2 ≈ 1.8 billion pair checks. At 1M checks per second that is 1,800 s, 30 minutes, for a step that took about 2 minutes at 15,000 rows (112M pairs; 4x the rows is 16x the time). The job times out and stale data is served.

What you'd do on Monday

Union rows through a key, one union per row per key, then read the groups.

PythonGroup rows that share an email or phone (needs the customers extract)
g = Groups()                                  # class from the production block
first_seen = {}
for row in rows:
    for key in (("e", row["email"]), ("p", row["phone"])):
        if key[1]:
            g.union(row["id"], first_seen.setdefault(key, row["id"]))
Scenario B

Imagine you work at Meta

2B friend-edge events a day

The numbers

Illustrative: 100M accounts and 2,000,000,000 edge events a day, so 2B ÷ 86,400 ≈ 23,000 per second. Measured here on 1M nodes: about 2.6 µs per edge with a list or array('i') (same speed) and about 7 µs with a dict. At 2.6 µs, 2B × 2.6 µs ≈ 5,200 s ≈ 87 minutes for a daily pass on one core. array('i') buys memory, not speed: two arrays of 100M 4-byte ints are 2 × 400 MB = 800 MB.

What the Scenario-A answer does here

The Scenario A fix still answers "same group?" on the stream. What breaks is unfriending: union-find cannot delete an edge, so a group that should split stays merged. The dict-based Groups is also about 3x slower and far too heavy at 100M accounts.

What flips at this scale

Treat the structure as a derived snapshot. Keep array('i') parents and sizes over dense ids, rebuild nightly from the surviving edges, and answer live queries from the last snapshot plus a small overlay of today's insertions. Deletions appear at the next rebuild.

The trade-off you'd defend

I would defend a nightly rebuild plus an insertion overlay over a dynamic-connectivity structure, trading up to a day of staleness for removed edges for a simple 800 MB structure with near-constant updates.

Illustrative; not Meta-published. The timings are local measurements (500,000 random unions on 1M nodes, CPython 3.11).

Gotchas

Chain of unions makes find linear

Symptom

Lookups slow as merges continue; the deepest node takes about n steps (999 below).

Cause

Attaching without comparing sizes builds a path.

Fix

Union by size or rank, plus compression.

Pythonruns
def max_depth(by_size, n=1000):
    p, sz = list(range(n)), [1] * n
    def root(x):
        while p[x] != x:
            x = p[x]
        return x
    for i in range(n - 1):
        a, b = root(i), root(i + 1)
        if by_size and sz[a] < sz[b]:
            a, b = b, a
        if by_size:
            p[b] = a; sz[a] += sz[b]
        else:
            p[a] = b
    def depth(x):
        d = 0
        while p[x] != x:
            x = p[x]; d += 1
        return d
    return max(depth(x) for x in range(n))

print(max_depth(False), max_depth(True))
Output
999 1

It says connected, but you cannot get there

Symptom

find("b") == find("a") is True although the only edge is a to b.

Cause

Union-find is undirected; direction is lost on union.

Fix

Use DFS/BFS for reachability.

Pythonruns
edges = [("a", "b")]                      # a points to b only
parent = {"a": "a", "b": "b"}
for u, v in edges:
    parent[u] = v
find = lambda x: x if parent[x] == x else find(parent[x])
print("uf says connected:", find("b") == find("a"), "| b reaches a:", any(u == "b" for u, v in edges))
Output
uf says connected: True | b reaches a: False

Deleting an edge leaves the group merged

Symptom

Two people stay in one group after the only link between them is removed.

Cause

A union only merges; nothing records which edge caused it.

Fix

Rebuild from the surviving edges.

Pythonruns
edges = [("a", "b"), ("b", "c")]

def groups(es, nodes="abc"):
    p = {x: x for x in nodes}
    f = lambda x: x if p[x] == x else f(p[x])
    for u, v in es:
        p[f(u)] = f(v)
    return len({f(x) for x in p})

print("before:", groups(edges), "| after removing b-c, rebuilt:", groups(edges[:1]))
Output
before: 1 | after removing b-c, rebuilt: 2

Tricky questions

Does path compression alone give O(alpha(V))?
Most people say

Yes, compression is the clever part and size is optional.

Actually

The stated bound needs both union by size or rank and path compression. Compression alone only gives an O(log n) amortized bound.

Scenario question

You're handed a feed of 10 million (record_a, record_b) pairs meaning "same entity" and asked how many distinct entities exist.

Model answer

I'd run union-find with a dict, union by size and path halving, and read the final component count: 10M × a few µs, tens of seconds. The trade-off: if pairs can be retracted, union-find cannot undo, so I'd keep the raw pairs and rebuild.

Interview corner

CommonWhat are the two optimisations, and what do they buy?
“I'd say union by size keeps trees shallow and path compression flattens them on find. Together the amortized cost per operation is O(alpha(V)), effectively constant.”
TrickCan union-find answer directed reachability?
“No. Union merges groups with no direction, so it answers undirected connectivity only. For reachability I'd run BFS or DFS.”
Experience checkWhere would you use it in ETL?
“I'd use it to group rows that share any of several keys, like email or phone, before picking a golden record. It replaces a quadratic pair loop.”

Memory hook

Badges that point to a leader; flatten the chain when you walk it.

If you remember only one thing:

Union-find is undirected, insertion-only connectivity, and the near-constant bound needs both union by size and path compression.

Self-check

  1. What does find return?

    The root of the element's tree, which names its group.

  2. What happens on a union of two elements already in one group?

    Nothing; the count is unchanged and union returns False.

  3. Name two things it cannot do.

    Directed reachability or paths, and deleting edges.

Prove it

Run 100,000 chained unions with and without union by size, using an iterative find. Record the maximum find depth and total time for each, and paste both lines.

dsa-06-06Card 6 of 6

Dijkstra with explicit heap assumptions

HardP3 · Role-dependentTalk about it8 min
dijkstraheapshortest-pathweighted

Why you care

When edges carry costs (fees, latencies) the cheapest route is not the fewest hops, and Dijkstra finds it in near-linear time. The risk is a silent wrong answer: one negative cost, or a stale heap entry processed twice, still returns numbers. Interviewers probe the preconditions and the heap model behind the bound.

Explain like I'm 5

You pay for a trip across several bus lines. Keep a notebook of the cheapest known fare to each stop, and always go to the unfinished stop with the smallest fare. If a bus from it gives a cheaper fare onward, cross out the old number and write the new one. Bin old slips.

Core concept

The rule: finalise the unfinished node with the smallest known distance; it cannot improve, provided no edge is negative.

  • Precondition: non-negative edge weights.
  • Start with dist[src] = 0; other nodes are absent, not 0. Push (0, src).
  • Relax u -> v with weight w only on strict improvement, dist[u] + w < dist[v]: update and push.
  • Stale skip: after popping (d, u), skip it if d > dist[u].
  • Indexed heap with decrease-key: O((V + E) log(V + 1)) time, O(V) auxiliary space. Lazy heapq (push duplicates, skip stale): O(V + E log(E + 1)) time, O(V + E) auxiliary space. Say which one you mean.

Use it for single-source cheapest paths with non-negative costs. Equal costs: BFS (BFS, level-order and grid traversal). Negative costs: a different algorithm.

Under the hood

heapq is a binary min-heap stored in a Python list. heappush and heappop are O(log n), but there is no decrease-key. So "improve a distance" means pushing a second entry and leaving the old one inside; it surfaces later and the d > dist[u] test discards it.

Strict improvement bounds the heap: each node is expanded once, each edge relaxed at most once, so pushes are at most E + 1. Each operation costs O(log(E + 1)), and for a simple graph log E is at most 2 log V. Using <= on a zero-weight cycle pushes for ever (demo below).

On 3.12 you negate for a max-heap (3.14 adds *_max helpers).

Minimal example A cheaper route found later

PythonLazy heap: the stale entry is popped and skippedruns
import heapq
g = {"s": [("a", 4), ("b", 1)], "b": [("a", 2)], "a": []}
dist, h, skipped = {"s": 0}, [(0, "s")], []
while h:
    d, u = heapq.heappop(h)
    if d > dist[u]:
        skipped.append((d, u)); continue
    for v, w in g[u]:
        if v not in dist or d + w < dist[v]:
            dist[v] = d + w; heapq.heappush(h, (d + w, v))
print(dist, skipped)
Output
{'s': 0, 'a': 3, 'b': 1} [(4, 'a')]

In production Cheapest payout route with a negative-fee guard

Groww-style routing: nodes are banks and rails, edges are fees in paise. The function validates input, counts stale pops, and rebuilds the route.

PythonLazy-heap Dijkstra with parent pointersruns
import heapq

def cheapest(graph, src):
    for u, edges in graph.items():
        for v, w in edges:
            if w < 0:
                raise ValueError(f"negative fee {u}->{v}: {w}")
    dist, parent = {src: 0}, {src: None}
    heap, pushes, stale = [(0, src)], 1, 0
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            stale += 1
            continue
        for v, w in graph.get(u, ()):
            nd = d + w
            if v not in dist or nd < dist[v]:          # strict improvement
                dist[v], parent[v] = nd, u
                heapq.heappush(heap, (nd, v)); pushes += 1
    return dist, parent, pushes, stale

def route(parent, dst):
    if dst not in parent:
        return None
    path = []
    while dst is not None:
        path.append(dst); dst = parent[dst]
    return path[::-1]

fees = {"wallet": [("upi", 5), ("neft", 2), ("neft", 9)], "neft": [("bank", 4), ("upi", 1)],
        "upi": [("bank", 7), ("upi", 0)], "bank": [], "island": [("bank", 1)]}
dist, parent, pushes, stale = cheapest(fees, "wallet")
print(dist["bank"], route(parent, "bank"), "island" in dist, route(parent, "island"))
print(sorted(dist.items()), pushes, stale)
print(cheapest({}, "x")[0], cheapest(fees, "bank")[0])
try:
    cheapest({"a": [("b", -1)]}, "a")
except ValueError as e:
    print(f"ValueError: {e}")
Output
6 ['wallet', 'neft', 'bank'] False None
[('bank', 6), ('neft', 2), ('upi', 3), ('wallet', 0)] 5 1
{'x': 0} {'bank': 0}
ValueError: negative fee a->b: -1

See it happen Pop the smallest, skip the stale slip

41216s = 0a = 3b = 1t = 4 (done)
  1. Start: s has distance 0 and the heap holds only (0, s).
  2. Pop s and relax both edges: a becomes 4 and b becomes 1, two entries pushed.
  3. Pop (1, b): edge b-a gives 3, better than 4, so a is rewritten and (3, a) is pushed; b-t sets t to 7.
  4. Pop (3, a): edge a-t gives 4, better than 7, so t is rewritten to 4.
  5. Pop (4, a), the stale slip from frame 2: 4 is greater than dist[a] = 3, so it is skipped.
  6. Pop (4, t) and finish; the leftover (7, t) will later be skipped as stale. Route is s, b, a, t at cost 4.
Notice: the heap never edits an entry; it keeps both and trusts dist to reject the old one.
Scenario A

In your world

The situation

Your ETL job routes each settlement file through internal systems using per-hop costs in Postgres, picking the fewest hops.

What actually breaks

The fee table says direct = 40 against via_partner = 6 + 7 = 13. Fewest-hops picks direct for all 48,000 files a day, overpaying 27 each: 48,000 × 27 = 1,296,000 units a day, found by finance a month later.

What you'd do on Monday

Use Dijkstra with a negative-cost guard.

PythonPick the route (needs the cost table from Postgres)
fees = {}
for src, dst, cost in cur.execute("SELECT src, dst, cost FROM hop_cost"):
    fees.setdefault(src, []).append((dst, cost))
dist, parent, pushes, stale = cheapest(fees, "ingest")     # production block
path = route(parent, "ledger") or fail("no route")
Scenario B

Imagine you work at Groww

3,000-node payment graph

The numbers

Illustrative: 3,000 nodes, 40,000 fee edges, 1,000,000 lookups a day. The bound is 40,001 pushes × log2(40,001) ≈ 15.3, about 612,000 heap steps; a random graph needs far fewer (about 6,700 here). Measured with the dict-based code: about 120 ms per run. 1,000,000 × 0.12 s = 120,000 s ≈ 33 hours of one core.

What the Scenario-A answer does here

The Scenario A fix still works, but it runs per lookup. Most lookups share a few hundred sources.

What flips at this scale

One Dijkstra run answers every destination from a source. Compute the trees once: 3,000 sources × 0.12 s = 360 s, and cache the parent maps (3,000 × 3,000 = 9M entries). A lookup becomes a dict read plus a path walk.

The trade-off you'd defend

I would defend precomputed trees with invalidation over per-lookup Dijkstra, trading 9M cached entries and invalidation logic for microsecond lookups instead of 120 ms.

Illustrative; not Groww-published. The 120 ms is a local, noisy measurement on a random graph of that size (CPython 3.11).

Gotchas

Negative edge gives a wrong answer

Symptom

A distance is larger than a hand calculation: 3 instead of 2 below.

Cause

This settled-set variant treats the first pop as final. The stale-skip template returns 2 here, but re-expands nodes and never ends on a negative cycle.

Fix

Reject negative weights.

Pythonruns
import heapq
g = {"s": [("a", 3), ("b", 4)], "b": [("a", -2)], "a": []}
dist, h, done = {"s": 0}, [(0, "s")], set()
while h:
    d, u = heapq.heappop(h)
    if u in done:
        continue
    done.add(u)
    for v, w in g[u]:
        if v not in done and (v not in dist or d + w < dist[v]):
            dist[v] = d + w; heapq.heappush(h, (d + w, v))
print(dist["a"], "but the true cheapest to a is", 4 + (-2))
Output
3 but the true cheapest to a is 2

<= on a zero-weight cycle never terminates

Symptom

The job spins and memory grows.

Cause

Non-strict improvement re-pushes an equal distance round the cycle.

Fix

Use <. The demo caps at 20 pops.

Pythonruns
import heapq
g = {"a": [("b", 0)], "b": [("a", 0)]}
dist, h, pops = {"a": 0}, [(0, "a")], 0
while h and pops < 20:
    d, u = heapq.heappop(h); pops += 1
    for v, w in g[u]:
        if v not in dist or d + w <= dist[v]:          # wrong: should be <
            dist[v] = d + w; heapq.heappush(h, (d + w, v))
print("pops:", pops, "heap still non-empty:", bool(h))
Output
pops: 20 heap still non-empty: True

Equal distances compare the payload

Symptom

TypeError: '<' not supported between instances of 'dict' and 'dict'.

Cause

Tied distances make the tuple compare its second element.

Fix

Push comparable ids, or add a counter tie-break.

Pythonruns
import heapq
h = []
heapq.heappush(h, (5, {"id": 1}))
try:
    heapq.heappush(h, (5, {"id": 2}))
except TypeError as e:
    print(f"TypeError: {e}")
Output
TypeError: '<' not supported between instances of 'dict' and 'dict'

Tricky questions

The heap has stale entries, so the complexity is worse than V log V. True?
Most people say

Duplicates make it O(V²) in the worst case.

Actually

With strict improvement pushes are at most E + 1, so lazy time is O(V + E log(E + 1)), which is O(E log V) for a simple graph. Heap space is O(V + E), not O(V).

Scenario question

You're handed a graph of 100,000 services with call latencies and asked for the fastest route from one gateway to every service. The input may contain bad data.

Model answer

I'd check weights are non-negative, then run lazy-heap Dijkstra with strict relaxation and a stale skip. With E at 500,000 that is about 500,000 × 19 ≈ 9.5M heap steps, a few seconds. The trade-off: lazy duplicates cost O(E) memory against O(V) for an indexed heap, which I'd accept.

Interview corner

CommonWhat must be true for Dijkstra to be correct?
“I'd say every edge weight is non-negative. That is what makes the smallest unfinished distance final when I pop it.”
TrickPython's heapq has no decrease-key. How do you cope?
“I push a new entry and skip stale ones when popped by comparing against the best distance. It can add up to E entries but keeps the code simple.”
DesignHow do you serve many shortest-path lookups?
“I'd precompute single-source results for the hot sources and invalidate when weights change. I trade cache memory and invalidation logic for microsecond lookups.”

Memory hook

Bus fares in a notebook: finalise the cheapest, bin stale slips.

If you remember only one thing:

Non-negative weights, strict improvement, skip stale pops, and say whether your heap is indexed or lazy.

Self-check

  1. Why must weights be non-negative?

    A later edge cannot improve a popped node.

  2. What does d > dist[u] detect?

    A stale entry.

  3. Time and space of lazy heapq Dijkstra?

    O(V + E log(E + 1)) time, O(V + E) space.

Prove it

Generate a seeded random graph with 3,000 nodes and 40,000 edges (weights 1 to 500), time cheapest from 20 sources and paste the average. Also paste a zero-mismatch check against Bellman-Ford style relaxation on 200 nodes.