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