Point-in-Time Reads from a Timestamped Key-Value Store
Company: Cockroach Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a key-value store that keeps every version of each key. A write records a value for a key at a timestamp without discarding earlier versions, and a read asks for a key as of a timestamp and returns the value that was current at that time.
The interviewer's focus is the data structure behind the read: a read should not have to scan through every version of its key.
So that the store can be called as one function, it is driven by a list of operations that are processed in order, and you return the results of the reads.
### Function Signature
```python
def run_versioned_store(operations: list[tuple]) -> list[str]:
```
Each operation is one of:
- `("set", key, value, timestamp)`: store `value` for `key` at time `timestamp`.
- `("get", key, timestamp)`: read `key` as of time `timestamp`.
### Rules
- A `get` considers only the `set` operations for the same `key` that appear earlier in the list. Among those, it returns the `value` of the one with the largest timestamp that is less than or equal to the `get`'s timestamp.
- If there is no such `set`, because the key has never been set or every earlier `set` of the key has a larger timestamp, the `get` returns the empty string `""`.
- A `set` never removes earlier versions of its key.
- Return one string per `get`, in the order the `get` operations appear. Return an empty list if there are no `get` operations.
### Constraints
- `1 <= len(operations) <= 2 * 10^5`
- Every `key` and `value` is a non-empty string of at most 100 lowercase English letters and digits.
- `1 <= timestamp <= 10^7` in every operation.
- The timestamps of the `set` operations strictly increase in the order those operations appear, across all keys. The timestamps of `get` operations can be any value in range, in any order.
### Examples
**Example 1**
```text
Input: operations = [("set", "price", "10", 5), ("get", "price", 4), ("get", "price", 5),
("set", "price", "12", 9), ("get", "price", 8), ("get", "price", 9),
("get", "price", 100)]
Output: ["", "10", "10", "12", "12"]
```
At time 4 the key has no version yet. Reads at times 5 and 8 see the version written at time 5, because the version written at time 9 is later than 8. Reads at times 9 and 100 see the version written at time 9.
**Example 2**
```text
Input: operations = [("set", "a", "x", 1), ("set", "b", "y", 2), ("get", "a", 2),
("get", "b", 1), ("set", "a", "z", 3), ("get", "a", 3), ("get", "c", 3)]
Output: ["x", "", "z", ""]
```
Key `b` was first written at time 2, so a read at time 1 finds nothing. Key `c` is never written.
Overview: Build a versioned key-value store whose reads return the value a key held at a given timestamp: the latest write at or before that time, or an empty string if there is none. Tests choosing a per-key data layout that keeps point-in-time lookups fast across up to 200,000 operations.
Read the full Cockroach Labs Software Engineer interview experience this question came from
Implement a key-value store that keeps every version of each key. A write records a value for a key at a timestamp without discarding earlier versions, and a read asks for a key as of a timestamp and returns the value that was current at that time. The focus is the data structure behind the read: a read should not have to scan through every version of its key.
So that the store can be called as one function, it is driven by a list of operations that are processed in order. Implement `run_versioned_store(operations)`, which returns the results of the reads as a list of strings.
Each operation is one of:
- `("set", key, value, timestamp)`: store `value` for `key` at time `timestamp`.
- `("get", key, timestamp)`: read `key` as of time `timestamp`.
Rules:
- A `get` considers only the `set` operations for the same `key` that appear earlier in the list. Among those, it returns the `value` of the one with the largest timestamp that is less than or equal to the `get`'s timestamp.
- If there is no such `set`, because the key has never been set or every earlier `set` of the key has a larger timestamp, the `get` returns the empty string `""`.
- A `set` never removes earlier versions of its key.
- Return one string per `get`, in the order the `get` operations appear. Return an empty list if there are no `get` operations.
Constraints:
- `1 <= len(operations) <= 2 * 10^5`
- Every `key` and `value` is a non-empty string of at most 100 lowercase English letters and digits.
- `1 <= timestamp <= 10^7` in every operation, so every timestamp fits in a 32-bit signed integer (no value exceeds 2^31 - 1).
- The timestamps of the `set` operations strictly increase in the order those operations appear, across all keys. The timestamps of `get` operations can be any value in range, in any order.
Example 1:
Input: operations = [("set", "price", "10", 5), ("get", "price", 4), ("get", "price", 5), ("set", "price", "12", 9), ("get", "price", 8), ("get", "price", 9), ("get", "price", 100)]
Output: ["", "10", "10", "12", "12"]
Explanation: At time 4 the key has no version yet. Reads at times 5 and 8 see the version written at time 5, because the version written at time 9 is later than 8. Reads at times 9 and 100 see the version written at time 9.
Example 2:
Input: operations = [("set", "a", "x", 1), ("set", "b", "y", 2), ("get", "a", 2), ("get", "b", 1), ("set", "a", "z", 3), ("get", "a", 3), ("get", "c", 3)]
Output: ["x", "", "z", ""]
Explanation: Key `b` was first written at time 2, so a read at time 1 finds nothing. Key `c` is never written.
Constraints
- 1 <= len(operations) <= 2 * 10^5
- Each operation is either ("set", key, value, timestamp) or ("get", key, timestamp).
- Every key and value is a non-empty string of at most 100 lowercase English letters and digits.
- 1 <= timestamp <= 10^7 in every operation (fits in a 32-bit signed integer).
- The timestamps of the set operations strictly increase in the order those operations appear, across all keys. The timestamps of get operations can be any value in range, in any order.
Examples
Input: ([('set', 'price', '10', 5), ('get', 'price', 4), ('get', 'price', 5), ('set', 'price', '12', 9), ('get', 'price', 8), ('get', 'price', 9), ('get', 'price', 100)],)
Expected Output: ['', '10', '10', '12', '12']
Explanation: Source Example 1: read below the first version, read equal to a version, floor between versions (8 sees time 5, not ceiling 9), and reads at and after the last version.
Input: ([('set', 'a', 'x', 1), ('set', 'b', 'y', 2), ('get', 'a', 2), ('get', 'b', 1), ('set', 'a', 'z', 3), ('get', 'a', 3), ('get', 'c', 3)],)
Expected Output: ['x', '', 'z', '']
Explanation: Source Example 2: key b read before its first version, key c never written, key a updated between reads.
Hints
- A get can only see sets that appear before it in the list, so each get can be answered at the moment you reach it while walking through the operations once.
- Given the rule about set timestamps, in what order are the versions of any single key recorded?
- A read wants the last version of its key at or before the read's time; consider how the ordering of a key's versions lets you find it without checking every version.