token-stream-differ — Commentary
Read after you have run it under the clock. Reference implementation:
solution.py.
Table of Contents
- Why This Problem
- What Weak, Median, and Strong Look Like
- The Representation That Survives
- Failure Modes
- The Narration Script
- Follow-Ups To Expect
Why This Problem
Rows 17–21 of source-report.md describe the reported
onsite Coding 1 round: a progressive multi-part format, each stage gated on the previous one
working, with the specific example being a token-level streaming differ tracking state
changes with rollback. This is that problem.
It is also the best available training instrument for the format itself, because its gates are honestly constructed: gate 1 admits a locally-reasonable design that dies at gate 3, and gate 3 admits a second locally-reasonable design that dies at gate 4's memory bound. There is no way to pass all four by luck.
What Weak, Median, and Strong Look Like
| Behavior | Result | |
|---|---|---|
| Weak | Cursor only. Gates 1–2 in ~18 min. Gate 3 needs the event log unwound, discovers there is no record of how many events each feed produced, and rewrites the core loop with 15 min left | 2 gates |
| Median | Cursor plus a full state snapshot per checkpoint. Gate 3 passes around minute 30. Gate 4's undo needs per-feed granularity, and there are thousands of feeds per checkpoint, so the snapshot approach fails the memory bound. Out of time | 3 gates |
| Strong | Records (cursor_before, n_events, token) per feed from gate 1 — not because gate 4 is visible, but because "how much did this call change" is the obvious thing to record about an incremental algorithm. Gate 3 becomes "remember three list lengths." Gate 4 becomes "pop the delta." | 4 gates |
The gap between median and strong is roughly forty lines of code and one design instinct.
The Representation That Survives
Per feed, store a delta, not a state:
history[i] = (cursor_before, n_events_emitted, token)
Three machine words. Everything follows:
| Operation | Implementation | Cost |
|---|---|---|
undo | pop the entry, truncate events by n_events, restore cursor | O(events removed) |
redo | re-apply the recorded token through the same code path as feed | O(1) amortized |
checkpoint | remember (len(events), cursor, len(history)) | O(1) |
rollback | truncate all three to the remembered lengths | O(removed) |
The generalizable rule — and this is the transferable lesson, not the problem itself:
When a stateful component might grow undo-like requirements, store the delta, not the state. Deltas compose; snapshots do not.
Checkpoints are then just positions in the delta log, which is why gate 3 collapses to three integers. A snapshot design forces you to choose a granularity up front, and gate 4 changes the granularity underneath you.
You cannot see gate 4 while writing gate 1. But you can ask: "if this needed to be reversible, what would break first?" The answer picks the representation.
Failure Modes
| Failure | Symptom | Root cause |
|---|---|---|
| Rewrite at gate 3 | 20 minutes lost | Recorded only the cursor, not the per-feed event count |
| Fails the memory bound | Gate 4 correctness passes, allocation assertion fails | Snapshotting per feed — O(feeds × events) |
| Off-by-one in the lookahead window | Gate 2 fails on the window-boundary case | The window is (cursor, cursor+lookahead] — exclusive at the left, inclusive at the right |
| Picks the farthest match | Gate 2's "smallest j" case fails | Scan forward and return the first hit; do not scan the whole window |
| Redo survives a new feed | Gate 4's branch-discard case fails | feed() must clear the redo stack; redo() must not |
close() not idempotent | Gate 1 fails on the second close() | Guard on the closed flag and return [] |
Failed undo(n) leaves partial state | Gate 4's bounds case fails | Validate n before mutating anything |
| Checkpoints survive a rollback past them | Gate 3's invalidation case fails | Rolling back to label L must drop every label created after L |
The Narration Script
Every problem in this track has one. Say it out loud; do not think it.
- Restate. "Tokens arrive one at a time, I diff each against a baseline incrementally, and I emit edit events as I go. I never see the whole new stream."
- Clarify. "Can the stream skip baseline tokens, or only insert? Is the baseline immutable? Do you want events returned per call or accumulated?" (The skip question is the one that matters — it is gate 2, and asking it early means gate 2 is not a surprise.)
- Approach. "A cursor into the baseline. Match at the cursor is a keep and advances it; anything else is an insert. I'll record what each feed did so I can unwind it later."
- Complexity. "O(1) per token for gate 1. With lookahead it's O(w) per token, w bounded, so still O(1) amortized. Memory is O(events + feeds)."
- Test the invariant first. Before implementing, write the assertion that the cursor only advances on a keep. That is the invariant every later gate depends on.
- Then code.
Note step 3's last sentence. Saying "I'll record what each feed did so I can unwind it later" out loud at minute two is what buys you gate 4 at minute forty — and it costs eight words.
Follow-Ups To Expect
Beyond the four gates, an interviewer with time left will ask:
- "What if the baseline is 10 GB and doesn't fit in memory?" The cursor becomes a file offset; the lookahead window becomes a bounded read-ahead buffer. Note that the window is what makes this possible at all — a real edit-distance algorithm needs random access.
- "Why a window instead of proper diff?" Myers diff is O(ND) and needs the whole input. This is streaming: you must emit before you have seen the end. The window is the price of being online, and the cost is that a skip longer than the window is misreported as an insert plus trailing deletes. That is a stated, bounded inaccuracy — say so.
- "How would you make this concurrent?" You would not, directly — the cursor is sequential state. You would shard by document and keep one differ per stream.
- "What's the memory ceiling with 100M tokens?" Events dominate. Cap the log and spill, or emit events to a consumer rather than accumulating them — which changes the API and is the correct answer.
- "What breaks if the baseline changes mid-stream?" Everything. Every recorded delta references baseline positions. You would need to version the baseline and invalidate.