Design timestamped key-value map
Company: Character.AI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Design a class that supports insert(key, value, timestamp) and get(key, timestamp) where get returns the value whose timestamp is the smallest timestamp ≥ the given timestamp, assuming inserts arrive in increasing timestamp order. Follow-up: How would you change the design if inserts arrive out of order (timestamps not strictly increasing)?
Quick Answer: This question evaluates the ability to design a timestamped key-value data structure, testing competencies in time-based indexing, ordered retrieval, and data structure selection for efficient timestamp queries.
Implement a function to process operations on a timestamped key-value map. It supports two operations: (1) insert(key, value, timestamp): store the value for key at the given timestamp; (2) get(key, timestamp): return the value for key whose timestamp is the smallest timestamp greater than or equal to the given timestamp. If no such timestamp exists for the key, return null. Assume that all insert operations arrive in nondecreasing timestamp order across all keys. The function should return a list of results for all get operations in the order they appear.
Constraints
- 1 <= len(operations) <= 200000
- Each operation is either ["insert", key:str, value:str, timestamp:int] or ["get", key:str, timestamp:int]
- All insert operations appear in nondecreasing timestamp order (timestamps may be equal)
- 0 <= timestamp <= 1e9
- 1 <= len(key), len(value) <= 50
- The function returns results for get operations only; insert operations produce no direct output
Solution
from bisect import bisect_left
def time_ceiling_kv(operations: list[list]) -> list:
"""
Process a sequence of ["insert", key, value, timestamp] and ["get", key, timestamp].
Returns a list with results for get operations; missing results are None.
Assumes all inserts are given in nondecreasing timestamp order.
"""
store = {} # key -> (timestamps:list[int], values:list[str])
out = []
for op in operations:
if not op:
continue
cmd = op[0]
if cmd == "insert":
if len(op) != 4:
raise ValueError("insert expects 4 fields: ['insert', key, value, timestamp]")
_, k, v, t = op
pair = store.get(k)
if pair is None:
store[k] = ([t], [v])
else:
ts, vs = pair
ts.append(t) # valid due to nondecreasing timestamp assumption
vs.append(v)
elif cmd == "get":
if len(op) != 3:
raise ValueError("get expects 3 fields: ['get', key, timestamp]")
_, k, t = op
pair = store.get(k)
if pair is None:
out.append(None)
else:
ts, vs = pair
i = bisect_left(ts, t) # first index with ts[i] >= t
if i < len(ts):
out.append(vs[i])
else:
out.append(None)
else:
raise ValueError(f"unknown operation: {cmd}")
return out
Explanation
Maintain, for each key, a pair of parallel arrays: timestamps (sorted) and values. Because all inserts arrive in nondecreasing timestamp order, appending keeps the timestamps sorted. For a get(key, t) query, perform a binary search with bisect_left to find the smallest index i such that timestamps[i] >= t; if it exists, return values[i]; otherwise return None. If inserts arrive out of order, you would insert timestamps and values at the appropriate positions using bisect.insort (O(log m) per insert plus O(m) shifts in arrays) or use a balanced tree/skip list to keep inserts and queries both O(log m), where m is the number of entries for that key.
Time complexity: Insert: O(1) amortized per operation (append); Get: O(log m) per query where m is the number of entries for the key. Space complexity: O(N) where N is the total number of inserted entries.
Hints
- Map each key to a sorted list of timestamps and a parallel list of values.
- Because inserts are in nondecreasing timestamp order, you can append to each key's lists to keep them sorted.
- Use binary search (bisect_left) on the timestamps list to find the first index with timestamp >= query.
- If inserts were out of order, maintain each key's timestamps in sorted order via bisect.insort or use a balanced BST.