Problem Description

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 "".

Example 1:

  • 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"

My Idea

With this data structure it is important to implement an efficient get method. To do this we utilize binary search. The key, value and timestamp are stored in a dictionary where key is the key and the (timestamp,value) tuple is the value. Since we might be calling the get method with a timestamp that is between two values and we want to return the highest lower one, we take advantage of the fact that the right pointer of the binary search always points at exactly this element if the target is not part of the array itself. The only other modification is covering the cases that get was called with a key that is not part of the TimeMap or a timestamp that is lower than the lowest one stored.

My solution

class TimeMap:

    def __init__(self):
        self.storage = dict()

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.storage:
            return ""
        elif timestamp < self.storage[key][0][0]:
            return ""
        else:
            l=0
            r=len(self.storage[key])-1
            while(l<=r):
                mid = (l + r) // 2
                if self.storage[key][mid][0]>timestamp:
                    r=mid-1
                elif self.storage[key][mid][0]<timestamp:
                    l=mid+1
                else:
                    return self.storage[key][mid][1]
            return self.storage[key][r][1]