Time Based Key-Value Store
- 2 min read
- LC-Medium
- Binary-search
3 years ago
Solution
- Just store the tuple (value, timestamp) in a list where this list is the value of a defaultdict where key is the given key
- When doing a search, we either want the target, OR (if it's not found), we want the closest value that's less than the target, so just do a binary search
- Combine two conditions into one, i.e.
if values[mid][1] <= timestamp:- I.e. if our current timestamp is less than or equal to our target timestamp, update answer and update left pointer
- Else, just update right pointer, without updating the answer. This is because the condition
values[mid][1] > timestampviolates our condition that the most recent timestamp should be lesser than the target timestamp if the target timestamp wasn't found
- Combine two conditions into one, i.e.
- Read the constraints of the problem-- they're super helpful in figuring out that this is a binary search problem!!!
| Time | Space | Explanation |
|---|---|---|
O(log n) | O(1) |
class TimeMap:
def __init__(self):
self.store = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.store[key].append((value, timestamp))
def get(self, key: str, timestamp: int) -> str:
ans = ''
values = self.store[key]
l, r = 0, len(values) - 1
while l <= r:
mid = (l + r) // 2
if values[mid][1] <= timestamp:
ans = values[mid][0]
l = mid + 1
else:
r = mid - 1
return ans