577. Time Based Key-Value Store
Design a versioned key-value store: writes never overwrite old data — each one is stamped with a time, and reads ask what a key held as of some moment.
Implement a class TimeMap with two methods:
set(key, value, timestamp)— record thatkeyheldvalueat timetimestamp.get(key, timestamp)— return the value written forkeywith the largest timestamp that is less than or equal to the queriedtimestamp. If every version of the key is newer than the query, or the key was never set, return the empty string"".
Successive set calls for the same key arrive with strictly increasing timestamps, so each key's history is already in chronological order. Both methods should be fast even after hundreds of thousands of operations.
Example 1:
Input: set("foo","bar",1); get("foo",1); get("foo",3); set("foo","bar2",4); get("foo",4); get("foo",5)
Output: "bar", "bar", "bar2", "bar2"
Explanation: At time 1 foo is "bar". Asking at time 3 still sees "bar" — it is the newest version not after 3. From time 4 onward the answer is "bar2".
Example 2:
Input: set("login","alice",5); get("login",5); get("login",3); set("login","bella",8); get("login",7); get("login",100)
Output: "alice", "", "alice", "bella"
Explanation: The query at time 3 predates every version of "login", so it returns the empty string (an empty output line). At time 7 the newest version not after 7 is still "alice"; at time 100 it is "bella".
Constraints:
- 1 ≤ q ≤ 2 * 10⁵ total operations
- Keys and values are non-empty strings of letters and digits, length ≤ 100
- 1 ≤ timestamp ≤ 10⁷
- Timestamps in successive set calls for the same key are strictly increasing
Hints:
Group the data by key first: a hash map from key to that key's list of (timestamp, value) pairs. The strictly-increasing guarantee means each list is already sorted — no sorting needed.
get asks for the rightmost entry with timestamp <= t in a sorted list. That is a textbook binary search (bisect_right / upper_bound, then step one left).
Watch the two empty cases: the key is absent entirely, or even the oldest version is newer than the query. Both must return "".
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: set("foo","bar",1); get("foo",1); get("foo",3); set("foo","bar2",4); get("foo",4); get("foo",5)
Expected output: "bar", "bar", "bar2", "bar2"