versioned-kv — 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 Two Decisions
- Failure Modes
- The Narration Script
- Follow-Ups To Expect
- The Distributed Counterpart
Why This Problem
Row 7 of source-report.md: the reported technical
screen's coding round was a versioned key-value store. It is also the single
most-corroborated OpenAI coding problem across independent sources — "time-based key-value
store with versioning" appears in essentially every aggregated list.
If you practise one problem in this track, practise this one.
What Weak, Median, and Strong Look Like
| Behavior | Result | |
|---|---|---|
| Weak | dict[key][version] = value. Gate 1 passes because tests read at versions that exist. Gate 2's "read as of a version with no write to this key" fails, because a hash map cannot answer largest version ≤ v. Rewrites | 1–2 gates |
| Median | Per-key list of (version, value) with a linear scan. Passes gates 1–3. Mentions bisect but does not implement it. Gate 4's transaction validation is attempted and half-lands | 3 gates |
| Strong | Per-key sorted list plus bisect from the start, because "as of version v" is a predecessor query and predecessor queries want ordered structures. States the complexity unprompted. Delete as a tombstone without being told. Gate 4 is thirty lines | 4 gates |
The tell that separates strong from median is at minute one: strong candidates hear "the value as of version v" and immediately say "that's a predecessor query, so I want an ordered structure, not a hash map." That single sentence determines whether gate 2 is additive or a rewrite.
The Two Decisions
1. Delete is a write, not a removal.
A tombstone. Removing the key would destroy the ability to read at an earlier version, which
is the entire product. This is also why delete() on a key that never existed still consumes
a version: versions describe the log, not the data. If deletes of absent keys were free,
two clients could disagree about what "as of version N" means.
2. Versions are global, not per key.
This is what makes a snapshot a single integer, and it is what makes cross-key transactions possible at all. Per-key versions would force a vector clock to express "read everything as of now," and every subsequent gate gets harder. Choosing global versioning at gate 1 is the decision that pays for gates 3 and 4.
Together these give you MVCC. Gate 4 layers optimistic concurrency control on top — read at a pinned version, track the read set, validate at commit — which yields snapshot isolation.
Failure Modes
| Failure | Symptom | Root cause |
|---|---|---|
| Hash map keyed by version | Gate 2 fails on "read at a version with no write to this key" | As of is a predecessor query |
| Delete removes the key | Gate 2 fails: an earlier read returns None | Delete must be a tombstone |
| Delete of an absent key is a no-op | Gate 2's version-monotonicity assertion fails | Versions describe the log |
| Per-key version counters | Gate 3 breaks: a snapshot is no longer one integer | Versions must be global |
| Linear scan instead of bisect | Passes every test, fails the interview | Interviewer asks the complexity; O(n) per read on deep history is not a store |
compact() drops a snapshot's version | Gate 3's live-snapshot case fails | Compaction must retain the entry visible from every live pin, not just the latest |
| Transaction writes get separate versions | Gate 4's atomicity assertion fails | One version per commit, or readers observe half a transaction |
| Conflict check on the write set | Gate 4's blind-write case fails | Snapshot isolation validates the read set; blind writes do not conflict |
| Conflicted transaction leaves partial writes | Gate 4's "applies nothing" assertion fails | Validate everything before applying anything |
The Narration Script
- Restate. "A key-value store where every write gets a version, and I can read the state as of any past version."
- Clarify. "Are versions global or per key? Do I need reads at arbitrary versions or only at ones that exist? Is history bounded?" (The global-vs-per-key question is the whole design; ask it in the first ninety seconds.)
- Approach. "Per key, an append-only list of
(version, value)sorted by version. Reading as of v is a predecessor query, so bisect." - Complexity. "Put O(1), get O(log n) in the number of writes to that key, memory O(total writes) — which is why compaction shows up eventually."
- Test the invariant first. Assert that reading at a version between two writes returns the earlier one. That is the invariant everything else rests on.
- Then code.
Follow-Ups To Expect
- "What's the complexity of
getat a version?" O(log n) in writes to that key. If you scanned linearly, this is where it costs you. - "Memory grows without bound. What now?" Compaction (gate 3), plus a retention policy — time-based, count-based, or pinned-by-reader. Say which and why.
- "Two transactions, both read A and write B. Both commit. Problem?" Write skew —
the anomaly snapshot isolation permits. Neither transaction's read set was written, so
neither conflicts, yet a cross-key invariant can be violated. Naming write skew unprompted
is a strong staff signal. The fix is serializable isolation: SSI, or promoting the read to
a write (
SELECT ... FOR UPDATE). - "How would you make
keys()fast?" It is O(total keys) as written. Maintain a secondary structure — a per-version live-key delta, or a skip list ordered by key with version chains. - "Make it durable." A write-ahead log; the in-memory structure becomes a cache
rebuilt on replay. See the
wal-storeproblem in this catalog. - "Make it concurrent." Readers never block under MVCC — that is the point. Writers need a lock on the version counter, or a CAS loop. Note that the version counter is now the throughput ceiling, and sharding it costs you the global ordering you built the design on.
The Distributed Counterpart
Row 8 of the source report pairs this coding question with a distributed systems design
round. Track C's design exercise d02-distributed-kv is the natural companion: take
everything here and add replication, and watch which decisions survive.
The interesting collisions:
- Global versions need a global sequencer. That is a consensus problem — Raft, or a timestamp oracle like Percolator's, or hybrid logical clocks if you will accept bounded staleness.
- Snapshots across shards need a consistent cut, which is why Spanner needs TrueTime and why everyone without an atomic clock uses HLCs and accepts a staleness bound.
- Compaction becomes distributed garbage collection. You cannot drop a version until every replica agrees no reader can see it.
Being able to say "here is my single-node design, and here is exactly which decision breaks when I distribute it" is the connection between the two rounds — and it is the kind of answer that makes an interviewer's notes read strong hire rather than hire.