TARGET DECK: Leetcode FILE TAGS:
Intuition
- Each key can have multiple timestamp, values.
- However, to get something, that something must have a key.
- Otherwise return ""
- For the timestamps of the key, run Binary Search to get the first timestamp timestamp_prev.
- Then, return the value associated with that.
Cards
START Basic Front: Time Based Key-Value Store - LeetCode Back: Use Bisect or Binary Search on a list of (timestamp, value)
END
Complexity
Runtime
for binary search, where T is maximum number of timestamps for a given key.
Space
- , where K is the number of keys, and T is the number of timestamps.
- K keys, wherein the K keys hold up to T timestamps in total.
Code
from collections import defaultdict
class TimeMap:
def __init__(self):
self.hm = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.hm[key].append([timestamp, value])
def get(self, key: str, timestamp: int) -> str:
if key not in self.hm:
return ""
candidates = self.hm[key]
def binarySearch():
l, h = 0, len(candidates) - 1
candidate = None
while l <= h:
mid = (l + h) // 2
if timestamp == candidates[mid][0]:
return mid
elif timestamp > candidates[mid][0]:
candidate = mid
l = mid + 1
else:
h = mid - 1
return candidate
candidate = binarySearch()
if candidate is None:
return ""
return self.hm[key][candidate][1]