Snapshot-Versioned Key-Value Store with Put, Get, Snapshot and Delete
Company: Snorkel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a key-value store whose history is versioned by snapshots rather than by timestamps. `put` sets a key's current value, `snapshot` freezes the current contents of the whole store and returns an id, and `get` reads the value a key had in a given snapshot. A second stage adds `delete`, which removes a key from the current contents.
The reported interview staged the work as milestones: `put`, `get` and `snapshot` first, then `delete` as an optional extension. This version asks for all four operations, fixes their exact semantics in Rules below, and replays them as a list of operations.
### Function Signature
```python
def run_snapshot_store(operations: list[list[str]]) -> list[str]:
```
### Rules
- The store starts empty, with no snapshots. Operations are applied in the order given.
- `["put", key, value]` sets the current value of `key` to `value`, replacing any earlier value. It produces no output.
- `["delete", key]` removes `key` from the current contents. Deleting a key that is absent is allowed and changes nothing. It produces no output.
- `["snapshot"]` records the current contents of the whole store as a new snapshot and outputs its id. Ids are `0, 1, 2, ...` in the order snapshots are taken, written as decimal strings. A snapshot taken when nothing has changed since the previous one still receives a new id.
- `["get", key, snap_id]` outputs the value `key` had at the moment snapshot `snap_id` was taken, or the empty string `""` if `key` was absent in that snapshot. `snap_id` is a decimal string without leading zeros. Changes made after a snapshot was taken never affect what `get` returns for it.
- `get` reads only snapshots, never the current, not-yet-snapshotted contents.
- Return the outputs of all `snapshot` and `get` operations in operation order; `put` and `delete` contribute nothing to the result.
### Constraints
- `1 <= len(operations) <= 2 * 10^5`
- Every key and every value has 1 to 20 characters, each a lowercase English letter or a digit. Values are therefore never empty, so `""` in the result always means absent.
- Every `get` has `0 <= snap_id < s`, where `s` is the number of snapshots taken before that `get`.
- There can be up to `2 * 10^5` distinct keys and up to `2 * 10^5` snapshots; a snapshot may be taken while the store holds a very large number of keys, and many snapshots may be taken in a row.
### Examples
**Example 1**
```text
Input: operations = [["put", "a", "1"], ["snapshot"], ["put", "a", "2"],
["get", "a", "0"], ["snapshot"], ["get", "a", "1"],
["get", "b", "0"]]
Output: ["0", "1", "1", "2", ""]
```
Snapshot `0` is taken while `a` is `"1"`. The second `put` changes only the current contents, so reading `a` in snapshot `0` still gives `"1"`. Snapshot `1` sees `a = "2"`. Key `b` was never put, so reading it in snapshot `0` gives `""`. The result lists the outputs of the five `snapshot` and `get` operations in order.
**Example 2**
```text
Input: operations = [["put", "x", "red"], ["snapshot"], ["delete", "x"],
["snapshot"], ["put", "x", "blue"], ["snapshot"],
["get", "x", "0"], ["get", "x", "1"], ["get", "x", "2"]]
Output: ["0", "1", "2", "red", "", "blue"]
```
`x` is present in snapshot `0`, absent in snapshot `1` because it was deleted before that snapshot, and present again with a new value in snapshot `2`.
**Example 3**
```text
Input: operations = [["put", "k", "v1"], ["put", "k", "v2"], ["delete", "k"],
["put", "k", "v3"], ["snapshot"], ["delete", "zz"],
["snapshot"], ["get", "k", "1"], ["get", "k", "0"]]
Output: ["0", "1", "v3", "v3"]
```
Only the contents at the moment of a snapshot count: `"v1"`, `"v2"` and the delete were all superseded before snapshot `0`, which sees `k = "v3"`. Deleting the absent key `zz` changes nothing, so snapshot `1` has the same contents and also returns `"v3"` for `k`.
Overview: Implement a key-value store versioned by snapshots: put sets a key's current value, snapshot freezes the whole store and returns an id, get reads a key's value as of a given snapshot, and delete removes a key going forward. Tests designing versioned state that stays fast when there are many keys and many snapshots.
Implement a key-value store whose history is versioned by snapshots rather than by timestamps, then replay a list of operations against it. `put` sets a key's current value, `delete` removes a key from the current contents, `snapshot` freezes the current contents of the whole store and returns an id, and `get` reads the value a key had in a given snapshot.
Write `run_snapshot_store(operations)`, which applies every operation in order and returns the list of outputs.
**Rules**
- The store starts empty, with no snapshots. Operations are applied in the order given.
- `["put", key, value]` sets the current value of `key` to `value`, replacing any earlier value. It produces no output.
- `["delete", key]` removes `key` from the current contents. Deleting a key that is absent is allowed and changes nothing. It produces no output.
- `["snapshot"]` records the current contents of the whole store as a new snapshot and outputs its id. Ids are `0, 1, 2, ...` in the order snapshots are taken, written as decimal strings. A snapshot taken when nothing has changed since the previous one still receives a new id.
- `["get", key, snap_id]` outputs the value `key` had at the moment snapshot `snap_id` was taken, or the empty string `""` if `key` was absent in that snapshot. `snap_id` is a decimal string without leading zeros. Changes made after a snapshot was taken never affect what `get` returns for it.
- `get` reads only snapshots, never the current, not-yet-snapshotted contents.
- Return the outputs of all `snapshot` and `get` operations in operation order; `put` and `delete` contribute nothing to the result.
**Constraints**
- `1 <= len(operations) <= 2 * 10^5`
- Each operation is exactly one of `["put", key, value]`, `["delete", key]`, `["snapshot"]` or `["get", key, snap_id]`.
- Every key and every value has 1 to 20 characters, each a lowercase English letter or a digit. Values are therefore never empty, so `""` in the result always means absent.
- Every `get` has `0 <= snap_id < s`, where `s` is the number of snapshots taken before that `get`.
- There can be up to `2 * 10^5` distinct keys and up to `2 * 10^5` snapshots; a snapshot may be taken while the store holds a very large number of keys, and many snapshots may be taken in a row.
- Snapshot ids therefore stay below `2 * 10^5`, well within 32-bit range; they are passed in and returned as decimal strings.
**Example 1**
```text
Input: operations = [["put", "a", "1"], ["snapshot"], ["put", "a", "2"],
["get", "a", "0"], ["snapshot"], ["get", "a", "1"],
["get", "b", "0"]]
Output: ["0", "1", "1", "2", ""]
```
Snapshot `0` is taken while `a` is `"1"`. The second `put` changes only the current contents, so reading `a` in snapshot `0` still gives `"1"`. Snapshot `1` sees `a = "2"`. Key `b` was never put, so reading it in snapshot `0` gives `""`.
**Example 2**
```text
Input: operations = [["put", "x", "red"], ["snapshot"], ["delete", "x"],
["snapshot"], ["put", "x", "blue"], ["snapshot"],
["get", "x", "0"], ["get", "x", "1"], ["get", "x", "2"]]
Output: ["0", "1", "2", "red", "", "blue"]
```
`x` is present in snapshot `0`, absent in snapshot `1` because it was deleted before that snapshot, and present again with a new value in snapshot `2`.
Constraints
- 1 <= len(operations) <= 2 * 10^5
- Each operation is exactly one of ["put", key, value], ["delete", key], ["snapshot"] or ["get", key, snap_id].
- Every key and every value has 1 to 20 characters, each a lowercase English letter or a digit; values are never empty, so "" in the result always means absent.
- Every get has 0 <= snap_id < s, where s is the number of snapshots taken before that get; snap_id is a decimal string without leading zeros.
- There can be up to 2 * 10^5 distinct keys and up to 2 * 10^5 snapshots; a snapshot may be taken while the store holds a very large number of keys, and many snapshots may be taken in a row.
- Snapshot ids stay below 2 * 10^5 and fit in a 32-bit integer; they are passed in and returned as decimal strings.
Examples
Input: ([['put', 'a', '1'], ['snapshot'], ['put', 'a', '2'], ['get', 'a', '0'], ['snapshot'], ['get', 'a', '1'], ['get', 'b', '0']],)
Expected Output: ['0', '1', '1', '2', '']
Explanation: Source example 1: snapshot 0 keeps a = '1' despite the later put, snapshot 1 sees a = '2', and the never-put key b reads as empty.
Input: ([['put', 'x', 'red'], ['snapshot'], ['delete', 'x'], ['snapshot'], ['put', 'x', 'blue'], ['snapshot'], ['get', 'x', '0'], ['get', 'x', '1'], ['get', 'x', '2']],)
Expected Output: ['0', '1', '2', 'red', '', 'blue']
Explanation: Source example 2: x is present in snapshot 0, deleted before snapshot 1, and re-put with a new value before snapshot 2; the delete must not erase snapshot 0.
Hints
- Only the contents at the moment a snapshot is taken can ever be read, so several changes to the same key between two snapshots collapse into the last one.
- The store can hold up to 2 * 10^5 keys while up to 2 * 10^5 snapshots are taken in a row; think about what actually differs between consecutive snapshots rather than what each one contains in full.
- A change made right after snapshot k is taken belongs to the next snapshot, not to k; check that boundary carefully.