Katkat
Back

Implement time-versioned KV store with restore

PerplexitySoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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