TL;DR: Keep, per key, an ascending list of the versions at which it was written and a parallel list of the values. A read at version v binary-searches for the largest recorded version less than or equal to v and returns the corresponding value. Writes append, which is O(1) amortized, and reads are O(log k) in the number of writes to that key. A global counter assigns versions so that ordering across keys is well defined. Three read cases decide whether the design is right. A version before the key's first write must raise rather than return a default, since "did not exist" and "was empty" are different. A deleted key needs a tombstone value rather than removal from the structure, because the history before the delete must remain readable. And a read at a version where some other key was written must return this key's value as of that moment, which the per-key list gets right automatically and a global snapshot list would get wrong or expensive.
How to approach it
State the structure in one sentence, because it is simple and the interview is about the cases rather than the cleverness. Then walk the three read cases, since each one distinguishes a correct implementation from a plausible one. Give the code and its output. Close with what changes at scale, which is compaction, because an append-only structure grows forever.
A strong answer
A typical situation: an implementation stores one global list of snapshots, each a full copy of the map. Reads are trivial and correct. Memory is the number of writes times the size of the whole map, so a store with 10,000 keys and 100,000 writes holds a billion entries instead of 100,000.
The structure:
per key: versions[] ascending, the global version at each write
values[] parallel, the value written at that version
global: a monotonically increasing counter, incremented per write
read(key, v)
binary search versions for the rightmost entry <= v
index < 0 means the key did not exist at v -> raise
value is a tombstone -> the key was deleted at that version -> raise
otherwise return values[index]
why per key rather than global snapshots
memory: O(total writes) rather than O(writes x keys)
a write touches one key's lists, so writes stay O(1)
a read touches one key's lists, so reads are O(log k) in that key's write count and are
unaffected by how many other keys exist or how often they change
import bisect, threading
_TOMBSTONE = object()
class VersionedStore:
def __init__(self):
self._data = {} # key -> (versions list, values list)
self._version = 0
self._lock = threading.Lock()
def put(self, key, value) -> int:
with self._lock:
self._version += 1
versions, values = self._data.setdefault(key, ([], []))
versions.append(self._version) # appended in ascending order by construction
values.append(value)
return self._version
def delete(self, key) -> int:
return self.put(key, _TOMBSTONE) # a delete is a write, not a removal
def get(self, key, version=None):
with self._lock:
if key not in self._data:
raise KeyError(key)
versions, values = self._data[key]
v = self._version if version is None else version
i = bisect.bisect_right(versions, v) - 1
if i < 0:
raise KeyError(f"{key!r} did not exist at version {v}")
value = values[i]
if value is _TOMBSTONE:
raise KeyError(f"{key!r} deleted at version {versions[i]}")
return value
Running it:
put a=1 -> v1; a=2 -> v2; b=x -> v3; a=3 -> v4
get('a') = 3 latest
get('a', 1) = 1
get('a', 2) = 2
get('a', 3) = 2 b's write at v3 did not change a
get('b', 1) raises: "'b' did not exist at version 1"
after delete('a') at v5:
get('a') raises: "'a' deleted at version 5"
get('a', 4) = 3 history before the delete is still readable
The three cases, and why each matters:
1. a version before the key's first write
bisect returns index 0, minus 1 gives -1, which is the signal
must raise rather than return None or a default, because a caller asking "what was the
value at v" needs to distinguish "nothing was there" from "the value was None"
an implementation that clamps to the first version silently invents history
2. a deleted key
removing the key from the map would delete its history too, so a read at an earlier
version would fail incorrectly
a tombstone is a write like any other: it takes a version, it appears in the list, and
reads before it are unaffected
this is the same reason distributed stores use tombstones rather than removal
3. a version at which some other key was written
the per-key list makes this automatic: a's list contains only a's writes, and a binary
search for v3 in [1, 2, 4] lands on 2
a global snapshot design has to decide what to store for keys that did not change, and
both answers (copy everything, or store deltas and walk backward) are worse
The Practical Coding Screen Playbook covers the habit of enumerating cases like these before writing, which is what this problem rewards. The same version-per-write structure appears in Interval Merging and Utilization Logs, where an event log is reconstructed into state at a point in time.
Complexity, and what changes at scale:
put O(1) amortized, one append to each of two lists
get O(log k) where k is the number of writes to that key
memory O(total writes), plus per-key list overhead
what breaks at scale
the structure is append-only, so a key written a million times holds a million entries
even though only the recent ones are ever read
compaction, which is the follow-up
keep a watermark: the oldest version any reader may still ask for
for each key, drop entries whose next entry is also at or below the watermark, since a read
at or above the watermark would never select them
a tombstone below the watermark can drop the key entirely
this is exactly what a multi-version storage engine does, and the watermark comes from the
oldest open transaction or snapshot
sanity: without compaction the store is a log that grows forever, which is fine for an
interview and not for a service, so saying it unprompted is worth more than the
implementation
The reversal condition: this design assumes reads are mostly at the latest version, with occasional historical reads. If most reads are historical and spread across the version range, the binary search per read is still fine but the memory is dominated by history that is actually needed, and compaction cannot help. If instead reads are only ever at the latest version, the whole structure is unnecessary and a plain map is correct, so the first question to ask is whether historical reads are a requirement or an assumption.
What interviewers probe next
- "How would you support range scans at a version?" Keep the keys in a sorted structure and, for each key in range, do the same per-key binary search. The cost is the number of keys in range times log of their write counts.
- "What about concurrent readers and writers?" A single lock is correct and coarse; because the lists are append-only and versions are assigned under the lock, readers can safely read without it if the language guarantees the list append is visible atomically, which is the multi-version idea in miniature.
- "Why a global counter rather than timestamps?" A counter is exact and monotonic. Timestamps have clock skew, and two writes in the same millisecond become ambiguous.
- "How do you know the watermark?" The oldest version any open reader might request, tracked as readers register and release, which is the same bookkeeping a database does for snapshot isolation.
Common mistakes
- Storing a full snapshot per version, which is writes times keys in memory.
- Removing the key on delete, which destroys history that earlier reads still need.
- Returning a default for a version before the key existed, which invents history.
- Never mentioning compaction, leaving an append-only structure that grows without bound.
Key takeaways
- Per key: an ascending version list and a parallel value list; reads binary-search for the rightmost version at or below the requested one.
- put is O(1), get is O(log k) in that key's write count, memory is O(total writes) rather than writes times keys.
- Three cases: before the first write raises, a delete is a tombstone rather than a removal, and another key's write is invisible by construction.
- Compaction needs a watermark from the oldest reader, or the store is a log that grows forever.