Time Based Key-Value Store

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"

---

A brute force solution would be to use a HashMap and hash each key with a list of tuples containing its respective values and timestamps.  If the set function was called, we would append the new value and timestamp to the key's list in the HashMap and if the get function was called, we would traverse the list backward and return the first value with a timestamp less than or equal to the one that was input.

One important thing to note, however, is that in the constraints it says that the timestamps are strictly increasing.  That means each list of tuples that we create will be in sorted order without duplicates.

Knowing this, we can implement a binary search in our get function to drop the time complexity down from O(N) to O(Log(N)).  The set function will stay the same as the brute force approach.

---

Let's start by initializing our store.

    def __init__(self):
        self.store = {}

---

Next, we'll create our set function.

    def set(self, key: str, value: str, timestamp: int) -> None:

 

If the current key is not already in the store, then we will place it there with a list containing an initial tuple of the current value and timestamp.

        if key not in self.store:
            self.store[key] = [(value, timestamp)]

 

Otherwise, we'll append the current value and timestamp to its already created list.

        else:
            self.store[key].append((value, timestamp))

---

Now let's create our get method.

    def get(self, key: str, timestamp: int) -> str:

 

If the current key isn't in the store then we will return an empty string.

        if key not in self.store:
            return ""

 

Otherwise, we'll grab the list of tuples from the key in the HashMap.

        values = self.store[key]

 

If the current timestamp is less than the first value in our list then we don't have a value less than or equal to the timestamp that we can return.

If this is the case, we will return an empty string.

        if timestamp < values[0][1]:
            return ""

 

Also, if the current timestamp is greater than the last value in the list then the last value would be the first value less than or equal to the timestamp so we can return it.

        if timestamp > values[-1][1]:
            return values[-1][0]

 

Otherwise, we'll run our binary search, so let's set our pointers.

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

 

We're trying to find the first timestamp less than or equal to the target timestamp, so we won't terminate our search until our pointers overlap.

        while left <= right:

 

Let's set a mid pointer to the index at the mean of our two pointers.

            mid = (left + right) // 2

 

If that middle timestamp equals the target one, we'll return the middle value.

            if values[mid][1] == timestamp:
                return values[mid][0]

 

If that middle value is less than the target timestamp, we'll abandon the left partition of our current search space.

            elif values[mid][1] < timestamp:
                left = mid + 1

 

Otherwise, if it is greater then we'll abandon the right partition instead.

            else:
                right = mid - 1

 

Once our pointers have overlapped, that would mean two things; either the left pointer passed the last timestamp less than the target or the right pointer passed the last timestamp greater than the target.

In either scenario, the target would be one index behind the left pointer which would be where the right pointer ended up at.

We'll return that value.

        return values[right][0]

---