Core Insight Each comparison proves that half of the remaining search space cannot contain the answer.
Common Pitfall Choose inclusive or exclusive bounds once and update them consistently.
Description
Design a time-based key-value data structure.
Constraints
- Time Complexity:
O(log n) - Space Complexity:
O(n)
Tags
hash-mapbinary-searchdesignstring
Implementation Plan Translate the invariant into these small, testable moves.
- Set the initial bounds.
- Compute a midpoint.
- Use the monotonic condition to discard one half.
- Return when found or when the bounds cross.
class TimeMap:
def __init__(self):
self.keyStore = {}
def set(self, key, value, timestamp):
if key not in self.keyStore:
self.keyStore[key] = []
self.keyStore[key].append([value, timestamp])
def get(self, key, timestamp):
res = ""
values = self.keyStore.get(key, [])
l, r = 0, len(values) - 1
while l <= r:
m = (l + r) // 2
if values[m][1] <= timestamp:
res = values[m][0]
l = m + 1
else:
r = m - 1
return res