Time-Based Key-Value Store
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Time-Based Key-Value Store
Design a key-value store that remembers multiple versions of each key, stamped with an integer time, and lets you read the value a key held **as of** a given time.
Implement a structure that supports two operations, applied as a list of queries:
- `["SET", key, value, timestamp]` — store `key = value` at the integer `timestamp`.
- `["GET", key, timestamp]` — return the value associated with `key` whose stored timestamp is the **largest timestamp less than or equal to** the query `timestamp`. If there is no such write (the key was never set, or all of its writes happened strictly after `timestamp`), return the empty string `""`.
Your function receives `queries: List[List[str]]` and returns `List[str]` — one entry for each `GET` query, in order (`SET` queries produce no output).
## Notes and constraints
- For any single key, the `SET` timestamps are strictly increasing in the order they are applied.
- Different keys are independent.
- `GET` must run in `O(log n)` time with respect to the number of writes for that key — design for the case where a hot key receives many writes and many point-in-time reads.
- `1 <= len(queries) <= 2 * 10^5`.
- `1 <= timestamp <= 10^9`; values and keys are non-empty strings of length up to 100.
## Example
Input:
```
[
["SET", "rate", "A", "1"],
["GET", "rate", "1"],
["GET", "rate", "3"],
["SET", "rate", "B", "4"],
["GET", "rate", "3"],
["GET", "rate", "5"],
["GET", "rate", "0"]
]
```
Output:
```
["A", "A", "A", "B", ""]
```
Explanation: at time 3 the latest write `<= 3` is the one at time 1 (`A`); at time 5 the latest is the write at time 4 (`B`); at time 0 there is no write at or before 0, so `""`.
Quick Answer: This question evaluates the ability to design a data structure that supports versioned storage and efficient point-in-time lookups. It tests binary search technique and time-space tradeoff reasoning within a coding and algorithms context, commonly used to assess practical system-building skills beyond basic data structure knowledge.
Design a key-value store that remembers multiple versions of each key, stamped with an integer time, and lets you read the value a key held **as of** a given time.
Implement a structure that supports two operations, applied as a list of queries:
- `["SET", key, value, timestamp]` — store `key = value` at the integer `timestamp`.
- `["GET", key, timestamp]` — return the value associated with `key` whose stored timestamp is the **largest timestamp less than or equal to** the query `timestamp`. If there is no such write (the key was never set, or all of its writes happened strictly after `timestamp`), return the empty string `""`.
Your function receives `queries: List[List[str]]` and returns `List[str]` — one entry for each `GET` query, in order (`SET` queries produce no output).
## Notes and constraints
- For any single key, the `SET` timestamps are strictly increasing in the order they are applied.
- Different keys are independent.
- `GET` must run in `O(log n)` time with respect to the number of writes for that key — design for a hot key that receives many writes and many point-in-time reads.
- `1 <= len(queries) <= 2 * 10^5`.
- `1 <= timestamp <= 10^9`; values and keys are non-empty strings of length up to 100.
## Example
Input:
```
[
["SET", "rate", "A", "1"],
["GET", "rate", "1"],
["GET", "rate", "3"],
["SET", "rate", "B", "4"],
["GET", "rate", "3"],
["GET", "rate", "5"],
["GET", "rate", "0"]
]
```
Output:
```
["A", "A", "A", "B", ""]
```
Explanation: at time 3 the latest write `<= 3` is the one at time 1 (`A`); at time 5 the latest is the write at time 4 (`B`); at time 0 there is no write at or before 0, so `""`.
Constraints
- 1 <= len(queries) <= 2 * 10^5
- For any single key, SET timestamps are strictly increasing in application order
- 1 <= timestamp <= 10^9
- Keys and values are non-empty strings of length up to 100
- GET must run in O(log n) with respect to the number of writes for that key
Examples
Input: ([['SET', 'rate', 'A', '1'], ['GET', 'rate', '1'], ['GET', 'rate', '3'], ['SET', 'rate', 'B', '4'], ['GET', 'rate', '3'], ['GET', 'rate', '5'], ['GET', 'rate', '0']],)
Expected Output: ['A', 'A', 'A', 'B', '']
Explanation: The worked example. GET at 1 and 3 return 'A' (only write <= them is at t=1). After SET B at t=4: GET 3 still sees only the t=1 write ('A'); GET 5 sees t=4 ('B'); GET 0 has no write at or before it, so ''.
Input: ([],)
Expected Output: []
Explanation: Empty query list produces no output.
Input: ([['GET', 'missing', '5']],)
Expected Output: ['']
Explanation: A GET on a key that was never SET returns the empty string.
Input: ([['SET', 'a', 'x', '10'], ['SET', 'b', 'y', '10'], ['GET', 'a', '10'], ['GET', 'b', '10'], ['GET', 'a', '9'], ['GET', 'b', '11']],)
Expected Output: ['x', 'y', '', 'y']
Explanation: Different keys are independent. GET a at 10 -> 'x', GET b at 10 -> 'y', GET a at 9 -> '' (its only write is at 10, which is later), GET b at 11 -> 'y' (latest write <= 11).
Input: ([['SET', 'k', 'v1', '5'], ['SET', 'k', 'v2', '8'], ['GET', 'k', '5'], ['GET', 'k', '7'], ['GET', 'k', '4'], ['GET', 'k', '1000000000']],)
Expected Output: ['v1', 'v1', '', 'v2']
Explanation: Boundary checks. GET at 5 hits the write exactly at 5 ('v1'); GET at 7 falls between the two writes -> 'v1'; GET at 4 precedes all writes -> ''; GET at 1e9 is past everything -> latest 'v2'.
Hints
- Bucket writes by key: for each key keep the (timestamp, value) pairs in the order they were SET. Since SET timestamps are strictly increasing per key, that list is already sorted by timestamp.
- A GET is a 'largest timestamp <= query' lookup on a sorted array — that is a classic binary search. Use bisect_right(times, ts): it returns the count of stored timestamps <= ts, so the answer is at index (that count - 1).
- Handle the empty case: if the key was never SET, or bisect returns 0 (every write happened strictly after the query time), return the empty string "".