Track A — The Follow-Up Bank

150 questions asked after your code works, with mechanism-level answers.

The coding round is not decided by whether the tests pass. It is decided by the ten minutes after they pass, when the interviewer starts asking why. This is that conversation, written out.

Companion to WARMUP.md (the patterns) and harness/ (the timed problems). Every measured number here was produced by a script on CPython 3.13; the machine-dependent ones are marked, and the point is always the ratio, not the absolute.

Table of Contents

• How to Use This
• Section 0: The Six Shapes of Follow-Up
• Section 1: Complexity, and the Question Behind It (Q1–Q16)
• Section 2: Predecessor Queries and Versioned State (Q17–Q28)
• Section 3: Delta Logs, Undo and Redo (Q29–Q38)
• Section 4: Caches and Intrusive Lists (Q39–Q52)
• Section 5: Rate Limiting (Q53–Q64)
• Section 6: Heaps and Deterministic Scheduling (Q65–Q76)
• Section 7: Streaming and Chunk Boundaries (Q77–Q86)
• Section 8: Graphs, Topological Order, Cycles (Q87–Q96)
• Section 9: Write-Ahead Logs and Crash Recovery (Q97–Q108)
• Section 10: Dedup and Probabilistic Structures (Q109–Q118)
• Section 11: Backpressure and Bounded Concurrency (Q119–Q130)
• Section 12: "How Would You Test This?" (Q131–Q140)
• Section 13: "Now Make It Concurrent" (Q141–Q150)
• The Twenty That Matter Most
• References

How to Use This

Not front to back. Work a harness problem, then read the section that matches it and answer out loud before reading the answer. The gap between your sentence and the written one is the finding — same loop as the worked designs.

Say the answer aloud. These are spoken answers, not written ones. An answer you can write but cannot say in twenty seconds is not usable in a round, and the failure mode is specific: you will start explaining, realize you are three clauses deep, and trail off. Practise the first sentence until it lands on its own.

Everything you miss goes to review/ at the 1/3/7/21-day intervals.

Section 0: The Six Shapes of Follow-Up

Every follow-up you will get is one of six, and knowing which one you are in tells you what kind of answer is wanted. Misclassifying the shape is how good engineers give irrelevant answers.

The single highest-value habit: answer the shape you were asked, then stop. Volunteering a second answer to a question nobody asked is the most common way to turn a correct answer into a doubtful one.

And the meta-answer for when you do not know: "I don't know — here's how I'd find out." Followed by an actual method. That scores far above a confident guess, and interviewers at this level are specifically listening for whether you can say it.

Section 1: Complexity, and the Question Behind It (Q1–Q16)

Q1. "What's the time complexity?" — what does a strong answer contain that a weak one does not?

The weak answer is a letter: "O(log n)." The strong answer is a letter plus the operation that produces it plus what n is: "O(log n) per query — it's a binary search over the version list, where n is the number of versions of that one key, not the number of keys."

Naming n is where most people lose the point, because complexity claims are meaningless without it and interviewers use exactly this to check whether you understand your own data structure.

Q2. Your solution is O(n log n). The interviewer says "can you do better?" What is the correct first move?

Ask what the input looks like, and check the lower bound. If the problem requires a comparison sort, O(n log n) is optimal and "can you do better" has the answer "not in comparisons — but if the keys are bounded integers, a radix/counting approach is O(n)."

Jumping straight to optimizing is the trap: half the time the question is testing whether you know the bound exists.

Q3. Why is bisect.insort into a Python list O(n) and not O(log n)?

The search is O(log n); the insert is O(n) because a Python list is a contiguous array of pointers and inserting in the middle memmoves everything after it.

Measured (CPython 3.13, mid-list insert+pop):

Clean linear scaling. memmove is fast — about 6 GB/s of pointers here — which is why the O(n) survives to surprisingly large n, and that is exactly what makes it a trap: it does not look quadratic until it suddenly does.

Q4. So when is a sorted list still the right answer despite the O(n) insert?

When n is small (below ~1,000 the constant beats a tree's pointer chasing), when the workload is read-heavy (binary search on contiguous memory is extremely cache-friendly), or when inserts are mostly at the end (append is amortized O(1); bisect.insort at the tail does no move).

The last case is the important one and it is the versioned-KV pattern: versions arrive in increasing order, so every insert is an append and the O(n) never happens. Say that — it turns a weakness into a deliberate choice.

Q5. "This is O(1) amortized." The interviewer asks what happens to the p99. What are you being asked?

Whether you know amortized is not the same as worst-case. A dynamic array's append is O(1) amortized, but the resize is O(n) and it lands on one unlucky caller.

For a latency SLO, amortized is the wrong metric — the p99 sees the resize. The fixes are incremental resizing (move a few elements per operation), pre-sizing when the count is known, or a structure with a real O(1) worst case (a linked list of chunks).

Q6. Give the complexity of heapq.heappush and explain why the measured cost barely grows.

O(log n) — sift-up compares against parents up the tree. Measured push+pop:

A 100× increase in n for a 1.5× increase in cost. log₂(100,000)/log₂(1,000) = 1.66, so the measurement matches the theory almost exactly — and being able to say "the measurement matches log₂ scaling" is worth more than either number alone.

Q7. list.pop(0) versus collections.deque.popleft() — quantify it.

Measured at n = 100,000: deque.popleft 40.7 ns, list.pop(0) 15,895 ns — 390× slower, and the gap grows linearly with n because pop(0) shifts every remaining element.

A deque is a doubly-linked list of fixed-size blocks, so both ends are O(1) and it stays mostly cache-friendly. This is the single most common accidental O(n²) in Python: a queue implemented as a list.

Q8. "What's the space complexity?" — the part people forget.

The recursion stack, and the output. A recursive DFS over a graph of n nodes is O(n) space even if you allocate nothing, and on a path graph it is O(n) stack frames — which in CPython means RecursionError at ~1,000 by default.

Also: intermediate collections. sorted(big_generator) materializes everything. Saying "O(1) auxiliary, O(n) output" shows you distinguish the two.

Q9. When is O(n²) the right answer?

When n is bounded and small, and the O(n log n) alternative costs correctness or clarity. n=100 means 10,000 operations — microseconds.

The right way to say it: "This is O(n²), which is fine because n is bounded at 100 by the API. If that bound changed I'd switch to X." That is a decision, and it scores far better than an accidental O(n²) or an over-engineered O(n log n) for n=100.

Q10. The interviewer says "assume n is a billion." What actually changes?

It stops being an algorithms question and becomes a memory question. A billion 8-byte pointers is 8 GB — before any objects. So:

1. Does it fit in RAM? If not, the algorithm must be external (sort-merge, not in-place).
2. Does one pass suffice? Multiple passes over a billion items means multiple disk reads.
3. Can it be approximate? Bloom filters, HyperLogLog, count-min trade a bounded error for orders of magnitude of memory.

Sequential access beats random access by a factor of hundreds at this scale, which is why external algorithms are sort-based rather than hash-based.

Q11. What is the complexity of x in my_list versus x in my_set, and when is the list faster?

O(n) versus O(1). The list wins below about 10 elements, because a set requires hashing x (which for a long string means reading the whole string) while a small list is a few pointer comparisons with is short-circuiting before ==.

The identity short-circuit is the mechanism worth knowing: CPython's list __contains__ compares is first, so a hit on an interned object is one pointer compare.

Q12. Your dict has a million entries. What is the real memory cost?

Far more than the data. A CPython dict of 1M entries: the compact index table plus an entries array of (hash, key*, value*) = 24 bytes/entry, so ~24 MB before the keys and values themselves. Add small-int/str objects at 28–50 bytes each and you are at 100+ MB for a "million integers".

If that matters: use array, numpy, or __slots__ objects, or key on packed bytes. Knowing that a dict costs ~10× the naive estimate is the useful part.

Q13. "Is your solution cache-friendly?" — how do you answer without hand-waving?

By naming the access pattern, not the structure. "The hot loop walks a contiguous array in order, so it's prefetch-friendly. The version lookup chases pointers into a dict, which is a cache miss per lookup — that's the part I'd optimize first if profiling said so."

The number to have: an L1 hit is ~1 ns, a main-memory miss is ~80–100 ns. Two orders of magnitude, which is why a linear scan of 100 contiguous items can beat a hash lookup.

Q14. Why can an O(n) algorithm beat an O(log n) one?

Because complexity ignores constants and memory hierarchy. A linear scan over a contiguous array of 64 items is one or two cache lines and full prefetching; a binary search over a pointer-based tree is ~6 dependent cache misses that cannot be prefetched because each address depends on the previous load.

"Dependent loads defeat prefetching" is the mechanism, and it is why B-trees exist: they restore locality by making nodes cache-line-sized.

Q15. The interviewer asks for the complexity of your solution "in terms of the output size."

They are pointing at output-sensitive complexity, and usually at a place where you claimed too much. A range query over a versioned store is not O(log n) — it is O(log n + k) where k is the number of results, because you still have to emit them.

Getting this right matters when k can be huge: "O(log n + k), and since k is unbounded I'd paginate rather than materialize."

Q16. "What's the complexity?" for an amortized structure with a rebuild — how do you state it?

Three numbers, and say all three: amortized, worst-case, and the rebuild's trigger.

"Amortized O(1) per insert; worst case O(n) when the segment merges; merges happen every n inserts, so the p99 sees it once in n operations. If that's not acceptable I'd merge incrementally — a few elements per insert — which trades a higher constant for a bounded worst case."

That is the complete answer for every LSM-shaped structure — the cache, the WAL, the text index, the segment merger — and it is one of the most reusable sentences in this bank.

Section 2: Predecessor Queries and Versioned State (Q17–Q28)

Pairs with WARMUP ch. 1 and versioned_kv.

Q17. Why is get(key, at_version) a predecessor query and not a lookup?

Because the version you are asked for usually does not exist for that key. get("x", 57) means "the value of x as of version 57", which is the value written at the largest version ≤ 57. That is bisect_right(versions, 57) - 1.

Naming it "a predecessor query" is worth real credit — it connects the problem to a known family (and to d02, d06, MVCC, and time-series as-of joins) and it tells the interviewer you have seen the shape before.

Q18. Why bisect_right(...) - 1 and not bisect_left?

bisect_right(v, 57) returns the insertion point after any existing 57, so subtracting 1 gives the last element ≤ 57 — which is the definition of predecessor.

bisect_left returns the point before existing equals, so bisect_left - 1 gives the last element < 57, which is wrong when a write happened exactly at 57.

The off-by-one is the whole question and the test that catches it is get(k, exact_write_version).

Q19. What does get return for a version before the key existed, and why does the choice matter?

None / not-found — and the reason it matters is that bisect_right(...) - 1 == -1 in that case, and Python's negative indexing will happily return the last element instead of raising.

i = bisect_right(versions, at) - 1
if i < 0:                       # <-- without this, versions[-1] is the NEWEST value
    return None

This is the single most common bug in this problem and it is silent: it returns a plausible value from the future.

Q20. A key is deleted at version 40 and re-created at 60. What does get(k, 50) return?

Not found. Deletion must be a versioned entry (a tombstone), not a removal from the list.

versions[k].append((40, TOMBSTONE))
versions[k].append((60, "new"))

If delete removed history, get(k, 50) would find version 30's value and return data that was deleted — a correctness bug that also violates any audit requirement. Tombstones are the same primitive as in d07 and m06; the pattern is "delete is a write".

Q21. What happens when versions arrive out of order?

bisect.insort handles it correctly and costs O(n) for the shift — which is fine, because out-of-order arrival is rare.

The interesting answer is which invariant breaks: if you optimized set to append (assuming monotonic versions), an out-of-order write silently corrupts the sort order and every subsequent bisect is wrong. So the optimization needs an assertion, not just a comment:

assert not vs or version > vs[-1][0], "versions must be monotonic"

Q22. How would you support "list all keys as of version V"?

Iterate the keys and predecessor-query each: O(K log n), which is fine for thousands of keys and not for millions.

For millions, invert the layout: keep a single global list of (version, key, value) sorted by version, and a snapshot is a scan up to V — but then per-key lookup degrades. The two layouts optimize opposite queries and you cannot have both from one index; say that rather than inventing a structure that claims to.

Q23. Memory grows without bound. What do you do?

Garbage-collect versions below the oldest live reader, exactly like MVCC:

watermark = min(active_snapshot_versions, default=current_version)
# For each key, keep the last version <= watermark plus everything after.

Keeping the last version at or below the watermark is the subtle part — you cannot drop all versions ≤ watermark, or a reader at the watermark loses the value that was current for it.

Q24. What is a "long-running reader" and why is it a production problem?

A snapshot held open for hours: it pins the watermark, so no version can be collected, and the store grows without bound. This is exactly the PostgreSQL long-transaction/bloat problem.

The mitigations, and each has a cost: a maximum snapshot age (readers get an error and must retry), a size-based forced collection (the reader sees SnapshotTooOld), or accepting the growth and alarming on it. Naming the tradeoff beats picking one.

Q25. bisect needs a sorted list of comparable keys, but your entries are tuples (version, value). What is the hazard?

Tuple comparison falls through to the second element when versions tie — and if value is not comparable (a dict, say), bisect raises TypeError at an unpredictable moment.

Two fixes: keep versions unique (they should be), or bisect on a separate key list:

i = bisect_right(self.version_list[k], at) - 1     # keys only
value = self.value_list[k][i]

Parallel lists are uglier and they remove a whole class of comparison bug. Prefer them in interview code and say why.

Q26. How does this become MVCC?

It already is. version becomes a transaction ID; a transaction reads at its snapshot version and writes at its commit version; commit assigns a monotonically increasing version.

What is missing from the toy version and worth naming: write-write conflict detection (two transactions writing the same key must not both commit), and the atomicity of multi-key commits. "This is the read path of MVCC; the write path needs conflict detection" is the complete answer.

Q27. Make version a wall-clock timestamp. What breaks?

Clocks go backwards (NTP steps, leap-second smearing, VM migration), so monotonic is violated and bisect is operating on an unsorted list — silently wrong results, not an error.

Also: ties. Two writes in the same millisecond are indistinguishable, so "last write wins" is undefined.

Use a logical counter, or a hybrid logical clock if you need both wall-time meaning and monotonicity (WARMUP §3.5).

Q28. Now shard this across ten machines. What is the hard part?

A consistent snapshot across shards. Each shard has its own version counter, so get_all(V) means different things on different shards.

The options — a global version service (a bottleneck, but simple), or per-shard versions plus a vector/HLC (no bottleneck, harder reads) — are worked in full in d02. Saying "this is the same problem d02 solves, and here is the fork" is exactly the right depth for a coding round.

Section 3: Delta Logs, Undo and Redo (Q29–Q38)

Pairs with WARMUP ch. 2 and token_stream_differ.

Q29. Snapshots or deltas — how do you choose?

By the ratio of change size to state size, and say it that way:

• Small change to large state (one cell in a spreadsheet) → deltas.
• Large change to small state, or reconstruction speed matters → snapshots.
• Both, in practice: periodic snapshots plus deltas between them, which bounds replay length.

"Snapshot every N operations so replay is bounded" is the answer to a follow-up you will get regardless of which you pick.

Q30. Undo requires the inverse of every operation. Which operations have no inverse?

Any that loses information: clear(), truncate(), overwriting without capturing the old value, and anything non-deterministic (now(), random()).

The fix is to make the delta carry what is lost — store the old value in the undo record, which turns "inverse of set" into "set back to what it was". Undo logs record old values precisely because inverses do not generally exist, and that sentence is the whole insight.

Q31. What is the difference between an undo log and a redo log?

Undo stores the old value: replay it backwards to roll back. Redo stores the new value: replay it forwards to roll forward.

Databases keep both: undo for aborting transactions and MVCC reads, redo for crash recovery. ARIES is "redo everything, then undo the losers" — and knowing that one line is usually enough depth for this round.

Q32. A user undoes three operations, then performs a new one. What happens to the redo stack?

It is discarded. History has branched, and the redos are now unreachable.

The alternative is a tree, not a stack — Vim's undo tree, Emacs's undo-redo. Worth mentioning as a known design, and worth not implementing unless asked: it changes the API from undo()/redo() to navigating a graph, which is a product decision.

Q33. Your undo stack is unbounded. Bound it. What is the correct policy?

Cap by memory, not by count. A hundred one-character edits are trivial; a hundred paste-a-megabyte operations are not.

while self.total_bytes > LIMIT and len(self.stack) > MIN_DEPTH:
    self.total_bytes -= self.stack.popleft().nbytes      # drop the OLDEST

Drop from the old end, and keep a floor so that a single huge operation cannot empty the stack — "undo does nothing" is a worse failure than using extra memory.

Q34. How do you compact a delta log?

Merge adjacent deltas that touch the same key: three writes to cell A collapse to one. This is LSM compaction, and it is the same operation as segment merging in d07 and m06.

What it costs, and you must say it: compaction destroys intermediate states, so undo can no longer stop between them. Compact only below the undo horizon — the oldest state any user can return to.

Q35. The delta log is replayed to reconstruct state. It is slow. Where does the time go?

Almost never in applying the deltas — in reading them. Replay is I/O-bound and usually random-access if the log is not contiguous.

The fixes are ordered by leverage: (1) snapshot more often so replay is shorter; (2) store the log contiguously so replay is one sequential read; (3) batch the apply.

Naming that it is I/O and not CPU is the answer — it redirects the optimization to the thing that matters.

Q36. Two users edit concurrently. What breaks, and what are the real options?

Deltas are positional, and a concurrent insert shifts positions, so applying B's delta after A's puts B's edit in the wrong place.

Three real answers:

• Locking — simple, correct, and it does not scale to collaborative editing.
• OT (operational transformation) — transform B's operation against A's. Correct, notoriously hard to get right, and what Google Docs uses.
• CRDTs — make operations commutative by construction so order does not matter. Simpler correctness, larger metadata.

"Positional deltas do not commute" is the diagnosis, and everything else follows from it.

Q37. Deltas are applied in order. How do you detect a missing one?

Sequence numbers, checked on apply:

if delta.seq != self.applied_seq + 1:
    raise GapDetected(expected=self.applied_seq + 1, got=delta.seq)

Detecting a gap requires that gaps are detectable, which requires dense sequence numbers — a timestamp will not do it. This is the same mechanism as WAL LSNs (Q98) and the event-dedupe window.

Q38. How do you test an undo/redo implementation properly?

Property-based, with a model. Generate random operation sequences and assert:

apply(ops) then undo(k) then redo(k)  ==  apply(ops)          # round-trip
undo to empty                          ==  initial state       # full unwind
state after any prefix                 ==  a naive model's     # oracle

The naive model is the point: implement the state directly (a plain dict) with no delta log and compare. A model-based test finds the bugs that example tests never reach, because the failing sequence is usually 7 operations long and nobody writes that by hand.

Section 4: Caches and Intrusive Lists (Q39–Q52)

Pairs with WARMUP ch. 3, lru_ttl_cache, and object_pool.

Q39. Why does an LRU need a doubly-linked list rather than a singly-linked one?

Because eviction and promotion both need O(1) removal from the middle, and removing a node requires knowing its predecessor. A singly-linked list makes that O(n).

The entry object is the list node (intrusive), so the dict maps key → node directly and no search is ever needed.

Q40. Why sentinel head and tail nodes?

They remove every null check. With sentinels, every real node has a non-null prev and next, so unlink is four unconditional pointer assignments:

node.prev.next = node.next
node.next.prev = node.prev

Without them you need four branches for the empty/first/last cases, and that is where the bugs live — an interviewer who has implemented one will specifically look for sentinels.

Q41. Python has OrderedDict. Why implement the list?

Usually you should not — OrderedDict.move_to_end is 21.9 ns and popitem(last=False) is part of a 123 ns promote-and-evict, both C-implemented.

Implement it when the interviewer asks for it (they are testing pointer manipulation), or when you need a policy OrderedDict cannot express — a TTL heap ordered differently from the LRU order, segmented LRU, or entries in two lists at once. The last is the real reason intrusive lists exist.

Q42. LRU with TTL: where does the expiry live?

Two structures, and they must stay consistent:

• Recency: the doubly-linked list.
• Expiry: a min-heap on expiry time, or a lazy check on access.

Lazy expiry alone leaks: an entry never accessed again is never evicted and occupies the cache forever. Active expiry alone is expensive: scanning every entry per tick.

The production answer is both — lazy on read (free, correct) plus a bounded active sweep (Redis samples 20 random keys per cycle and repeats if >25% were expired).

Q43. Deleting from the middle of a heap is O(n). How do you expire from a TTL heap?

Lazy deletion with a validity check. Do not remove from the heap; mark the entry dead and check on pop:

while heap:
    exp, key, entry = heap[0]
    if entry.dead or entry.expiry != exp:     # stale heap record
        heappop(heap); continue
    if exp > now: break                        # nothing expired yet
    heappop(heap); evict(key)

entry.expiry != exp is the trick that handles TTL updates: refreshing an entry pushes a new heap record and the old one is detected as stale rather than being removed. Same pattern as the scheduler's cancellation (Q68).

Q44. The heap fills with dead entries. When do you compact it?

When dead exceed live, which bounds memory at 2×:

if self.dead_count > len(self.heap) // 2:
    self.heap = [r for r in self.heap if not r.entry.dead]
    heapify(self.heap)             # O(n), amortized O(1) per insert
    self.dead_count = 0

heapify is O(n), not O(n log n) — Floyd's algorithm, sifting down from the middle. Getting that right is a small but real signal.

Q45. LRU versus LFU — when does each fail?

LRU fails on a scan: one pass over a large dataset evicts the entire working set, and this is the classic "a backup job destroyed the cache" incident.

LFU fails on a shift: an item popular last week keeps a high count forever and blocks genuinely hot new items. Fixed by aging — halve all counters periodically.

The production answer is a hybrid: segmented LRU (a probationary and a protected segment) or TinyLFU (an LFU admission filter in front of an LRU). TinyLFU's insight — under pressure the scarce resource is the right to occupy the cache, not the space — recurs in m02 and m07.

Q46. What is cache stampede and how do you prevent it?

A hot key expires and every concurrent request misses simultaneously, all hitting the origin. A single key can generate thousands of identical backend requests.

Three mechanisms, and each is worth naming:

• Single-flight: the first miss takes a per-key lock and computes; the rest wait for its result.
• Probabilistic early expiry: refresh at expiry - β·ln(rand())·Δ so one request refreshes before the herd arrives (XFetch).
• Serve-stale-while-revalidate: return the expired value and refresh in the background.

Single-flight is the one to implement; the others are what you mention.

Q47. What is a negative cache and why does it need a different TTL?

Caching "this key does not exist" — otherwise every lookup of a missing key hits the origin, and an attacker can generate unbounded misses on purpose.

A shorter TTL, because a negative entry becomes wrong the moment the key is created, while a positive entry stays valid until it changes. Getting the asymmetry right is the answer; getting it wrong means creating an object and not seeing it for five minutes.

Q48. Your cache is 90% hit rate. Doubling its size takes it to 92%. Was that worth it?

Convert to what matters — origin load — not hit rate. Misses went from 10% to 8%: a 20% reduction in backend traffic for 2× memory.

Whether that is worth it depends on which resource is scarce, and the honest answer names both: "20% less origin load for 2× memory. Worth it if the origin is the bottleneck, not if memory is. I'd want the marginal-hit-rate curve — it's usually logarithmic, so the next doubling buys about half as much."

Q49. __slots__ and the object pool — what is the trap?

__slots__ removes __weakref__ along with __dict__. A pooled object that must be weak-referenced (for leak detection) needs it declared explicitly:

class Pooled:
    __slots__ = ('data', 'in_use', '__weakref__')      # <-- required

Without it, weakref.ref(obj) raises TypeError. This is a real bug that the object-pool harness gate catches, and it is exactly the kind of detail that separates having read about __slots__ from having used it.

Q50. A subclass omits __slots__. What happens, and how do you detect it?

It gets a __dict__ back and the memory saving is lost for that subclass.

And on CPython 3.11+ the detection is not what you expect. The instance dict is managed and created lazily, so a slotted and an unslotted instance measure identical — same sys.getsizeof, same tracemalloc — until something is actually stored:

The reliable tell is hasattr(x, "__dict__"), not the size. Measured, not assumed — this was found by a failing test, not by reading.

Q51. How do you detect a leak from an object pool?

Weak references plus a checkout ledger. On acquire, record a weakref and the acquiring stack; on release, clear it. An object whose weakref dies while still marked checked-out was dropped without release.

def _on_dead(ref):
    if ref in self.checked_out:
        log.error("pool object GC'd while checked out, acquired at %s", self.sites[ref])

Better: a context manager, so release cannot be forgotten. The best leak detection is an API that makes the leak impossible, and saying that is stronger than any detector.

Q52. Should the pool clear an object's data on release or on acquire?

On release, for two reasons: the caller's data does not sit in the pool longer than necessary (a security consideration if it is sensitive), and an acquire is on the latency path while a release usually is not.

The counter-argument is real and worth conceding: clearing on acquire means never clearing objects that are released and then discarded at shutdown. Clear on release, and say why — it is a defensible call either way and the reasoning is what is being scored.

Section 5: Rate Limiting (Q53–Q64)

Pairs with WARMUP ch. 4, rate_limiter, and d03.

Q53. Name the four algorithms and the one-line failure of each.

Token bucket is the default, and the burst is a feature: it is the only one of the four that can express "100/s sustained, 1,000 at once is fine".

Q54. Why does fixed window allow 2× the limit?

100 requests at 0:59 and 100 more at 1:01 are in different windows and both are allowed — 200 requests in 2 seconds against a 100/minute limit.

The general statement: the burst is bounded by 2 × limit over 2 × window, and it is why fixed window is only acceptable when the limit is a rough guard rather than a contract.

Q55. Derive the token bucket refill without a timer.

Lazily, from elapsed time. No background thread, no timer:

now = time.monotonic()
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= cost:
    self.tokens -= cost
    return True
return False

Two details that get missed: clamp to capacity before the check (otherwise idle time accumulates unbounded credit), and update last unconditionally (updating only on success means a rejected request's elapsed time is refilled twice).

Q56. time.time() or time.monotonic() — and what actually goes wrong?

monotonic. time.time() can jump backwards on an NTP step, which makes now - last negative, which removes tokens — and a large enough backward step can leave the bucket permanently drained.

Measured resolutions on this machine: monotonic 41.7 ns, time 1 µs. Monotonic is both safer and finer-grained. There is no case for time.time() in a limiter.

Q57. Two threads call allow() simultaneously. What is the failure?

A classic read-modify-write race: both read tokens = 1, both decrement, both return True, and the bucket goes to -1. The limit is exceeded.

The fix is a lock around the whole read-check-write, and the answer worth giving is why it is cheap: the critical section is a few arithmetic operations, so contention is negligible and a lock-free version buys nothing.

And the Python-specific caveat — do not rely on the GIL. Measured on 3.13, counter += 1 in a tight loop across 4 threads loses zero updates, because since 3.10 the eval breaker is only checked at backward jumps and calls, so the read-modify-write completes within one iteration. That is an implementation detail, not a guarantee, and it disappears under free-threading (PEP 703). Lock anyway.

Q58. Per-key buckets. How do you stop the map growing without bound?

Bound it as a cache, not as a map. Options:

• LRU with a cap — bounded, and evicting a bucket resets a client's state (they get a free burst, which is usually acceptable).
• TTL eviction — remove buckets idle for > capacity / rate seconds, which is exactly the time a bucket takes to refill to full. After that the state is indistinguishable from a fresh bucket, so dropping it is free — this is the elegant answer.

The second is strictly better and the reasoning is the point.

Q59. What should the API return besides a boolean?

Decision(allowed: bool, remaining: int, retry_after: float, limit: int)

retry_after computed exactly — (cost - tokens) / rate — so a well-behaved client can sleep precisely instead of polling. Turning a rejected client from a poller into a sleeper is the single biggest load reduction available.

And jitter it before sending (d03). An un-jittered Retry-After synchronizes every rejected client to retry at the same instant — the header creates the herd it was meant to prevent.

Q60. Weighted requests — a search costs 10, a health check costs 1. What changes?

allow(key, cost) subtracts cost. One real subtlety:

A request with cost > capacity can never succeed and will spin forever. Reject it at the API boundary with a distinct error:

if cost > self.capacity:
    raise CostExceedsCapacity(cost, self.capacity)   # not a 429 -- a 400

"Never satisfiable" and "not right now" are different failures and must be different responses.

Q61. Is this limiter fair between clients?

Only if each client has its own bucket. A shared bucket is FCFS, so an aggressive client consumes the tokens and a polite one starves — exactly the noisy-neighbour problem from m01.

For fair sharing of a global capacity you need weighted fair queueing or a reserved floor per class, not a limiter. "A rate limiter enforces a contract; it does not allocate capacity" is the distinction, and it is the difference between d03 and d05.

Q62. Now make it distributed. What is the first thing you say?

"How exact does it need to be?" — because the answer selects the entire design.

• Exact → one round trip to a shared store per decision. At 1M decisions/s that is 1M round trips/s and the store is on your hottest path.
• Approximate (~1%) → lease blocks of tokens to each process and enforce locally. A lease factor of 20 is a 20× reduction in store traffic.

Leasing is the answer, and the accuracy loss is bounded by lease_size × process_count. Full treatment in d03.

Q63. The shared store goes down. Fail open or fail closed?

It depends on what the limit protects, and saying "it depends" with the fork is the answer:

• Overload protection → fail open. A limiter outage must not become a total outage.
• Billing / abuse enforcement → fail closed, or your incident becomes free unlimited usage.

And the best answer is neither: fail open to a degraded local limit derived from this process's observed share of that key's traffic — enforcement continues, approximately, without the store.

Q64. How do you test a rate limiter deterministically?

Inject the clock. Never call time.monotonic() directly:

class Bucket:
    def __init__(self, rate, capacity, clock=time.monotonic):
        self._clock = clock

# test
t = [0.0]
b = Bucket(10, 10, clock=lambda: t[0])
assert all(b.allow() for _ in range(10))
assert not b.allow()
t[0] = 0.5                    # advance exactly
assert sum(b.allow() for _ in range(10)) == 5     # exactly 5 tokens refilled

No sleep, no flakes, and the boundary cases are reachable — you can test "exactly at the refill instant", which a real clock cannot hit. Clock injection is the single highest-value testing habit in this whole track; it applies to the scheduler, the TTL cache, the WAL and the retry logic identically.

Section 6: Heaps and Deterministic Scheduling (Q65–Q76)

Pairs with WARMUP ch. 5 and job_scheduler.

Q65. Why does the heap key need four fields?

(fire_at, -priority, seq, job_id)

• fire_at — the actual ordering.
• -priority — higher priority first (negated because heapq is a min-heap).
• seq — a monotonic counter giving FIFO among equals, which is what makes the schedule deterministic.
• job_id — a final tie-break so the order never depends on insertion history.

Without seq, two jobs at the same time and priority come out in an arbitrary order that depends on heap internals — the schedule is not reproducible, and a test that passes today fails after an unrelated change.

Q66. What happens if the tuple's last element is a non-comparable object?

heapq compares tuples element-wise, so when the first three tie it compares the job objects — and if they define no ordering, TypeError, at an unpredictable moment under load.

Always terminate the key with something totally ordered (seq alone suffices, since it is unique). This is the same hazard as Q25 and it is worth noticing that it is the same hazard: tuple comparison falls through to elements you did not intend to compare.

Q67. Why -priority rather than a max-heap?

Python has no max-heap. Negation is the idiom and it is correct for integers.

Where it breaks: floats near the representable limits, and -x for unsigned/arbitrary precision is fine but -x for a string priority is a TypeError. For non-numeric priorities, map to a rank integer first. Say the mapping rather than negating something that does not negate.

Q68. Cancel a scheduled job. Removing from a heap is O(n) — what do you do?

Lazy deletion, same as Q43:

def cancel(self, job_id):
    self.cancelled.add(job_id)          # O(1)

def pop_ready(self, now):
    while self.heap and self.heap[0][0] <= now:
        fire_at, _, seq, jid = heappop(self.heap)
        if jid in self.cancelled:
            self.cancelled.discard(jid)
            continue
        return jid
    return None

And compact when dead exceed live (Q44), or a workload that schedules and cancels repeatedly grows the heap without bound.

Q69. heapq.heappop is O(log n). What is heapify, and why does it matter here?

heapify is O(n), not O(n log n) — Floyd's bottom-up construction: sift down from index n//2 - 1 to 0, and the work is Σ n/2^h · h which converges to 2n.

It matters because compaction (Q68) rebuilds the heap, and O(n) makes that amortize to O(1) per insert. If it were O(n log n) the compaction policy would need rethinking.

Q70. The scheduler sleeps until the next job. How long does it sleep?

heap[0].fire_at - now, but clamped and interruptible:

timeout = max(0, min(self.heap[0][0] - now, MAX_SLEEP)) if self.heap else MAX_SLEEP
self.wakeup.wait(timeout)                 # an Event, not time.sleep

Two things, both necessary. An interruptible wait, so scheduling a nearer job wakes the loop immediately — with time.sleep a job scheduled for 1 s from now waits behind a sleep until the previous next-job time. And a MAX_SLEEP cap, so the loop still ticks for shutdown checks and clock corrections.

Q71. A job takes 10 seconds and the next is due in 1. What happens?

With a single-threaded loop, the next job fires 9 seconds late — head-of-line blocking.

The options, and the tradeoff is the answer: run jobs on a worker pool (the scheduler only dispatches, and now you need concurrency limits), or accept lateness and measure it — a scheduling_delay histogram is the metric that makes this visible.

Never silently drop the late job. Late is a degradation; missing is a bug.

Q72. A recurring job every 60 s takes 70 s. What is the correct behaviour?

Three defensible policies, and you must pick one explicitly:

Default to skip, and emit a missed_runs counter. Silently queueing is how a slow job turns into an unbounded backlog that nobody notices until memory runs out.

Q73. fire_at uses wall-clock time and the clock jumps back an hour. What happens?

Every scheduled job appears to be an hour in the future and nothing fires until real time catches up. If the clock jumps forward, everything fires at once — a thundering herd of your own making.

The fix separates the two clocks: schedule on monotonic time internally; keep wall-clock only for the user-facing "run at 3am" semantics, and recompute the monotonic deadline when the wall clock is adjusted.

"Monotonic for durations, wall-clock for calendar" is the rule, and it generalizes far past schedulers.

Q74. How would you make the schedule reproducible in a test?

Inject the clock (Q64) and drive it manually. A virtual clock that jumps to the next event makes an eight-hour schedule testable in milliseconds:

while sched.heap:
    clock.now = sched.heap[0][0]          # jump straight to the next event
    sched.run_ready()
assert executed == expected_order          # exact, every time

A scheduler tested against a real clock is a scheduler with flaky tests, and this is the second place clock injection pays for itself.

Q75. Now distribute it. What is the hard part?

Not the heap — exactly-once dispatch. Two schedulers must not both fire the same job, and a scheduler that appears dead but is not (a GC pause, a network partition) will fire jobs while its replacement also fires them.

The answer is leases with fencing tokens: the leader holds a lease, every dispatch carries a monotonically increasing token, and the worker rejects tokens lower than the highest it has seen. A lease alone is not enough — the zombie leader's dispatch still arrives. Worked in full in d01.

Q76. What is the difference between at-least-once and exactly-once here, honestly?

Exactly-once delivery does not exist. What exists is at-least-once delivery plus idempotent execution, which is observably equivalent.

So the real question is what makes the job idempotent: a dedupe key stored transactionally with the job's side effect, or an operation that is naturally idempotent (set x = 5 rather than increment x).

"I'd do at-least-once delivery and make execution idempotent, keyed on (job_id, scheduled_time)" is the complete answer, and offering "exactly once" without that qualification is a tell.

Section 7: Streaming and Chunk Boundaries (Q77–Q86)

Pairs with WARMUP ch. 6, streaming_parser, and resumable_iterator.

Q77. Why can't you just chunk.split(delimiter)?

The delimiter can straddle a chunk boundary. \r\n arriving as ...\r at the end of one chunk and \n at the start of the next is invisible to per-chunk splitting, and the record is silently merged with the next one.

This is the defining bug of stream parsing and it is the reason the pattern exists: you need a carry buffer holding the unconsumed tail.

Q78. Write the carry-buffer loop.

def feed(self, chunk):
    self.buf += chunk
    while True:
        i = self.buf.find(self.delim)
        if i < 0:
            break
        yield self.buf[:i]
        self.buf = self.buf[i + len(self.delim):]

Two properties to state: the loop drains all complete records from one chunk (a if instead of while silently delays records until the next chunk arrives), and the buffer holds only the incomplete tail at exit.

Q79. What is the memory hazard in that loop, and how do you bound it?

An input with no delimiter grows the buffer without bound — a 10 GB line, or a malicious client sending bytes with no newline, is an OOM.

if len(self.buf) > MAX_RECORD:
    raise RecordTooLarge(len(self.buf))

Every streaming parser needs a maximum record size, and it is a security control, not a robustness nicety — this is the shape of a real class of DoS.

Q80. self.buf = self.buf[i+1:] in a loop — what is the complexity?

O(n²) for n records in one chunk: each slice copies the remaining buffer.

The fix is an index, not a slice:

start = 0
while (i := self.buf.find(self.delim, start)) >= 0:
    yield self.buf[start:i]
    start = i + len(self.delim)
self.buf = self.buf[start:]        # ONE copy at the end

One copy per chunk instead of one per record. This is a real and common performance bug, and it only appears when a chunk contains many records — which is exactly the high-throughput case.

Q81. Multi-byte delimiters and encodings — what breaks?

Decoding at chunk boundaries. A UTF-8 character can be split across chunks, so chunk.decode('utf-8') raises UnicodeDecodeError on a valid stream.

Parse in bytes, decode complete records — or use codecs.getincrementaldecoder('utf-8')(), which holds the partial character across calls. Never decode a raw chunk.

Q82. Resumable iteration: what must the checkpoint contain?

Enough to reconstruct the position and the parser state, which is more than an offset:

{"byte_offset": 8_412_990, "records_emitted": 40_112, "parser_state": "IN_QUOTED_FIELD",
 "carry": b'partial-line-so-far'}

The carry buffer is the part people forget. Resuming at a byte offset without the partial record either loses it or re-emits it. A resumable parser's state is the offset plus the buffer plus the state machine's mode.

Q83. Is your resume exactly-once, at-least-once, or at-most-once?

It depends on the order of two operations, and this is the whole question:

• Checkpoint before processing → at-most-once (a crash loses the record).
• Process before checkpointing → at-least-once (a crash reprocesses it).
• Both atomically → exactly-once, and it requires the checkpoint and the side effect to be in the same transaction.

"Process then checkpoint, and make processing idempotent" is the practical answer — the same resolution as Q76, arrived at from a different direction, which is worth noticing out loud.

Q84. The state machine has five states. How do you keep it correct?

A table, not a chain of ifs:

TRANSITIONS = {
    (S.FIELD,  ord(',')): (S.FIELD,  Action.EMIT_FIELD),
    (S.FIELD,  ord('"')): (S.QUOTED, Action.NONE),
    (S.QUOTED, ord('"')): (S.MAYBE_END_QUOTE, Action.NONE),
    ...
}

Why it is better in a round: every (state, input) pair is visible, so missing transitions are findable by inspection, and the test is "assert the table is total" — one test covering all 5 × 256 combinations instead of guessing which branches matter.

Q85. How do you test a streaming parser thoroughly?

Feed the same input at every possible chunking and assert the output is invariant:

data = b"a,b\nc,d\n"
expected = list(parse_whole(data))
for size in range(1, len(data) + 1):
    p = Parser()
    out = [r for i in range(0, len(data), size) for r in p.feed(data[i:i+size])]
    assert out == expected, f"chunk size {size} differs"
# and the pathological case:
assert [r for b in data for r in p.feed(bytes([b]))] == expected   # one byte at a time

Byte-at-a-time is the test that finds every boundary bug, and it is cheap. Say this unprompted — it is the strongest possible answer to "how would you test it".

Q86. The producer is faster than the consumer. What does your parser do?

Nothing — and that is the bug. A parser that buffers whatever it is fed converts a rate mismatch into unbounded memory.

The parser must either block (synchronous: the caller cannot feed more until records are consumed) or expose a bounded queue and let the caller handle the full condition. That is backpressure, and it belongs in the parser's contract, not in a comment. See Q119.

Section 8: Graphs, Topological Order, Cycles (Q87–Q96)

Pairs with WARMUP ch. 7 and spreadsheet_eval.

Q87. Kahn's algorithm or DFS — how do you choose?

Kahn (repeatedly remove in-degree-zero nodes) when you want level-by-level processing — everything at one level can run in parallel, which is what a build system or a scheduler needs.

DFS (post-order reversed) when you want a single ordering cheaply, or when you also need cycle paths for error messages.

"Kahn if I need parallelism levels, DFS if I need the cycle path" is the answer, and it beats naming one.

Q88. Kahn's algorithm ends with nodes remaining. What does that mean, and what do you report?

A cycle exists, and the remaining nodes are exactly those in or downstream of it.

Reporting "there is a cycle" is not enough — for a spreadsheet or a build graph the user needs the cycle. Run a DFS from a remaining node with an on-stack set; when you reach an on-stack node, the stack slice from that node is the cycle: A → B → C → A.

Q89. Explain three-colour DFS and why two colours is not enough.

• White — unvisited. Grey — on the current recursion stack. Black — fully explored.
• An edge to a grey node is a back edge = a cycle.
• An edge to a black node is fine — it is a cross or forward edge in a DAG.

With only "visited/unvisited", you cannot distinguish a back edge from a cross edge, so a diamond (A→B→D, A→C→D) is falsely reported as a cycle. The grey state is what makes it correct, and this is the single most common bug in cycle detection.

Q90. Your DFS hits RecursionError. What do you do?

Convert to an explicit stack, not raise the recursion limit — sys.setrecursionlimit risks a hard interpreter crash because the C stack is the real limit.

stack = [(node, iter(adj[node]))]
while stack:
    n, it = stack[-1]
    nxt = next(it, None)
    if nxt is None:
        stack.pop(); colour[n] = BLACK; order.append(n)
    elif colour[nxt] == WHITE:
        colour[nxt] = GREY; stack.append((nxt, iter(adj[nxt])))
    elif colour[nxt] == GREY:
        raise Cycle(...)

Keeping the iterator on the stack is the trick — it is what preserves "where we were in this node's children" across pops, and it is what makes the iterative version equivalent rather than merely similar.

Q91. A spreadsheet cell changes. Do you recompute everything?

No — only the transitive dependents, found by a forward BFS/DFS over the reverse-dependency graph, then evaluated in topological order restricted to that subgraph.

The structure this requires: you must maintain the reverse edges (who depends on me), not just the forward ones. That is a data-model decision made at the start, and retrofitting it means walking the whole graph on every change.

Q92. A cell's formula changes from =A1+B1 to =C1. What must be updated?

Remove the old edges before adding the new ones, in both directions:

for old in self.deps[cell]:
    self.rdeps[old].discard(cell)          # <-- forgetting this leaks stale dependents
self.deps[cell] = new_deps
for new in new_deps:
    self.rdeps[new].add(cell)

Forgetting the removal means A1 still thinks the cell depends on it, so changing A1 recomputes a cell that no longer references it — wasted work, and eventually a stale-edge cycle that does not exist in the real graph.

Q93. How do you make evaluation incremental and correct?

Dirty-marking plus topological evaluation:

1. On change, mark the cell and all transitive dependents dirty (reverse edges).
2. Evaluate dirty cells in topological order so each is computed after its inputs.
3. Optional: if a recomputed value is unchanged, stop propagating — early cutoff.

Early cutoff is the big win in practice (Salsa, Adapton, incremental build systems), and it requires comparing the new value to the old, which requires keeping the old. Say the requirement, not just the optimization.

Q94. Can you detect a cycle without a full traversal?

On insert, yes and cheaply: before adding edge u → v, check whether u is reachable from v. That is one DFS from v, and in a mostly-acyclic graph it terminates fast.

Better for repeated inserts: maintain a topological order incrementally (Pearce–Kelly). Adding an edge that respects the current order is O(1); one that violates it triggers a bounded reorder of only the affected region.

Naming Pearce–Kelly is a genuine differentiator — it is the right answer for an incremental system and almost nobody reaches for it.

Q95. Two independent subgraphs. How do you evaluate them in parallel?

Kahn gives you the levels for free: all nodes at in-degree zero can run concurrently; as each finishes, decrement its dependents' in-degrees and enqueue any that hit zero.

ready = deque(n for n in nodes if indeg[n] == 0)
# workers pull from `ready`; on completion, decrement dependents, push new zeros

The concurrency control that must come with it: a bounded worker pool, or a wide graph spawns thousands of tasks at once — see Q119.

Q96. Your dependency graph has a million nodes. What changes?

The adjacency representation. A dict-of-sets at a million nodes is hundreds of megabytes of Python object overhead.

Use CSR (compressed sparse row): two flat arrays, offsets[n+1] and targets[edges]. Contiguous, cache-friendly, and roughly 8 bytes per edge instead of ~100.

The tradeoff: CSR is immutable-ish — inserting an edge means rebuilding. So CSR for a static graph traversed many times; dict-of-sets for a mutating one, which is exactly the spreadsheet case.

Section 9: Write-Ahead Logs and Crash Recovery (Q97–Q108)

Pairs with WARMUP ch. 8 and wal_store.

Q97. State the write-ahead rule in one sentence.

The log record describing a change must be durable before the change itself is. That is the entire protocol; everything else is optimization.

Q98. What goes in a log record?

[ length ][ LSN ][ type ][ payload ][ CRC32 ]

• length — so a reader can frame records without parsing them.
• LSN — a dense monotonic sequence number; gaps are detectable (Q37).
• CRC32 — over the whole record, so a torn write is detectable.

The CRC is over length and LSN too. If it covered only the payload, a corrupted length field would misframe every subsequent record and the CRCs would all "pass" on garbage.

Q99. Why CRC32 and not SHA-256?

Because the threat is corruption, not tampering. Measured on this machine: CRC32 21.8 GB/s, SHA-256 2.4 GB/s — 9.2× faster, and CRC32 has hardware support on every modern CPU.

CRC32 detects all single-bit errors, all burst errors up to 32 bits, and ~99.99999998% of the rest. For an adversarial threat you need a MAC, not a hash — and if that is the requirement, say so explicitly rather than reaching for SHA-256 as if it helped.

Q100. flush() versus fsync() — quantify the difference.

flush() moves data from the Python buffer to the OS page cache — it survives a process crash and not a power loss. fsync() asks the OS to push it to the device.

Measured, 100-byte appends:

11× — and this machine understates it. On Linux with a real spinning or non-battery-backed device the ratio is 100×–1000×. The ratio is the point; the absolute is hardware.

Q101. The fsync trap that catches people on macOS.

On macOS, fsync() does not flush the drive's own write cache. It returns once the data reaches the device, which may still lose it on power failure. Real durability needs fcntl(fd, F_FULLFSYNC).

This is why the 11× above is low — the measurement is of a cheaper operation than Linux's fsync. Knowing that your durability primitive is platform-specific is exactly the kind of detail this round rewards, and it is a real bug in shipped software.

Q102. fsync per record is too slow. What do you do?

Group commit. Batch the fsyncs, not the writes:

writers append to the buffer and WAIT on a condition
one flusher: fsync once, then wake every writer whose record is now durable

N writers pay one fsync. Throughput scales with batch size while each writer's latency stays roughly one fsync — the classic latency/throughput trade where increasing the batch does not increase the latency, which is unusual and worth saying.

The tunable is the wait window: longer window, bigger batches, higher latency floor.

Q103. Recovery reads the log and hits a bad CRC in the middle. What do you do?

Stop and truncate there. Records after a bad CRC cannot be trusted — a torn write means the tail is garbage, and the framing itself may be wrong (Q98).

# Everything up to the last good record is durable; the rest never happened.
truncate(last_good_offset)

Do not skip and continue. A skipped record means a lost mutation that later records may depend on, and you will have silently applied an inconsistent prefix. "Truncate at the first bad record" is the correct and standard answer.

Q104. What is a checkpoint and what does it actually buy?

A durable snapshot of the applied state plus the LSN it reflects. It bounds recovery time: replay starts at the checkpoint LSN instead of the beginning of the log, and it lets you truncate the log below that LSN.

Without checkpoints, recovery time grows without bound with uptime — a system that has been up for a year takes a year's worth of log to recover. That is the failure people do not anticipate.

Q105. What if the crash happens during the checkpoint?

The checkpoint must be atomic, and the standard mechanism is write-then-rename:

write(tmp_path); fsync(tmp); os.rename(tmp, final); fsync(dir_fd)

rename is atomic on POSIX, so a reader sees either the old or the new checkpoint and never a partial one.

The fsync on the directory is the part everyone forgets — without it the rename itself may not be durable, so after a power loss the directory entry can still point at the old file even though the new file's data is on disk.

Q106. Replay is idempotent — why does that matter, and how do you get it?

Because recovery may run more than once (a crash during recovery), and because replay re-applies records that were already applied before the crash.

Two mechanisms: make operations idempotent by construction (set k=v rather than increment k), or record the applied LSN with the state and skip records at or below it.

LSN comparison is the general answer and it is exactly ARIES's page-LSN check.

Q107. Do you fsync the data file too, or only the log?

Only the log, on the write path — that is the entire point of write-ahead logging: turn random durable writes into one sequential durable write.

The data file is fsynced at checkpoint, after which the corresponding log prefix can be truncated. "The WAL is how you pay for durability once, sequentially, instead of per-page, randomly" is the sentence that shows you understand why WALs exist rather than what they are.

Q108. How do you test crash recovery without crashing?

Truncate the log at every possible byte offset and assert recovery succeeds:

full = open(log_path,'rb').read()
for cut in range(len(full) + 1):
    write(tmp_log, full[:cut])
    store = Store.recover(tmp_log)               # must not raise
    assert store.state in valid_states_at(cut)   # a prefix of the operations

This finds torn-record handling, framing bugs, and partial-CRC bugs exhaustively, and it runs in milliseconds. Add bit-flip injection for the CRC path — flip one bit at each offset and assert recovery either detects it or is unaffected.

Say this unprompted. Alongside Q85's byte-at-a-time chunking, it is the strongest "how would you test it" answer in the whole track.

Section 10: Dedup and Probabilistic Structures (Q109–Q118)

Pairs with WARMUP ch. 9, event_dedupe, and text_index.

Q109. Exact dedup of a billion IDs. What is the memory problem?

A Python set of a billion 16-byte IDs is well over 100 GB — the set's table plus a Python object per ID.

Three real answers: partition by hash across machines/passes (exact, more I/O); sort and scan for adjacent duplicates (exact, external, one pass after the sort); or accept approximation with a Bloom filter. State that the first two are exact and the third is not, because the interviewer is checking whether you know what you gave up.

Q110. What error does a Bloom filter make, and in which direction?

False positives only, never false negatives. "Definitely not present" or "probably present".

The direction is what makes it useful: as a negative cache in front of an expensive lookup, a false positive costs one unnecessary lookup (which then returns the truth) and a false negative would be a correctness bug. The error is in the cheap direction, which is the whole design.

Q111. Give the false-positive formula and the optimal k.

\[ p = \left(1 - e^{-kn/m}\right)^k, \qquad k_{\text{opt}} = \frac{m}{n}\ln 2 \]

Computed:

"About 10 bits per element for 1%" is the number to have memorized — it is the one that makes the sizing conversation possible without a calculator.

Q112. Why can't you delete from a Bloom filter?

Clearing a bit would also clear it for every other element that hashes to it, creating false negatives — which breaks the one guarantee the structure offers.

The alternatives: a counting Bloom filter (counters instead of bits — 4× the memory), or a cuckoo filter (stores fingerprints, supports delete, and is often smaller at low FP rates). Cuckoo filter is the modern answer and naming it is worth credit.

Q113. Your Bloom filter fills up. What do you do?

Its FP rate degrades continuously — there is no "full" and no error. That is the hazard: it quietly becomes useless.

Scalable Bloom filters: when the current filter reaches its target FP rate, add a new one with a tighter rate; query all of them. Total FP rate stays bounded by a geometric series.

And track n. A filter with no element count cannot know it is degrading, so the failure is silent. Any probabilistic structure needs its own health metric.

Q114. Deduplicating a stream with a bounded window — what exactly does "bounded" cost you?

Correctness for events displaced further than the window. An event whose duplicate arrives window + 1 positions later is not detected.

So the window must be justified by the source's reordering bound, not chosen arbitrarily: "the upstream guarantees at-most-30-second reordering, so at 1,000 events/s the window is 30,000."

A window chosen without that reasoning is a guess, and the event-dedupe gate tests exactly this: a fully shuffled stream produces gaps correctly, because the displacement exceeded the window.

Q115. MinHash — what does it estimate, and how does it save you?

Jaccard similarity, in constant space: P(minhash_A[i] == minhash_B[i]) = J(A,B).

128 permutations × 4 bytes = 512 bytes per document, regardless of the document's length, with standard error 1/√128 ≈ 8.8%. The length-independence is the point — comparing two documents becomes comparing two 512-byte signatures.

Q116. LSH banding — what do b and r actually control?

They are the similarity threshold. With b bands of r rows, the probability that two documents with Jaccard s become candidates is 1 - (1 - s^r)^b, an S-curve with its knee at:

\[ s^* \approx (1/b)^{1/r} \]

For 128 hashes as 16 bands of 8: (1/16)^(1/8) ≈ 0.71.

More bands → lower threshold → more candidates and more compute. Being able to state that relationship, and which way to move each knob, is what separates having used MinHash from having read about it. Applied at scale in m04.

Q117. When is exact dedup preferable despite the cost?

When a false positive destroys data. Deduplicating documents for a training corpus with a probabilistic filter means silently dropping unique documents — and m04's R2 shows that error can be biased, not random, which is far worse.

Rule: probabilistic when a false positive costs work; exact when it costs data.

Q118. HyperLogLog — one sentence on the mechanism and the tradeoff.

Count distinct elements in fixed space by tracking the maximum number of leading zeros in the hashes — a hash with k leading zeros suggests roughly 2^k distinct elements; averaging across registers reduces the variance.

~1.6 KB gives ~2% error for cardinalities up to billions, and it merges: the union of two HLLs is the element-wise max, which is what makes it usable in a distributed aggregation. The merge property is the part worth mentioning — it is why HLL is in every analytics system.

Section 11: Backpressure and Bounded Concurrency (Q119–Q130)

Pairs with WARMUP ch. 10, bounded_queue, and async_crawler.

Q119. What is backpressure, in one sentence?

A slow consumer's ability to make a fast producer slow down, instead of the difference accumulating in a buffer.

The corollary is the useful half: any unbounded buffer is a system with no backpressure, and it will fail as an OOM under sustained overload rather than as a visible slowdown.

Q120. asyncio.gather over 10,000 URLs. What happens?

All 10,000 coroutines are created and scheduled immediately. You open 10,000 sockets, exhaust the file-descriptor limit, and DoS the target — gather is not a concurrency limiter, it is a completion barrier.

sem = asyncio.Semaphore(20)
async def fetch(u):
    async with sem:
        return await client.get(u)
await asyncio.gather(*(fetch(u) for u in urls))

The semaphore inside the coroutine is what bounds it — the coroutine objects still all exist, but only 20 are past the acquire at once. Note carefully: the memory for 10,000 coroutines is still allocated. For truly large inputs use a worker pool over a bounded queue instead.

Q121. What is wrong with asyncio.gather(*tasks) when one task raises?

By default gather propagates the first exception immediately while the other tasks keep running — orphaned, unawaited, and their eventual exceptions surface as Task exception was never retrieved warnings, or not at all.

asyncio.TaskGroup (3.11+) is the fix: on any failure it cancels the siblings and raises an ExceptionGroup containing everything that went wrong.

async with asyncio.TaskGroup() as tg:
    for u in urls:
        tg.create_task(fetch(u))

"Use a TaskGroup" is the modern answer and knowing why — orphaning, not ergonomics — is the part being tested.

Q122. Why is asyncio.CancelledError a BaseException and not an Exception?

So that except Exception: does not swallow it. Cancellation must propagate; a broad handler that caught it would make tasks uncancellable, and wait_for would hang forever waiting for a task that already absorbed its own cancellation.

Since 3.8 it inherits from BaseException for exactly this reason. A try/except Exception around await is safe; a try/except BaseException without a re-raise is a bug.

Q123. A worker pool over a bounded queue: how do workers know when to stop?

A sentinel per worker, or an explicit close:

for _ in range(n_workers):
    await queue.put(SENTINEL)          # one per worker, so each gets exactly one

The bug worth naming: a single sentinel stops one worker and the rest block forever. And the producer must be the one to send them — a worker that produces the sentinel means an empty input produces none, and the whole pool hangs.

That exact bug is in the async-crawler gate: an empty seed list hung forever, because the stream-ending sentinel was only produced by a worker and no worker ever ran.

Q124. What is the correct queue size?

Small — usually 1–2× the worker count. A large queue does not increase throughput (the workers are the bottleneck); it only increases latency and memory, and it delays the backpressure signal.

The argument for a slightly larger one is smoothing bursts, so 2 × workers is a defensible default. Say "small, because the queue is a buffer against jitter, not a source of throughput" — people reflexively make queues big.

Q125. Queue full: block, drop, or reject?

Blocking a user-facing request is worse than rejecting it: it consumes a connection and a thread while the client times out anyway. Match the policy to who is on the other end.

Q126. Retries make it worse under load. Explain the mechanism.

Retries multiply load exactly when the system is least able to serve it. A system at capacity starts timing out; each timeout produces a retry; effective load becomes (1 + retries) × offered; more timeouts follow. Positive feedback — a metastable failure that persists after the original trigger is gone.

Three mechanisms, in this order:

1. A retry budget — retries capped at ~10% of requests, fleet-wide. Bounds the multiplier.
2. Circuit breakers — stop retrying a dependency that is failing.
3. Exponential backoff with jitter — spreads the survivors in time.

The order matters and it is the answer: backoff alone spreads the load without reducing it. The budget is what caps the multiplier.

Q127. Why jitter, specifically?

Without it, backoff synchronizes clients. Everyone fails at T, everyone retries at T+1s, everyone fails again, everyone retries at T+2s. The backoff creates the herd it was meant to prevent.

Full jitter is the right default:

sleep = random.uniform(0, min(cap, base * 2 ** attempt))

Not base * 2**attempt * random.uniform(0.5, 1.5) — AWS's measurements show full jitter (uniform over the whole interval) beats partial jitter on both completion time and server load.

Q128. What breaks a circuit breaker's half-open state?

Letting more than a trickle through. Half-open should admit one probe. Admitting the full flow the instant the timer expires re-overloads a recovering dependency and it trips again — oscillation.

And the second half: on success, ramp gradually (10% → 50% → 100%), not straight to full. A recovering service has cold caches and empty connection pools; full traffic knocks it straight back down.

Q129. ThreadPoolExecutor versus asyncio — how do you choose?

By what blocks. asyncio for I/O with async libraries; threads for blocking I/O with no async equivalent (most database drivers, requests); processes for CPU work.

The trap: one blocking call inside a coroutine stalls the entire event loop, not just that task — so a single synchronous requests.get in an async service serializes everything. loop.run_in_executor (or asyncio.to_thread) is the bridge.

Q130. How do you test that a bounded queue actually applies backpressure?

Assert the producer blocks, with a fake consumer that never consumes:

q = BoundedQueue(maxsize=2)
q.put(1); q.put(2)                                    # fills it
t = threading.Thread(target=lambda: q.put(3)); t.start()
t.join(timeout=0.1)
assert t.is_alive(), "put() should have blocked -- no backpressure"
q.get()                                                # make room
t.join(timeout=1); assert not t.is_alive()             # now it completes

Asserting the thread is still alive is the test — it proves blocking rather than assuming it. Most people test that the queue holds two items, which is a capacity test, not a backpressure test.

Section 12: "How Would You Test This?" (Q131–Q140)

Q131. What is the single best answer to "how would you test this?"

Name a specific technique that matches the structure, not a category:

• Stream parser → every chunk size, including byte-at-a-time (Q85).
• Crash recovery → truncate at every offset (Q108).
• Undo/redo → property-based against a naive model (Q38).
• Rate limiter / scheduler → injected clock, exact boundaries (Q64, Q74).
• Bounded queue → assert the producer blocks (Q130).

"Unit tests, integration tests, and edge cases" is the answer that scores zero. Everyone says it, it applies to everything, and it demonstrates nothing.

Q132. What is property-based testing and when is it worth it?

Generate random inputs and assert invariants rather than specific outputs. Worth it when the invariant is easy to state and the correct output is hard to enumerate:

@given(st.lists(st.integers()))
def test_roundtrip(ops):
    assert decode(encode(ops)) == ops

The high-value part is shrinking: on failure, Hypothesis minimizes the input to the smallest one that still fails — turning "it broke on this 200-element list" into "it breaks on [0, 0]". Shrinking is why property tests are worth the setup, and it is the part to mention.

Q133. Give three invariants worth asserting in a stateful system.

1. Conservation — nothing appears or disappears. items_in == items_out + items_held.
2. Monotonicity — sequence numbers only increase; a cache's size never exceeds its cap.
3. Round-trip — decode(encode(x)) == x; undo(do(x)) == x.

All three are checkable after every operation in a random sequence, which is what makes a model-based test far stronger than example tests: the assertion runs thousands of times in states nobody thought to write down.

Q134. How do you test something time-dependent without sleep?

Inject the clock (Q64) and drive it explicitly. sleep in tests means slow tests, flaky tests, and — worst — untestable boundaries: you cannot land exactly on the refill instant with a real clock, and that instant is where the off-by-one lives.

If you cannot inject (third-party code), freezegun or unittest.mock.patch('time.monotonic'). But injection as a constructor parameter is better design, because it makes the dependency visible in the signature.

Q135. How do you test concurrent code deterministically?

Mostly: do not test concurrency, test the state machine. Extract the logic so it is single-threaded and testable, and keep the concurrency layer thin enough to inspect.

For the concurrency itself, in order of value:

• Stress with assertions — run N threads and assert an invariant afterwards. Finds races probabilistically.
• Deterministic interleaving — inject a scheduler hook and force specific orders.
• ThreadSanitizer/helgrind for native code; for Python, a stress test plus the GIL caveat from Q57.

"Make the concurrent surface small enough to reason about" is the honest lead — it is what experienced people actually do.

Q136. What is a flaky test, and what causes them here?

A test that fails non-deterministically. Causes, in the order they occur in this material:

1. Real time — sleep, timeouts, "should finish within 100 ms" (Q134).
2. Ordering assumptions — asserting on a set/dict iteration order, or on which of two equal items comes first (Q65 — this is why seq exists).
3. Shared state between tests — a module-level cache not reset.
4. Real network / filesystem — anything external.

A flaky test is worse than no test, because it trains the team to ignore red. Fix or delete; never retry.

Q137. How do you test the error path?

Inject the failure. A dependency that never fails in tests means the error path is never executed:

class FlakyStore:
    def __init__(self, real, fail_on): ...
    def get(self, k):
        if self.calls in self.fail_on: raise ConnectionError
        return self.real.get(k)

And fuzz the failure point: fail on call 1, then 2, then 3, and assert the system is consistent each time. This is the same shape as Q108's truncate-at-every-offset — enumerate the failure position rather than picking one.

Q138. What is a golden/snapshot test and when is it a mistake?

Comparing output against a stored expected file. Good for: complex structured output where writing assertions by hand is impractical (a parse tree, a rendered report).

A mistake when the output changes for legitimate reasons often — then the test becomes "run with --update and commit", which asserts nothing. A snapshot test that is regularly regenerated without being read is a test that only detects that code ran.

Q139. What do you do when a test is hard to write?

Treat it as a design signal, not a testing problem. Hard-to-test almost always means:

• Hidden dependencies — time, random, network, filesystem reached for directly. → inject.
• Too much in one unit — a function that parses, validates, computes and persists. → split.
• Global state — module-level singletons. → pass explicitly.

"The test is hard because the design has an implicit dependency; I'd make it explicit" is a much stronger answer than a clever mock, and it is the answer a staff-level interviewer is listening for.

Q140. You have ten minutes left and no tests. What do you write?

One test per failure mode you can name, cheapest first, and say the order out loud:

1. The happy path — proves it runs at all.
2. The empty input — the single most common crash (heap[0] on an empty heap, versions[-1] on an empty list, an empty seed list hanging the crawler).
3. The boundary you know is subtle — the exact-version lookup, the delimiter straddling a chunk.
4. The one that would have caught the bug you almost wrote.

Naming the order and the reason for it is worth more than writing four more tests, because it shows the tests are chosen rather than accumulated.

Section 13: "Now Make It Concurrent" (Q141–Q150)

Q141. The interviewer says "now make it thread-safe." What is your first move?

Ask what the concurrency actually is — multiple readers, multiple writers, or both — because the answer changes the mechanism entirely:

• Read-mostly → a read-write lock, or copy-on-write with an atomic pointer swap.
• Write-heavy → sharded locks (lock per bucket), or a single-writer design with a queue.
• Both, low contention → one lock. Start here and optimize only under measurement.

"One lock, and here is how I'd shard it if profiling said to" is a better answer than a lock-free structure you cannot prove correct.

Q142. Where exactly does the lock go in an LRU cache?

Around the whole get, not just the dict access — because get mutates (it promotes the entry to the front). That surprises people: a read operation on an LRU is a write.

def get(self, k):
    with self._lock:                # the promote is a mutation
        node = self._map.get(k)
        if node is None: return None
        self._move_to_front(node)
        return node.value

"An LRU has no read-only operations" is the observation being tested, and it is why an RWLock buys nothing here.

Q143. Sharded locks: how many shards, and what breaks?

Rule of thumb: 4–8× the core count, so contention is unlikely but memory overhead stays small. Shard by hash(key) % n_shards.

What breaks: any operation spanning shards. len() is now approximate or requires all locks; an atomic multi-key update requires locking several shards, in a consistent order, or you have a deadlock.

"Lock ordering" is the answer to the deadlock, and stating it before being asked is the signal.

Q144. Two threads must lock A and B. How do you guarantee no deadlock?

A total order on locks, always acquired in that order. id(), or an explicit rank:

first, second = sorted((lock_a, lock_b), key=id)
with first, second: ...

Deadlock requires a cycle in the wait-for graph; a total order makes cycles impossible. That is the same argument used to fix m03's gang-scheduling reservation — worth noticing that a lock-ordering rule and a resource-reservation rule are the same theorem.

Q145. Is dict[k] += 1 atomic in CPython?

Not by specification, and the measurement is misleading. On 3.13, four threads each doing 100,000 increments lost zero updates — because since 3.10 the eval breaker is checked only at backward jumps and calls, so the whole read-modify-write completes inside one loop iteration.

That is an implementation detail, not a guarantee. It differs by Python version, by whether the operand's __add__ is Python-level, and it disappears under free-threading (PEP 703/779, Phase II in 3.14).

d.append(x) on a deque genuinely is atomic (a single C call). Rely on documented atomicity or a lock — never on the GIL's current scheduling.

Q146. queue.Queue versus asyncio.Queue versus multiprocessing.Queue — one line each.

• queue.Queue — threads, locks and condition variables, blocking put/get.
• asyncio.Queue — one event loop, not thread-safe; await, no blocking.
• multiprocessing.Queue — processes, pickles everything through a pipe. Slow for large objects and it silently fails on unpicklable ones.

The trap: using queue.Queue from a coroutine blocks the entire event loop. Use asyncio.Queue, or asyncio.to_thread around the blocking call.

Q147. What is the difference between a lock and a semaphore, mechanically?

A lock is mutual exclusion — one holder, and (by convention) the holder releases it. A semaphore is a counter of permits — N holders, and any thread may release.

The consequence that matters: a semaphore is the right tool for bounding concurrency (Q120), and a lock is the right tool for protecting state. Using a lock to limit concurrency to one when you meant to allow ten is a real and common confusion.

Q148. Your code works with the GIL. What breaks under free-threading (3.13t / 3.14)?

Every place that relied on the GIL for implicit atomicity — exactly Q145. Read-modify-write on shared containers can now genuinely interleave.

Also: C extensions not built for free-threading, and performance assumptions (uncontended atomics have a cost; single-threaded code can be measurably slower).

The answer that lands: "Anywhere I depended on the GIL rather than a lock. The migration is to audit every shared mutable and either lock it or make it thread-local — and the code was already incorrect by specification, the GIL was just hiding it."

Q149. How do you make a counter fast under contention?

Do not share it. Per-thread (or per-shard) counters summed on read:

class ShardedCounter:
    def __init__(self, n=64): self._c = [0] * n
    def inc(self, tid):       self._c[tid % len(self._c)] += 1
    def value(self):          return sum(self._c)     # approximate while writing

Trade an exact instantaneous read for contention-free writes. This is LongAdder in Java, and per-CPU counters in the kernel.

Pad to cache lines if it is a real hot path — otherwise adjacent counters share a cache line and you get false sharing, which is contention you cannot see in the code.

Q150. "Now make it distributed" — what is the single most important thing to say first?

"What consistency does this actually need?" — because the answer determines everything after it, and giving a design before asking is the most common way to answer the wrong question.

Then the ladder, and knowing it is the point:

And the one primitive that keeps recurring: if a leader or a lock is involved, you need fencing tokens — a lease alone does not prevent a paused-then-resumed holder from acting. d11 is that in full, and it is the highest-value single concept in the distributed half of this program.

The Twenty That Matter Most

If you only drill twenty, drill these. They are the ones that recur across problems, and each answers a question you will be asked.

References

• WARMUP.md — the ten patterns, from zero, with complete implementations
• README.md — Track A drills, the harness, the rubric
• harness/problems/ — the 15 timed problems these questions attach to
• ../python-internals/QUIZBANK.md — 150 questions on the runtime beneath all of this
• ../systems-design/designs/README.md — where Q28, Q62, Q75 and Q150 lead
• ../ml-infra/designs/README.md — the same primitives on a bandwidth-bound substrate
• ../../CHEATSHEET.md#2-coding--representation-first — the dense version for the morning of a round
• Bloch, J. Effective Java, 3rd ed. — items on concurrency and lazy initialization; the reasoning transfers
• Kleppmann, M. Designing Data-Intensive Applications, 2nd ed. — ch. 3 (LSM/WAL), ch. 8 (clocks), ch. 11 (streams)
• Mohan, C. et al. ARIES: A Transaction Recovery Method. TODS 1992 — redo-then-undo, page LSNs (Q106)
• Amazon Builders' Library. Timeouts, retries, and backoff with jitter — the full-jitter result in Q127
• Bronson, N. et al. Metastable Failures in Distributed Systems. HotOS 2021 — the retry feedback loop in Q126
• Hypothesis documentation — property-based testing and shrinking (Q132)