Snapshot Key-Value Store

Based on my comprehensive research, I can now provide the problem definition. The "Snapshot Key-Value Store" is a design problem documented in Apple and Rubrik interviews, though there isn't an official LeetCode listing. Let me create the final output.

Snapshot Key-Value Store

Problem Description

Design a key-value data structure that allows users to store and retrieve values associated with keys, with the additional capability to take point-in-time snapshots of the entire data structure. After a snapshot is taken, any subsequent modifications to the key-value store should not affect previously captured snapshots. Users must be able to read values from any snapshot they have taken, and optionally delete snapshots to free up resources.

The data structure should support an arbitrary number of snapshots, where each snapshot preserves the complete state of the key-value store at the moment it was created. Modifications made after a snapshot is taken should be isolated from that snapshot—meaning queries against a snapshot return values as they existed at the time of the snapshot, regardless of changes made afterward.

Input/Output Format

Constructor

SnapshotKeyValueStore()

• Initializes an empty key-value store with no snapshots

Methods

void set(String key, String value)

• Sets the value for a given key in the current key-value store
• If the key already exists, update its value
• Returns: void
• Time Complexity: O(1) amortized

String get(String key)

• Retrieves the value associated with a key from the current key-value store
• If the key does not exist, returns an empty string or null
• Returns: the value as a String
• Time Complexity: O(1) amortized

String takeSnapshot() (or int takeSnapshot())

• Captures a snapshot of the current state of the key-value store
• Returns a snapshot identifier (can be a string ID or integer index)
• Time Complexity: O(1) if using copy-on-write; O(n) if requiring full copy where n is number of key-value pairs
• Space Complexity: O(1) if using reference counting; O(n) if using full copy

String get(String key, String snapshotId) (or with snapshot identifier)

• Retrieves the value for a key from a specific snapshot
• Returns the value as it existed in that snapshot at the time it was taken
• If the key did not exist in the snapshot, returns empty string or null
• Returns: the value as a String
• Time Complexity: O(1) amortized

void deleteSnapshot(String snapshotId)

• Deletes a snapshot, freeing up associated resources
• After deletion, that snapshot ID should not be queryable
• Returns: void
• Time Complexity: O(1) or O(n) depending on implementation

Examples

Example 1: Basic Snapshot Operations

Input: ["SnapshotKeyValueStore", "set", "get", "takeSnapshot", "set", "get", "get"] [[], ["name", "Alice"], ["name"], [], ["name", "Bob"], ["name"], ["name", "snapshot1"]]

Output: [null, null, "Alice", "snapshot1", null, "Bob", "Alice"]

Explanation:

1. Initialize empty key-value store
2. set("name", "Alice") – Store name → Alice
3. get("name") – Returns "Alice" from current store
4. takeSnapshot() – Create snapshot labeled "snapshot1" with state {name: Alice}
5. set("name", "Bob") – Update current store, name → Bob
6. get("name") – Returns "Bob" from current store (modified after snapshot)
7. get("name", "snapshot1") – Returns "Alice" (value from snapshot1, unaffected by the subsequent update)

Example 2: Multiple Snapshots and Deletions

Input: ["SnapshotKeyValueStore", "set", "set", "takeSnapshot", "set", "takeSnapshot", "get", "get", "deleteSnapshot", "get"] [[], ["user", "John"], ["age", "30"], [], ["user", "Jane"], [], ["user", "snap1"], ["user", "snap2"], ["snap1"], ["user", "snap2"]]

Output: [null, null, null, "snap1", null, "snap2", "John", "Jane", null, "Jane"]

Explanation:

1. Initialize empty store
2. set("user", "John") – current state: {user: John}
3. set("age", "30") – current state: {user: John, age: 30}
4. takeSnapshot() – Create "snap1" with {user: John, age: 30}
5. set("user", "Jane") – current state: {user: Jane, age: 30}
6. takeSnapshot() – Create "snap2" with {user: Jane, age: 30}
7. get("user", "snap1") – Returns "John" (snap1 captured before update)
8. get("user", "snap2") – Returns "Jane" (snap2 captured after update)
9. deleteSnapshot("snap1") – Delete snap1
10. get("user", "snap2") – Returns "Jane" (snap2 still valid, unaffected by snap1 deletion)

Constraints

• Key/Value Size: 1 ≤ key.length, value.length ≤ 100
• Key/Value Characters: Keys and values consist of lowercase English letters, digits, and underscores
• Number of Operations: At most 10^4 total operations (set, get, takeSnapshot, deleteSnapshot)
• Number of Keys: At most 10^3 distinct keys across all operations
• Number of Snapshots: At most 10^2 snapshots
• Memory Efficiency: Space complexity is prioritized over time complexity; minimize memory footprint especially for snapshot storage
• Snapshot Immutability: Snapshots must be immutable and independent of current state mutations

Solution Hint

Use a hash map to store the current key-value pairs. For each snapshot, instead of copying the entire hash map (which is space-inefficient), maintain a mapping from snapshot ID to only the key-value pairs that were modified before or at that snapshot. For queries against a snapshot, check the snapshot's stored changes first; if a key was not modified before the snapshot, fall back to the current state. Alternatively, use a versioning strategy where each key maintains a history of values with associated snapshot timestamps, enabling efficient retrieval without full copies. Copy-on-write or reference counting techniques can further optimize memory usage by sharing unchanged data across snapshots.