TL;DR: Keep each key's values alongside the increasing versions at which they were written. A historical read finds the last version at or before the requested one by binary search; deletion appends a tombstone so earlier values remain readable.
How to approach it
Start with the per-key history, then trace a read before the first write, a read after deletion and a read at a version that changed another key. These cases explain why the binary search uses the rightmost version less than or equal to the requested version. Discuss synchronization and retention once the basic behavior is clear.
A strong answer
Copying the entire map after every write would make historical reads simple, but it duplicates unchanged values. If a map already contains 10,000 keys and retains 100,000 full snapshots, those snapshots contain a billion key entries. Recording only each changed key's new value requires 100,000 additional history entries, plus its initial state and data-structure overhead.
Store two parallel lists for each key: increasing versions and their values. A global counter assigns a new version to every write. A read uses binary search to find the rightmost version at or below the requested one. If none exists, the key had not been created; if that entry is a tombstone, the key was deleted.
The example assumes immutable values. Mutable objects would need copying or an explicit ownership rule, otherwise changing an object could alter later historical reads. A request for a future version returns the latest known value; it does not wait for that version to exist.
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
Before the first write, bisect_right returns zero. Subtracting one gives −1, which the implementation checks before indexing. Returning the first value instead would invent a value before the key existed. Raising also distinguishes absence from a stored None.
Deletion appends a tombstone rather than removing the lists. Reads before the deletion still find their earlier values. A later write can recreate the key without losing that history.
Writes to other keys do not need entries in this key's lists. In the example, a read of a at version 3 finds its version-2 value because only b changed at version 3. This is why per-key histories are a useful fit for point reads.
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.
A write appends to two lists, taking O(1) amortized time. A read takes O(log k), where k is the number of writes to that key. Memory grows with the total retained writes rather than the number of full-map snapshots.
Retention eventually matters. Set a watermark for the oldest version readers are still allowed to request. For each key, keep the newest entry at or before that watermark and every newer entry. Earlier entries cannot affect an allowed read. If the retained anchor is a tombstone, an explicit absence policy may allow omitting it, but later writes that recreate the key must remain.
The watermark can come from registered snapshots or a declared history-retention window. The example does not implement compaction; adding it also requires rejecting reads older than the retained history instead of returning misleading results.
| Requested version | Result |
|---|---|
| Before the key's first write | Not found |
| Exactly at a write | That write's value |
| Between writes | The preceding value |
| At or after a deletion, before recreation | Not found |
The same structure supports both frequent and 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?" Keep the lock in this implementation. A write changes the counter and two lists, so atomic append alone cannot give readers a consistent view. Lock-free reads need a separate publication and memory-safety design.
- "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.