Implement time-versioned KV store with restore
Company: Perplexity
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Design and implement an in-memory key–value store where every operation is associated with a timestamp (monotonically increasing integer). The store must support time-travel queries and rollback.
Implement the following operations (you may choose function signatures, but the semantics must match):
1. `set(key, value, ts)`: Set `key` to `value` effective at time `ts`.
2. `get(key, ts)`: Return the value of `key` at time `ts` (the most recent `set` at or before `ts` that hasn’t been deleted by time `ts`). Return `null`/`None` if the key does not exist at `ts`.
3. `delete(key, ts)`: Delete `key` effective at time `ts`.
4. Range query requirement: support querying a time interval for a key, e.g. `getRange(key, startTs, endTs)`, returning the value history within `[startTs, endTs]` (for example, a list of segments or (timestamp, value) change points within the interval).
5. `restore(ts)`: Restore the *entire store* to exactly the state it had at time `ts` (after all operations with timestamp `<= ts`), discarding the effects of any operations with timestamp `> ts`.
Discuss and/or implement data structures that make these operations efficient. Clarify any assumptions (e.g., whether multiple operations may share the same timestamp, and how ties are resolved).
Quick Answer: This question evaluates a candidate's ability to design and implement a time-versioned key–value store, assessing knowledge of temporal data structures, versioning semantics, time-travel and range queries, deletion semantics, and rollback/restoration.
You are given a sequence of operations for an in-memory time-versioned key-value store. Implement a function `solution(operations)` that processes the operations in order and returns the answers for every `get` and `getRange` query.
Operations are represented as tuples:
- `("set", key, value, ts)`: set `key` to `value` effective at timestamp `ts`.
- `("get", key, ts)`: return the value visible for `key` at time `ts`, or `None` if the key does not exist at that time.
- `("delete", key, ts)`: delete `key` effective at timestamp `ts`.
- `("getRange", key, startTs, endTs)`: return the visible value history for `key` inside `[startTs, endTs]` as a list of `[timestamp, value]` change points.
- `("restore", ts)`: restore the entire store to exactly the state it had after all mutations with timestamp `<= ts`, permanently discarding every mutation with timestamp `> ts`.
Important clarifications:
- Process operations in input order.
- Only `set` and `delete` create historical changes.
- `get` and `getRange` are queries only; they do not change history.
- `restore` truncates the current timeline; discarded future mutations do not come back later.
- Mutation timestamps (`set`/`delete`) are non-decreasing in input order. Equal timestamps are allowed.
- If multiple mutations share the same timestamp, input order breaks ties: the later mutation is the visible one at that timestamp.
- For `getRange`, return visible change points, not every raw mutation. If the key already exists at `startTs`, include `[startTs, value_at_startTs]` as the first entry. Then include later timestamps in `(startTs, endTs]` where the visible value changes. Deletions are represented by `None`.
Your goal is to support these operations efficiently.
Constraints
- 0 <= len(operations) <= 2 * 10^5
- 0 <= ts, startTs, endTs <= 10^9
- Timestamps of `set` and `delete` operations are non-decreasing in input order
- Equal mutation timestamps are allowed; later input order wins for that timestamp
- Keys are strings; values can be any Python value comparable with `==`
Examples
Input: [("set", "a", "x", 1), ("set", "a", "y", 4), ("get", "a", 3), ("getRange", "a", 1, 5), ("delete", "a", 6), ("get", "a", 6)]
Expected Output: ["x", [[1, "x"], [4, "y"]], None]
Explanation: At time 3, `a` is `x`. The range [1, 5] shows `a` starting as `x` and changing to `y` at time 4. After deleting at time 6, `get(a, 6)` returns None.
Input: [("set", "a", 10, 1), ("set", "b", 20, 2), ("set", "a", 30, 5), ("get", "a", 5), ("restore", 2), ("get", "a", 5), ("get", "b", 100), ("getRange", "a", 1, 10)]
Expected Output: [30, 10, 20, [[1, 10]]]
Explanation: Before restore, `a` is 30 at time 5. Restoring to time 2 discards the change at time 5, so later queries see `a = 10` and `b = 20`. The only visible history for `a` is its value from time 1.
Hints
- Store, for each key, a sorted history of its mutations. Because mutation timestamps are non-decreasing, you can append instead of inserting.
- To make `restore(ts)` efficient, keep a global stack of applied mutations and pop mutations from the end while their timestamp is greater than `ts`.