time_based_key_value_store
1from collections import defaultdict 2 3 4# @leet start 5from sortedcontainers import SortedList 6 7 8class TimeMap: 9 """ 10 This class defines a time-based key-value store that can store 11 multiple values for the same key at different timestamps, and retrieve 12 the key's value at a certain timestamp. 13 14 So, set takes 3 params, key, value, timestamp and sets the key to value 15 at the given timestamp. 16 17 Get takes 2 params, key and timestamp, and returns a matching value 18 where prev_timestamp <= timestamp. 19 20 To implement this, we store the timestamps in a dict of key -> SortedList 21 and the values in a dict of (timestamp, key) -> value. 22 When we set, we set the key -> timestamp and the (timestamp, key) -> value. 23 When getting, we check the index of the timestamp to get by bisecting right 24 on the key with the given timestamp, and returning the previous index. 25 26 Finally, if that index is inbounds, we use the (timestamp, key) pair to get the value 27 If its not in bounds, we return "". 28 """ 29 30 def __init__(self): 31 self.timestamps = defaultdict(lambda: SortedList()) 32 self.values = {} 33 34 def set(self, key: str, value: str, timestamp: int) -> None: 35 self.timestamps[key].add(timestamp) 36 self.values[(timestamp, key)] = value 37 38 def get(self, key: str, timestamp: int) -> str: 39 idx = self.timestamps[key].bisect_right(timestamp) - 1 40 if 0 <= idx < len(self.timestamps[key]): 41 timestamp = self.timestamps[key][idx] 42 return self.values[(timestamp, key)] 43 else: 44 return "" 45 46 47# Your TimeMap object will be instantiated and called as such: 48# obj = TimeMap() 49# obj.set(key,value,timestamp) 50# param_2 = obj.get(key,timestamp) 51# @leet end 52 53 54def test(): 55 assert 2 + 2 == 4
9class TimeMap: 10 """ 11 This class defines a time-based key-value store that can store 12 multiple values for the same key at different timestamps, and retrieve 13 the key's value at a certain timestamp. 14 15 So, set takes 3 params, key, value, timestamp and sets the key to value 16 at the given timestamp. 17 18 Get takes 2 params, key and timestamp, and returns a matching value 19 where prev_timestamp <= timestamp. 20 21 To implement this, we store the timestamps in a dict of key -> SortedList 22 and the values in a dict of (timestamp, key) -> value. 23 When we set, we set the key -> timestamp and the (timestamp, key) -> value. 24 When getting, we check the index of the timestamp to get by bisecting right 25 on the key with the given timestamp, and returning the previous index. 26 27 Finally, if that index is inbounds, we use the (timestamp, key) pair to get the value 28 If its not in bounds, we return "". 29 """ 30 31 def __init__(self): 32 self.timestamps = defaultdict(lambda: SortedList()) 33 self.values = {} 34 35 def set(self, key: str, value: str, timestamp: int) -> None: 36 self.timestamps[key].add(timestamp) 37 self.values[(timestamp, key)] = value 38 39 def get(self, key: str, timestamp: int) -> str: 40 idx = self.timestamps[key].bisect_right(timestamp) - 1 41 if 0 <= idx < len(self.timestamps[key]): 42 timestamp = self.timestamps[key][idx] 43 return self.values[(timestamp, key)] 44 else: 45 return ""
This class defines a time-based key-value store that can store multiple values for the same key at different timestamps, and retrieve the key's value at a certain timestamp.
So, set takes 3 params, key, value, timestamp and sets the key to value at the given timestamp.
Get takes 2 params, key and timestamp, and returns a matching value where prev_timestamp <= timestamp.
To implement this, we store the timestamps in a dict of key -> SortedList and the values in a dict of (timestamp, key) -> value. When we set, we set the key -> timestamp and the (timestamp, key) -> value. When getting, we check the index of the timestamp to get by bisecting right on the key with the given timestamp, and returning the previous index.
Finally, if that index is inbounds, we use the (timestamp, key) pair to get the value If its not in bounds, we return "".