⏱️981. Time Based Key-Value Store

Medium | Grind 75 | January 19th Thursday, 2023

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() Initializes the object of the data structure.

• 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 a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Constraints:

• 1 <= key.length, value.length <= 100

• key and value consist of lowercase English letters and digits.

• 1 <= timestamp <= 10^7

• All the timestamps timestamp of set are strictly increasing.

• At most 2 * 10^5 calls will be made to set and get

First Tab

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

SOLUTION

The problem requires us to store multiple values for the same key, which can be achieved by using a dictionary of an array of tuples. The set method can be implemented by creating a new key-value entry in the dictionary if the key is seen for the first time, otherwise, appending to the already existing key value. The get method, however, requires a more efficient algorithm due to the large number of calls that will be made. Given that the time stamps are always in increasing order, we can use a binary search to find the previous largest value. The key to using the binary search is knowing how to handle the case where the exact timestamp is not found. By using the left and rightmost index of the list, we can find the mid and adjust the value of the left and right index accordingly. The right index will stop moving once it has found a value lower than the timestamp unless every value in the list is greater than the timestamp. We return the element at the right index of the list if the right index is not negative(meaning no element in the list is smaller than the timestamp).

class TimeMap:
    """ a dictionary containing an array of tuples"""
    def __init__(self):
        # only need a dictionary. Append array of tuples only when set method is called.
        self.dict = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key in self.dict: 
            self.dict[key].append((timestamp, value))
        else: 
            self.dict[key] = [(timestamp, value)]

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.dict: 
            return ""
        
        items = self.dict[key]

        left, right = 0, len(items)-1

        while left <= right: 
            mid = left + (right - left)//2

            if items[mid][0] == timestamp:
                return items[mid][1]
            
            if timestamp < items[mid][0]: 
                right = mid - 1
            
            else: 
                left = mid + 1
        
        if right >=0 : 
            return items[right][1]
        
        return ""




# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

TIME AND SPACE COMPLEXITY

TIME: The time complexity for each method is different. set: If the key is already in the dictionary, we append the current values resulting in time complexity of O(1). If the key does not exist in the dictionary, we add a new key-value entry which is also O(1). Therefore the set methods have a time complexity of O(1). get: We implemented a binary search that has a time complexity of O(logn)

SPACE: O(n) where n is the total number of entries to be set in the data structure. Our dictionary stores a key-value pair. The value is an array of tuples.

* Written with help from ChatGPT *