0032 - Time Based Key Value Store

Implement a time-based key-value data structure that supports:

Storing multiple values for the same key at specified time stamps Retrieving the key's value at a specified timestamp Implement the TimeMap class:

TimeMap() Initializes the object. void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. String get(String key, int timestamp) Returns the most recent value of key if set was previously called on it and the most recent timestamp for that key prev_timestamp is less than or equal to the given timestamp (prev_timestamp <= timestamp). If there are no values, it returns "". Note: For all calls to set, the timestamps are in strictly increasing order.

Example 1:

Input: ["TimeMap", "set", ["alice", "happy", 1], "get", ["alice", 1], "get", ["alice", 2], "set", ["alice", "sad", 3], "get", ["alice", 3]]

Output: [null, null, "happy", "happy", null, "sad"]

Explanation: TimeMap timeMap = new TimeMap(); timeMap.set("alice", "happy", 1); // store the key "alice" and value "happy" along with timestamp = 1. timeMap.get("alice", 1); // return "happy" timeMap.get("alice", 2); // return "happy", there is no value stored for timestamp 2, thus we return the value at timestamp 1. timeMap.set("alice", "sad", 3); // store the key "alice" and value "sad" along with timestamp = 3. timeMap.get("alice", 3); // return "sad"

Solution¶

• The TimeMap is like a time-traveling dictionary that stores values with timestamps.
• When setting, it maintains a list of value-timestamp pairs for each key. - When getting, it uses binary search to find either an exact timestamp match or the most recent value before the target time.
• If no value exists before the target time, it returns an empty string.
• The binary search makes lookups efficient with O(log n) time complexity.

In [9]:

class TimeMap:
    def __init__(self):
        self.store={} #key:[list of [val,timestamp]]
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key]=[]
        self.store[key].append([value,timestamp])

    def get(self, key: str, timestamp: int) -> str:
        res=""
        values=self.store.get(key,[])
        #binary search
        l,r=0,len(values)-1
        while l<=r:
            m=(l+r)//2
            if values[m][1]==timestamp:
                return values[m][0]
            elif values[m][1]>timestamp:
                r=m-1
            else:
                res=values[m][0]
                l=m+1
        return res

In [10]:

timeMap = TimeMap()
timeMap.set("alice", "happy", 1)
timeMap.get("alice", 1)

Out[10]:

'happy'