R06 · Week 6 Recall & Drill

Weekly revision · Week 6 · Covers 5 sessions from Mon–Fri.

Sessions covered

• S026 — Stacks & Queues — LIFO/FIFO in Practice
• S027 — Recursion — Call Stack, Base Case, Worked Examples
• S028 — Trees & BSTs — Traversal (BFS/DFS)
• S029 — Heaps & Priority Queues
• S030 — Graphs — Representation, BFS, DFS, Shortest Path

90-min structure

Blank-page reconstruction · 30 min

S026 · Stacks & Queues

1. State LIFO and FIFO in one sentence each, and name the correct Python container for each.
2. Explain the monotonic-stack pattern in two sentences, and say what invariant the stack maintains.
3. Implement a queue using two stacks, and state the amortised cost per operation.

Gotcha you probably forgot: choosing a stack or a queue is a scheduling decision, not a storage decision. The container is the same; only the removal policy differs. That policy determines the order your problem is explored in, which is why swapping a stack for a queue in a traversal does not just reorder the output — it changes which answers the algorithm can produce at all.

S027 · Recursion

1. Name the three ingredients of every correct recursion, and identify each one in a factorial implementation.
2. Explain why naive Fibonacci is exponential, and how a cache decorator collapses it to linear.
3. Say why Python raises a recursion error at around a thousand levels, and give both fixes.

Gotcha you probably forgot: converting recursion to iteration does not remove the stack — it moves it. Only tail recursion becomes a plain loop for free. General recursion becomes a loop plus an explicit stack you manage on the heap. The reason to do it is that the heap is far larger than the call stack, not that the stack disappears.

S028 · Trees & BSTs

1. State the BST invariant in one sentence, precisely enough that it excludes the common wrong version.
2. Name the four traversal orders and give one problem that specifically needs each.
3. Explain why databases use B-trees rather than binary search trees.

Gotcha you probably forgot: a plain BST gives lookup proportional to its height, not to the logarithm of its size. Logarithmic behaviour holds only when the tree is balanced, and nothing in the plain insert algorithm enforces balance. Insert already-sorted data and you have built a linked list with extra pointers — every lookup is a full traversal. Self-balancing variants exist precisely because this failure is so easy to trigger.

S029 · Heaps & Priority Queues

1. State the min-heap invariant, then say what it does not tell you.
2. Explain why a binary heap lives in a flat array, and write the index arithmetic for parent and children.
3. Explain why finding the top K of n items with a size-K heap beats sorting everything.

Gotcha you probably forgot: the common Python gotcha is tuple comparison. Pushing (priority, item) works until two items share a priority, at which point the heap compares the second element — and if item is a type that does not support comparison, it raises. The standard fix is a monotonically increasing counter as a tiebreaker: push (priority, counter, item).

S030 · Graphs

1. Name the three representations and say which is the default in real code, with the density argument.
2. Explain why every traversal needs a visited set, and what happens without one.
3. Outline Kahn's algorithm for topological sort, and say what it produces when the graph has a cycle.

Gotcha you probably forgot: Dijkstra breaks on negative edge weights, and it breaks silently. The algorithm finalises a node's distance the moment it is popped, on the assumption that no later path can improve it — an assumption that holds only when every edge adds cost. A negative edge can improve an already-finalised distance, and nothing in the algorithm detects that.

Hands-on drill · 30 min

Task: build one small graph and attack it with every algorithm from this week — BFS, DFS, Dijkstra, topological sort — writing each from memory.

Step 1 — the graph (5 min)

mkdir -p ~/projects/w6-drill && cd ~/projects/w6-drill

# graph.py
# Weighted directed acyclic graph. A -> F has one direct edge that is
# expensive, and a longer chain that is cheaper. This is the case that
# separates "fewest edges" from "lowest cost".
GRAPH: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 1), ("C", 4), ("F", 20)],
    "B": [("C", 2), ("D", 5)],
    "C": [("D", 1), ("E", 3)],
    "D": [("E", 1), ("F", 6)],
    "E": [("F", 2)],
    "F": [],
}

Step 2 — BFS and DFS from memory (8 min)

# traverse.py
from collections import deque
from graph import GRAPH
 
 
def bfs_fewest_edges(start: str, goal: str) -> list[str] | None:
    """Fewest EDGES, ignoring weight entirely."""
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for nxt, _weight in GRAPH[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, path + [nxt]))
    return None
 
 
def dfs_all_reachable(start: str) -> set[str]:
    """Iterative DFS with an explicit stack — no recursion limit to hit."""
    stack, visited = [start], set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nxt, _weight in GRAPH[node]:
            if nxt not in visited:
                stack.append(nxt)
    return visited
 
 
if __name__ == "__main__":
    print("bfs A->F :", bfs_fewest_edges("A", "F"))
    print("reachable:", sorted(dfs_all_reachable("A")))

Expected outcome: BFS returns the two-node path ['A', 'F'], because that is genuinely the fewest edges — and it is also the most expensive route at cost 20. Reachable is all six nodes. Note what just happened: BFS gave a correct answer to the question it was asked and a wrong answer to the question you probably meant.

Step 3 — Dijkstra, which asks the right question (10 min)

# dijkstra.py
import heapq
from graph import GRAPH
 
 
def dijkstra(start: str, goal: str) -> tuple[int, list[str]] | None:
    # (cost, counter, node, path) — the counter is the tiebreaker that stops
    # Python from trying to compare lists when two costs are equal.
    counter = 0
    heap = [(0, counter, start, [start])]
    best: dict[str, int] = {}
    while heap:
        cost, _c, node, path = heapq.heappop(heap)
        if node in best:          # lazy deletion: first pop wins, rest are stale
            continue
        best[node] = cost
        if node == goal:
            return cost, path
        for nxt, weight in GRAPH[node]:
            if nxt not in best:
                counter += 1
                heapq.heappush(heap, (cost + weight, counter, nxt, path + [nxt]))
    return None
 
 
if __name__ == "__main__":
    print("dijkstra A->F:", dijkstra("A", "F"))

Expected outcome: Dijkstra returns a cost strictly below 20 along a multi-hop path, not the single direct edge. Work the arithmetic by hand before running it and confirm the program agrees with your paper answer — that manual check is the drill. The lesson to write down: BFS was not slower here, it was answering a different question.

Step 4 — topological sort and cycle detection (7 min)

# toposort.py
from collections import deque
from graph import GRAPH
 
 
def kahn(graph: dict[str, list[tuple[str, int]]]) -> list[str] | None:
    indeg = {n: 0 for n in graph}
    for node in graph:
        for nxt, _w in graph[node]:
            indeg[nxt] += 1
    queue = deque(sorted(n for n, d in indeg.items() if d == 0))
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt, _w in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    # Fewer nodes emitted than exist means something never reached in-degree 0.
    return order if len(order) == len(graph) else None
 
 
if __name__ == "__main__":
    print("topo order:", kahn(GRAPH))
 
    cyclic = {k: list(v) for k, v in GRAPH.items()}
    cyclic["F"] = [("A", 1)]          # close the loop
    print("topo on cyclic graph:", kahn(cyclic))

Expected outcome: the first call emits all six nodes in a dependency-respecting order starting at A. The second returns None. That None is the important half: Kahn's algorithm is a cycle detector as well as a sorter, and the detection is free — if the queue empties before every node is emitted, the remaining nodes are exactly the ones trapped in a cycle. This is how a build system tells you that your dependencies are circular.

Gap analysis + next week preview · 10 min

• Did you predict the BFS-versus-Dijkstra divergence before running Step 3? If you expected them to agree, that is the misconception landing on you in real time — and it is the single most common wrong answer in graph interviews.
• Which algorithm did you have to look up? Rewrite it from scratch tomorrow, on paper, before you touch a keyboard.
• Can you state what Kahn's algorithm returning a short list means about the graph? If not, re-read the cycle-detection half of S030.

Next week (S031–S035) finishes DSA and opens databases: sorting with merge and quicksort and when to trust the built-in; binary search as the pattern behind a whole family of problems; dynamic programming with memoisation and tabulation; greedy versus backtracking; and then the relational model with tables, keys, and normalisation. The memoisation instinct you drilled in S027 is precisely the bridge into dynamic programming.

Part of the 6-month evergreen learning plan.