Timestamped key-value store: return each key's value as of a query time
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Build a key-value store that keeps every version of each key. Each write records a value for a key at a timestamp. Each read asks what the value of a key was at a given time: the value written by the latest write to that key whose timestamp is less than or equal to the query time.
Process a sequence of operations and return the result of every read.
### Function Signature
```python
def run_time_store(operations: list[list]) -> list[str]:
```
Each operation is one of:
- `["set", key, value, timestamp]` records `value` for `key` at `timestamp`. It produces no output.
- `["get", key, timestamp]` produces the value written by the `set` for `key` with the largest timestamp less than or equal to `timestamp`, or `""` if there is no such `set`.
`key` and `value` are strings, and `timestamp` is an integer.
### Rules
- Operations are processed in list order. A `get` sees only the `set` operations that appear before it in the list.
- `set` timestamps are strictly increasing in the order the `set` operations appear, across all keys, so a key never has two writes with the same timestamp.
- A `get` timestamp can be any value in the allowed range, earlier or later than any write.
- The output contains one string per `get`, in the order the `get` operations appear. If there are no `get` operations, return an empty list.
### Constraints
- `1 <= len(operations) <= 2 * 10^5`
- Every `key` and `value` is a nonempty string of at most 20 lowercase English letters and digits.
- `1 <= timestamp <= 10^9`
### Examples
**Example 1**
```text
Input: operations = [["set", "color", "red", 3], ["get", "color", 2], ["get", "color", 3], ["get", "color", 5], ["set", "color", "blue", 8], ["get", "color", 7], ["get", "color", 8], ["get", "color", 100]]
Output: ["", "red", "red", "red", "blue", "blue"]
```
At time 2 nothing has been written to `color`. Times 3, 5 and 7 see the write at time 3. Times 8 and 100 see the write at time 8.
**Example 2**
```text
Input: operations = [["set", "a", "x", 1], ["set", "b", "y", 2], ["get", "a", 2], ["get", "b", 1], ["get", "c", 5]]
Output: ["x", "", ""]
```
`b` was first written at time 2, so it has no value at time 1, and `c` was never written.
**Example 3**
```text
Input: operations = [["set", "k", "v1", 10], ["get", "k", 50], ["set", "k", "v2", 20], ["get", "k", 50], ["get", "k", 15]]
Output: ["v1", "v2", "v1"]
```
The first `get` sees only the write at time 10. After the write at time 20, time 50 sees `"v2"`, while time 15 still sees `"v1"`.
Overview: A coding question that processes set and get operations on a key-value store where each write carries a timestamp and each read asks for a key's value as of a given time. It tests per-key version history, finding the latest write at or before a query time, and handling many interleaved operations efficiently.
Read the full Oracle Software Engineer interview experience this question came from
Build a key-value store that keeps every version of each key. Each write records a value for a key at a timestamp. Each read asks what the value of a key was at a given time: the value written by the latest write to that key whose timestamp is less than or equal to the query time.
Implement `run_time_store(operations)`, which processes a sequence of operations and returns the result of every read.
Each operation is one of:
- `["set", key, value, timestamp]` records `value` for `key` at `timestamp`. It produces no output.
- `["get", key, timestamp]` produces the value written by the `set` for `key` with the largest timestamp less than or equal to `timestamp`, or `""` (the empty string) if there is no such `set`.
`key` and `value` are strings, and `timestamp` is an integer.
**Rules**
- Operations are processed in list order. A `get` sees only the `set` operations that appear before it in the list.
- `set` timestamps are strictly increasing in the order the `set` operations appear, across all keys, so a key never has two writes with the same timestamp.
- A `get` timestamp can be any value in the allowed range, earlier or later than any write.
- Return one string per `get`, in the order the `get` operations appear. If there are no `get` operations, return an empty list.
**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 nonempty string of at most 20 lowercase English letters and digits.
- `1 <= timestamp <= 10^9` for every operation. No timestamp exceeds 2^31 - 1, so every timestamp fits in a signed 32-bit integer.
**Input types by language**
Each operation mixes strings and an integer. In Java an operation is a `java.util.List<Object>` whose timestamp should be read through `Number`; in C++ an operation is a `std::vector<std::string>` whose timestamp arrives as its decimal text (for example `"3"`), so convert it with `std::stoll`.
**Example 1**
```text
Input: operations = [["set", "color", "red", 3], ["get", "color", 2], ["get", "color", 3], ["get", "color", 5], ["set", "color", "blue", 8], ["get", "color", 7], ["get", "color", 8], ["get", "color", 100]]
Output: ["", "red", "red", "red", "blue", "blue"]
```
At time 2 nothing has been written to `color`. Times 3, 5 and 7 see the write at time 3. Times 8 and 100 see the write at time 8.
**Example 2**
```text
Input: operations = [["set", "k", "v1", 10], ["get", "k", 50], ["set", "k", "v2", 20], ["get", "k", 50], ["get", "k", 15]]
Output: ["v1", "v2", "v1"]
```
The first `get` sees only the write at time 10. After the write at time 20, time 50 sees `"v2"`, while time 15 still sees `"v1"`.
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 nonempty string of at most 20 lowercase English letters and digits.
- 1 <= timestamp <= 10^9 for every operation (fits in a signed 32-bit integer).
- set timestamps are strictly increasing in the order the set operations appear, across all keys.
Examples
Input: ([['set', 'color', 'red', 3], ['get', 'color', 2], ['get', 'color', 3], ['get', 'color', 5], ['set', 'color', 'blue', 8], ['get', 'color', 7], ['get', 'color', 8], ['get', 'color', 100]],)
Expected Output: ['', 'red', 'red', 'red', 'blue', 'blue']
Explanation: Source Example 1: time 2 precedes the first write; times 3, 5 and 7 see red; times 8 and 100 see blue.
Input: ([['set', 'k', 'v1', 10], ['get', 'k', 50], ['set', 'k', 'v2', 20], ['get', 'k', 50], ['get', 'k', 15]],)
Expected Output: ['v1', 'v2', 'v1']
Explanation: Source Example 3: the first get cannot see the later set; time 15 still sees v1 after v2 is written.
Hints
- A get can only see set operations that appear before it in the list, so each get can be answered at the moment it is reached.
- Every set timestamp is larger than all earlier ones, so the writes you have seen for any single key are already in timestamp order.
- Writes to one key never affect reads of another key, so keep each key's history separate.