Rubrik OA 面试真题解析：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

这道题考察的是“带版本回溯”的键值存储设计。核心思路通常是为每个 key 维护按 snapshot_id 递增的历史记录，例如用哈希表映射到有序版本列表，再配合二分查找在指定快照中快速定位值；删除操作可以记录 tombstone 标记，删除快照则需要让对应 snapshot_id 失效。实现时要同时处理“key 不存在”和“snapshot 不存在”两类错误，并保证查询能够还原到快照创建时的状态。