Design a snapshotable key-value store
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design and implement a snapshotable key–value map supporting the following APIs:
- S(key, value): set the current value of a string key to a string value.
- G(key): get the current value for key (or null if absent).
- Snapshot(): capture the current state and return a snapshotId (opaque string).
- GS(snapshotId, key): get the value of key as of the given snapshot.
Requirements:
- Support arbitrarily many snapshots; later writes must not affect earlier snapshots.
- Be space‑efficient across snapshots (avoid full copies; consider copy‑on‑write or per‑key versioned logs).
- Target time complexity around O(log u) per operation where u is updates per key (justify alternatives).
- Define behavior for overwrites, deletions, unknown keys, and consecutive snapshots without intervening writes.
- Specify snapshotId generation and ordering guarantees.
- Discuss how to extend to concurrency (reads during writes) and persistence/durability (optional).
Example scenario to satisfy:
S("a", "a-foo"); S("b", "b-foo"); id = Snapshot(); S("a", "a-foo-prime");
G("a") -> "a-foo-prime"
GS(id, "a") -> "a-foo"
G("b") -> "b-foo"
GS(id, "b") -> "b-foo".
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design a snapshotable key-value store states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Implement a snapshotable key-value store and drive it with a replayable command log.
Write a function that takes a list of `operations` and returns the list of outputs produced by the query operations, in order. Each operation is a list whose first element is the operation name:
- `["S", key, value]` - **Set**: set the current value of string `key` to string `value`. Produces no output.
- `["G", key]` - **Get**: return the current value of `key`, or `null`/`None` if absent. Appended to the output.
- `["Snapshot"]` - capture the current state and return a `snapshotId`. The id is deterministic: the i-th snapshot (0-indexed) returns `"snap-<i>"` (`"snap-0"`, `"snap-1"`, ...). Appended to the output.
- `["GS", snapshotId, key]` - **Get-Snapshot**: return the value of `key` as of the moment `snapshotId` was taken, or `null`/`None` if the key did not exist then (or the snapshotId is unknown). Appended to the output.
Rules / behavior to honor:
- Later writes must NOT affect earlier snapshots.
- An overwrite replaces the current value; the new value is only visible to snapshots taken AFTER the overwrite.
- Consecutive writes to the same key between two snapshots collapse - only the last value before a snapshot is captured by that snapshot.
- Unknown keys (never set, or not yet set at the snapshot's time) and unknown snapshotIds return `null`/`None`.
- A `Snapshot` taken with no intervening writes captures the same visible state as the previous snapshot.
Return the ordered list of outputs from all `G`, `Snapshot`, and `GS` operations.
Constraints
- 0 <= number of operations <= 10^5
- Keys and values are non-empty strings (except absent reads, which return null/None).
- snapshotId values are exactly the strings returned by prior Snapshot ops: "snap-0", "snap-1", ...
- A GS with an unknown snapshotId returns null/None.
- Reads of a key that was never set (or not yet set at the snapshot's time) return null/None.
Examples
Input: ([["S", "a", "a-foo"], ["S", "b", "b-foo"], ["Snapshot"], ["S", "a", "a-foo-prime"], ["G", "a"], ["GS", "snap-0", "a"], ["G", "b"], ["GS", "snap-0", "b"]],)
Expected Output: ["snap-0", "a-foo-prime", "a-foo", "b-foo", "b-foo"]
Explanation: The prompt's example. Snapshot returns 'snap-0'. After overwriting 'a', G("a")='a-foo-prime' (current) but GS('snap-0','a')='a-foo' (frozen at the snapshot). 'b' was never overwritten, so both G and GS return 'b-foo'.
Input: ([["G", "x"]],)
Expected Output: [null]
Explanation: Reading a key that was never set returns null/None.
Hints
- Don't deep-copy the whole map on every Snapshot - that is O(keys) space per snapshot. Keep history per key instead (copy-on-write).
- Maintain a global 'era' counter that increments on each Snapshot. A write tags its value with the current era; a read 'as of snapshot s' wants the latest value whose era is <= the era when s was taken.
- Store each key's changes as a sorted list of (era, value). Binary search (bisect_right - 1) gives the value visible at any era in O(log u).
- Map each returned snapshotId to the era value it captured, so GS can translate the opaque id back into an era before searching.