How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Perplexity.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Perplexity during technical interviews.

Implement time-versioned KV store with restore

Quick Overview

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.

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.

Input: [("set", "k", "first", 2), ("set", "k", "second", 2), ("delete", "k", 2), ("set", "k", "final", 2), ("get", "k", 2), ("getRange", "k", 1, 3)]

Expected Output: ["final", [[2, "final"]]]

Explanation: All mutations happen at the same timestamp. Input order breaks ties, so the final visible value at time 2 is `final`. The range query collapses same-timestamp mutations into one visible change point.

Input: [("delete", "m", 1), ("get", "m", 1), ("getRange", "m", 1, 3), ("set", "m", "z", 4), ("getRange", "m", 2, 4)]

Expected Output: [None, [], [[4, "z"]]]

Explanation: Deleting a missing key leaves it absent, so `get(m, 1)` is None and there is no visible history in [1, 3]. After setting `m` at time 4, the range [2, 4] shows a single visible change at time 4.

Input: [("set", "a", "red", 1), ("set", "a", "blue", 5), ("set", "a", "blue", 7), ("delete", "a", 9), ("getRange", "a", 3, 10), ("restore", 5), ("get", "a", 10), ("getRange", "a", 6, 10)]

Expected Output: [[[3, "red"], [5, "blue"], [9, None]], "blue", [[6, "blue"]]]

Explanation: From time 3 to 10, `a` starts as `red`, changes to `blue` at 5, stays `blue` at 7, and is deleted at 9. Restoring to 5 discards the later update and delete, so afterwards `a` is still `blue` at time 10.

Input: []

Expected Output: []

Explanation: No operations means no query outputs.

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`.

Quick Overview