DSA problem
Time Based Key-Value Store
Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key's value at a certain timestamp. Implement the TimeMap class with two methods.
TimeMap() initializes the object of the data structure. set(key, value, timestamp) stores the key key with value value at the given timestamp. get(key, timestamp) returns the value associated with key such that set was called previously with a timestamp_prev <= timestamp. If there are multiple such values, return the value associated with the largest timestamp_prev. If there are no values, return the empty string "".
The crucial observation is that all timestamps passed to set are strictly increasing — this is part of the problem's contract. That means for any single key, the list of (timestamp, value) entries is already sorted by timestamp simply by virtue of insertion order. So set is a constant-time append, and get reduces to a binary search for the largest timestamp not exceeding the query.
The natural backing structure is a hash map from key to a list of (timestamp, value) pairs. set appends to the list in O(1). get runs binary search on that list, finding the rightmost entry with timestamp ≤ query in O(log n). Overall time is O(1) per set and O(log n) per get; space is O(N) for N total set calls. The strictly-monotonic-timestamps constraint is what allows binary search instead of a balanced BST.
Examples
["TimeMap","set","get","get","set","get","get"]
[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]][null,null,"bar","bar",null,"bar2","bar2"]["TimeMap","set","set","get"]
[[],["love","high",10],["love","low",20],["love",5]][null,null,null,""]["TimeMap","get"]
[[],["nope",1]][null,""]Constraints
- 1 <= key.length, value.length <= 100
- key and value consist of lowercase English letters and digits.
- 1 <= timestamp <= 10^7
- All the timestamps timestamp of set are strictly increasing.
- At most 2 * 10^5 calls will be made to set and get.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.