Coding Interview: Implement a Time-Versioned Key-Value Store

Prompt and scope

Implement an in-memory structure with set(key, value, timestamp) and get(key, timestamp). get returns the newest version for that key whose timestamp is at most the query time; it returns an explicit miss when none exists. Clarify whether timestamps are monotonic per key, whether equal timestamps overwrite, whether reads and writes are concurrent, and whether deletion or persistence is required. The core is maintaining a per-key history invariant, not repeatedly sorting and scanning every record.

What the interviewer evaluates

A strong answer targets O(log m) lookup, where m is the number of versions for the key, and explains the write trade-off between append-only and out-of-order input. The interviewer will probe empty keys, both time boundaries, duplicate timestamps, null values, unknown keys, and the difference between the latest effective version and a version after the query time. A thread-safety claim must include lock granularity and snapshot semantics.

Clarifying questions before coding

1. Are timestamps monotonic per key? If yes, append and use a short reverse scan or binary search; if no, preserve order or reject out-of-order writes.
2. What do equal timestamps mean? For last-write-wins, keep a monotonically increasing sequence as a stable tie-breaker; otherwise reject conflicts.
3. Can values be null? If so, a miss cannot also be represented by null; return a result with an explicit found flag.
4. Is concurrency required? Finish the single-threaded invariant first, then define visibility and choose per-key locks or immutable snapshots.
5. Is history unbounded? A retention window or version cap changes eviction and the meaning of an old query.

30-second answer framework

“I store a time-sorted version array for each key. get uses upper_bound(timestamp) to find the first version greater than the query and returns the previous entry, so lookup is O(log m). If writes are not monotonic, I use ordered insertion and call out its cost; if write throughput dominates, I append to a log and build an index in batches. A sequence number makes equal timestamps deterministic, and misses have an explicit state. I test empty keys, boundaries, out-of-order writes, and duplicate timestamps.”

Step-by-step solution

Represent each record as (timestamp, sequence, value) and keep each key’s array nondecreasing by (timestamp, sequence). For get(k, t), find the first position i with timestamp > t. If i is zero there is no effective version; otherwise return records[i - 1]. This upper-bound rule includes a write exactly at t.

When timestamps are monotonic per key, append gives amortized O(1) set and O(log m) get. With out-of-order timestamps, locating the insertion point is logarithmic but shifting an array is O(m) in the worst case. A balanced tree avoids shifting at the cost of more allocation and pointer overhead. A single global sorted array is incorrect because query boundaries are independent per key.

Duplicate timestamps need a deterministic rule. For last-write-wins, assign each call an increasing sequence and sort by (timestamp, sequence); the upper bound compares only timestamp, so the last record at that timestamp wins. If timestamps can exceed the language’s safe integer range, use a suitable integer type or comparator instead of silently converting to floating point.

For concurrency, the smallest extension locks one key while replacing its array or running a binary search. To keep reads non-blocking, a writer can build a new immutable array and atomically replace the reference; readers see either the old or new snapshot, never a partial array. Persistence adds a log, checksum, and recovery cursor and should be discussed only if the interviewer expands the scope.

High-quality sample answer

“I’ll assume timestamps may arrive out of order, equal timestamps use last-write-wins, and the first version is single-threaded. Each key maps to an array sorted by (timestamp, sequence). get performs an upper-bound search for the first timestamp greater than the query and returns the preceding version, giving O(log m) lookup and correct equality behavior. If timestamps are guaranteed increasing, set becomes amortized O(1). If writes dominate reads, I would append to a log and build an index asynchronously. Tests cover unknown keys, before the first version, equal to first and last versions, after the last version, out-of-order writes, duplicate timestamps, and null values.”

Common mistakes

• Mistake → linearly scan for the last version; why it fails → lookup becomes O(m) and scales poorly; fix → maintain sorted histories and use upper-bound search.
• Mistake → use timestamp < t; why it fails → a write exactly at t is omitted; fix → find the first timestamp > t.
• Mistake → assume all writes are increasing; why it fails → an out-of-order event breaks the array invariant; fix → state the constraint and use ordered insertion or a tree.
• Mistake → use null for both a miss and a stored value; why it fails → callers cannot distinguish states; fix → return { found, value } or an explicit option type.
• Mistake → ignore equal timestamps; why it fails → results depend on incidental ordering; fix → add a sequence or reject the conflict.

Follow-up responses

How would you optimize if timestamps are guaranteed increasing?

Append per key for amortized O(1) writes. Keep binary search for predictable O(log m) reads, or scan backward only when access patterns show queries are usually near the newest version. Do not claim backward scanning is worst-case constant time.

How would you retain only the last 30 days per key?

Define whether the cutoff uses event time or service time, then periodically remove the old prefix while preserving order. A query before the cutoff should return “history unavailable,” not masquerade as an ordinary miss.

What changes for concurrent readers and writers?

Define a linearization point first. A straightforward design uses a read-write lock per key. For non-blocking reads, build a new array and atomically swap its reference so readers observe a complete old or new snapshot.

How would you persist and recover after a crash?

Append a sequenced log before acknowledging a write, periodically materialize an index snapshot, and replay the suffix after recovery while validating sequence numbers. Do not add a full database design when the prompt only asks for memory.