Time Based Key-Value Store
Create a time-based key-value store class that supports two operations: put and get. The put operation takes three parameters: key, value, and timestamp. The get operation takes two parameters: key and timestamp. The get operation should return the value of the key at the given timestamp if it exists, otherwise it should return -1.
Constraints:
- 1 <= key <= 10^5
- 1 <= value <= 10^5
- 1 <= timestamp <= 10^7
- At most 10^5 calls to put and get
Examples:
Input: ["TimeKeyStore","put","get","get","put","get"] [["foo","bar",1],["foo",1],["foo",3],["foo",2],["foo","bar",4],["foo",4]]
Output: [null,null,"bar","bar",null,"bar"]
Explanation: TimeKeyStore timeKeyStore = new TimeKeyStore(); timeKeyStore.put("foo","bar",1); timeKeyStore.get("foo",1); timeKeyStore.get("foo",3); timeKeyStore.put("foo","bar",4); timeKeyStore.get("foo",4);
Solutions
Hash Table
We use a hash table to store the key-value pairs. For each key, we store a list of values and timestamps. When we put a new value, we append it to the list. When we get a value, we use binary search to find the latest value that is less than or equal to the given timestamp.
class TimeKeyStore:
def __init__(self):
self.map = {}
def put(self, key:
str, value:
str, timestamp:
int) -> None:
if key not in self.map:
self.map[key] = []
self.map[key].append([value, timestamp])
def get(self, key:
str, timestamp:
int) -> str:
if key not in self.map:
return "-1"
values = self.map[key]
left, right = 0, len(values) - 1
while left <= right:
mid = (left + right) // 2
if values[mid][1] <= timestamp:
left = mid + 1
else:
right = mid - 1
if right == -1:
return "-1"
return values[right][0]Follow-up:
How would you optimize the solution if the number of keys is very large?
