KV Store with Timestamps and Restore

Implement a key-value store where set, get, and delete operations are timestamp-aware. A later part adds restore behavior that must find the correct historical timestamp state. Temporal Key-Value Store (Online Assessment) Overview This Perplexity OA is a two-part CoderPad exercise built around a temporal key-value store. Part 1 asks you to implement point-in-time get, set, and delete operations efficiently. Part 2 extends the store with a restore operation that rolls the entire store back to an earlier timestamp without breaking historical reads. The version to optimize for is the one where operations may arrive in any timestamp order, and sortedcontainers is available in CoderPad. That changes the data-structure choice: an append-only list is no longer enough you want each key's history kept in sorted timestamp order sortedcontainers makes the implementation much cleaner than manually inserting into Python lists Read the starter code carefully before writing anything. The intended solution is efficient, but it does not require exotic tricks if you pick the right ordered container. class TemporalKVStore: """ A key-value store with point-in-time reads. """ def __init__(self): """Initialize the store.""" pass def get(self, key: str, timestamp: int): """ Return the value for key at the given timestamp. If the key does not exist at that time, return None. """ pass def set(self, key: str, value: str, timestamp: int) -> None: """ Record that key has the given value starting at timestamp. """ pass def delete(self, key: str, timestamp: int) -> bool: """ Delete the key at timestamp. Returns: True if the key existed at that timestamp, False otherwise. """ pass Part 1: Implement the Temporal Store Suggested time: 30-60 minutes The starter file is src/temporal_kv_store.py. The OA asks you to study the starter code first, then implement: __init__ get set delete You should spend a few minutes understanding the starter code before coding, because misunderstandings about the data model will slow you down much more than the implementation itself. Core Behavior The store keeps a history of values for each key instead of only the latest value. set(key, value, timestamp) records a new version for key get(key, timestamp) returns the latest value whose write time is <= timestamp delete(key, timestamp) marks the key as deleted starting at timestamp Operations may arrive in any timestamp order If the most recent event at or before timestamp is a delete, get should return None This is essentially a point-in-time configuration store: reads should answer "what did this key look like at timestamp t?" Example kv = TemporalKVStore() kv.set("feature_x", "disabled", 5) kv.set("feature_x", "enabled", 1) # earlier timestamp inserted later assert kv.get("feature_x", 1) == "enabled" assert kv.get("feature_x", 4) == "enabled" assert kv.get("feature_x", 5) == "disabled" assert kv.get("feature_x", 999) == "disabled" assert kv.delete("feature_x", 8) is True assert kv.get("feature_x", 8) is None assert kv.get("feature_x", 7) == "disabled" assert kv.delete("does_not_exist", 9) is False Performance Notes from the OA The Part 1 benchmark interleaves a large number of operations: 200,000 get operations 200,000 set operations 100,000 delete operations Around 90% of operations hit a single "hot" key Aim for a total benchmark time of roughly 10 seconds or less in CoderPad. The takeaway is that a naive linear scan per get will likely be too slow on the hot key. Recommended Approach Use an ordered history per key: store[key] -> SortedList[(timestamp, sequence, value_or_tombstone)] timestamp keeps events ordered by logical time sequence breaks ties when multiple operations land on the same timestamp get uses predecessor search to find the rightmost event with event_timestamp <= timestamp That gives the right complexity profile: set: O(log n) get: O(log n) for one key's history delete: O(log n) to check current existence, then O(log n) insert This is enough to handle the benchmark well even for the hot key, and it stays correct when earlier timestamps arrive late. Python Solution from itertools import count from typing import Optional from sortedcontainers import SortedList class TemporalKVStore: def __init__(self): # key -> SortedList[(timestamp, sequence, value_or_none)] # value None is a tombstone representing deletion. # sequence makes same-timestamp events deterministic. self.store: dict[str, SortedList[tuple[int, int, Optional[str]]]] = {} self._sequence = count() def _insert_event(self, key: str, timestamp: int, value: Optional[str]) -> None: if key not in self.store: self.store[key] = SortedList() self.store[key].add((timestamp, next(self._sequence), value)) def _find_value( self, history: SortedList[tuple[int, int, Optional[str]]], timestamp: int, ) -> Optional[str]: idx = history.bisect_right((timestamp, float("inf"), "")) - 1 if idx < 0: return None return history[idx][2] def get(self, key: str, timestamp: int) -> Optional[str]: history = self.store.get(key) if not history: return None return self._find_value(history, timestamp) def set(self, key: str, value: str, timestamp: int) -> None: self._insert_event(key, timestamp, value) def delete(self, key: str, timestamp: int) -> bool: history = self.store.get(key) if not history: return False current_value = self._find_value(history, timestamp) if current_value is None: return False self._insert_event(key, timestamp, None) return True This is the cleanest interview story for this OA version: keep each key's history sorted by timestamp use predecessor queries for get insert into the ordered structure for set and delete if duplicate timestamps are possible, add a monotonic sequence number so later inserted events win deterministically If you mention sortedcontainers, call out that it is a third-party dependency. If the interviewer disallows it, the fallback is a manually maintained sorted list plus bisect, or a balanced-tree equivalent in another language. Part 2: Add Restore Support Suggested time: 20-30 minutes Part 2 introduces a common configuration-store workflow: rolling the entire store back to a known-good point in time after a bad change. Implement restore according to the docstring in the starter code. A representative shape is: def restore(self, timestamp: int, restore_at_timestamp: int) -> None: """ At time `timestamp`, restore the whole store so that every key matches the value it had at `restore_at_timestamp`. Historical reads before `timestamp` must still work. The restore behaves like a batch of writes/deletes recorded at `timestamp`. """ pass Expected Semantics At restore time, every key should look exactly as it did at the target timestamp: If a key had value "on" at restore_at_timestamp, it should have value "on" at timestamp If a key did not exist at restore_at_timestamp, it should be deleted at timestamp Historical queries for times before the restore timestamp should still return the original pre-restore history Existing events after the restore timestamp should still take effect for later reads Because this OA version allows out-of-order timestamps, restore(10, 5) is just another batch of events inserted at logical time 10. If there is already a write at time 12, that later write should still win for queries at 12 and beyond. Example kv = TemporalKVStore() kv.set("a", "v3", 12) kv.set("a", "v1", 1) kv.set("a", "v2", 5) kv.set("b", "keep", 6) kv.delete("b", 7) kv.restore(10, 5) assert kv.get("a", 10) == "v2" # restored from time 5 assert kv.get("a", 11) == "v2" assert kv.get("a", 12) == "v3" # existing later write still applies assert kv.get("b", 10) is None # b did not exist at time 5 assert kv.get("a", 6) == "v2" # old history still queryable assert kv.get("b", 6) == "keep" assert kv.get("b", 8) is None Recommended Approach Because the benchmark performs only a small number of restores, a straightforward implementation is usually enough: Track the set of all keys ever seen. For each key, compute its value at restore_at_timestamp using the same predecessor-search helper as get. Compute the key's current value at timestamp. If the two differ, insert a new event at timestamp: a normal value event if the key existed at the restore point a tombstone if the key did not exist at the restore point This preserves full history while making reads at timestamp and later observe the restored snapshot until a later event overrides it. Python Solution from itertools import count from typing import Optional from sortedcontainers import SortedList class TemporalKVStore: def __init__(self): self.store: dict[str, SortedList[tuple[int, int, Optional[str]]]] = {} self.all_keys: set[str] = set() self._sequence = count() def _insert_event(self, key: str, timestamp: int, value: Optional[str]) -> None: if key not in self.store: self.store[key] = SortedList() self.store[key].add((timestamp, next(self._sequence), value)) self.all_keys.add(key) def _find_value( self, history: SortedList[tuple[int, int, Optional[str]]], timestamp: int, ) -> Optional[str]: idx = history.bisect_right((timestamp, float("inf"), "")) - 1 if idx < 0: return None return history[idx][2] def get(self, key: str, timestamp: int) -> Optional[str]: history = self.store.get(key) if not history: return None return self._find_value(history, timestamp) def set(self, key: str, value: str, timestamp: int) -> None: self._insert_event(key, timestamp, value) def delete(self, key: str, timestamp: int) -> bool: history = self.store.get(key) if not history: return False current_value = self._find_value(history, timestamp) if current_value is None: return False self._insert_event(key, timestamp, None) return True def restore(self, timestamp: int, restore_at_timestamp: int) -> None: for key in self.all_keys: history = self.store.get(key) if not history: continue restored_value = self._find_value(history, restore_at_timestamp) current_value = self._find_value(history, timestamp) if restored_value == current_value: continue self._insert_event(key, timestamp, restored_value) The important idea is that restore does not mutate or erase old history. It inserts new events at the restore timestamp. Once you store histories in sorted order, this stays correct even when the overall operation stream is not chronological.