Rubrik Interview Coding Question: Snapshot Key-Value Store

Design a key-value store with snapshot support.

Implement the following functions:

• void put(string key, string value)
• void delete(string key)
• string get(string key, int snapshot_id)
• int takeSnapshot()
• void deleteSnapshot(int snapshot_id)

Behavior:

• put(key, value) stores or updates the value for the given key.
• delete(key) removes the key from the current state.
• takeSnapshot() creates a snapshot and returns its snapshot id.
• get(key, snapshot_id) returns the value of key at the time the snapshot was taken.
• deleteSnapshot(snapshot_id) removes that snapshot.
• If a key does not exist at the requested snapshot, return an error.
• If a snapshot does not exist, return an error.

Example:

put("k1", "v1")
put("k2", "v2")
put("k3", "v3")
takeSnapshot() -> Snapshot 1
get("k1", Snapshot 1) -> v1
put("k1", "v4")
delete("k3")
takeSnapshot() -> Snapshot 2
get("k1", Snapshot 2) -> v4
get("k1", Snapshot 1) -> v1
get("k3", Snapshot 2) -> Error: k3 does not exist
get("k3", Snapshot 1) -> v3
deleteSnapshot(Snapshot 1)
get("k1", Snapshot 1) -> Error: Snapshot 1 does not exist
get("k2", Snapshot 2) -> v2

This problem is about designing a versioned key-value store with snapshot lookup. A common approach is to keep, for each key, a history of values indexed by snapshot id, then use binary search to answer queries at a given snapshot efficiently. Deletions can be represented with tombstones, and deleting a snapshot should invalidate that snapshot id so later queries return an error. The main challenge is preserving old values while supporting updates, deletes, snapshot creation, and snapshot removal correctly.