The problem
Design a store that keeps several values for the same key, each stamped with a time. set(key, value, timestamp) stores a value; get(key, timestamp) returns the value set at the latest time at or before timestamp, or "" if there is none.
The timestamps passed to set always increase.
Examples
01
- Input
["TimeMap", "set", "get", "get", "set", "get", "get"] [ [], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5] ]
- Output
[null, null, "bar", "bar", null, "bar2", "bar2"]
Constraints
- 1 ≤ key.length, value.length ≤ 100
- 1 ≤ timestamp ≤ 10⁷
- At most 2 × 10⁵ calls in total.
The idea
Keep, for each key, its list of (timestamp, value) pairs. Because timestamps only increase, appending keeps every list sorted — for free.
get then binary searches that list for the first entry later than the requested time; the entry just before it is the latest one at or before that time. No entry before it means the answer is "".
- Time
- O(1) to set, O(log n) to get
- Space
- O(total number of sets)
Solution · every language run against every case
class TimeMap: def __init__(self): # key -> list of (timestamp, value). Timestamps arrive increasing, so each list is sorted. self.store = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.store[key].append((timestamp, value)) def get(self, key: str, timestamp: int) -> str: entries = self.store.get(key, []) lo, hi = 0, len(entries) # find the first entry later than timestamp while lo < hi: mid = (lo + hi) // 2 if entries[mid][0] <= timestamp: lo = mid + 1 else: hi = mid return entries[lo - 1][1] if lo > 0 else "" # the one before it is the latest in time