Time Based Key-Value Store

Problem Statement

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:
time_map = TimeMap()
time_map.set("alice", "happy", 1)  # store the key "alice" and value "happy" along with timestamp = 1.
time_map.get("alice", 1)           # return "happy"
time_map.get("alice", 2)           # return "happy", there is no value stored for timestamp 2, thus we return the value at timestamp 1.
time_map.set("alice", "sad", 3)    # store the key "alice" and value "sad" along with timestamp = 3.
time_map.get("alice", 3)           # return "sad"

Constraints:

1 <= key.length, value.length <= 100
key and value only include lowercase English letters and digits.
1 <= timestamp <= 1000

You should aim for a solution with O(1) time for set(), O(log n) time for get(), and O(m * n) space, where n is the total number of values associated with a key, and m is the total number of keys.

Recommended Time and Space Complexity

Hint 1

Can you think of a data structure that is useful for storing key-value pairs? Perhaps a hash-based data structure where we not only store unique elements but also associate additional information with each element?

Hint 2

We store key-value pairs in a hash map. In this case, we store the keys as usual, but instead of a single value, we store a list of values, each paired with its corresponding timestamp. This allows us to implement the set() method in O(1). How can you leverage this hash map to implement the get() method?

Hint 3

A brute force solution would involve linearly going through every value associated with the key and returning the most recent value with a timestamp less than or equal to the given timestamp. This approach has a time complexity of O(n) for each get() call. Can you think of a better way? Since the timestamps in the value list are sorted in ascending order by default, maybe an efficient searching algorithm could help.

Hint 4

We can use binary search because the timestamps in the values list are sorted in ascending order. This makes it straightforward to find the value with the most recent timestamp that is less than or equal to the given timestamp.

Solution

Brute Force

class TimeMap:
    def __init__(self):
        self.key_store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.key_store:
            self.key_store[key] = {}
        if timestamp not in self.key_store[key]:
            self.key_store[key][timestamp] = []
        self.key_store[key][timestamp].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.key_store:
            return ""
        seen = 0

        for time in self.key_store[key]:
            if time <= timestamp:
                seen = max(seen, time)
        return "" if seen == 0 else self.key_store[key][seen][-1]

Time complexity: O(1) for set() and O(n) for get(). Space complexity: O(m * n)

Binary Search (Sorted Map)

from sortedcontainers import SortedDict
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.m = defaultdict(SortedDict)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key][timestamp] = value

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.m:
            return ""

        timestamps = self.m[key]
        idx = timestamps.bisect_right(timestamp) - 1

        if idx >= 0:
            closest_time = timestamps.iloc[idx]
            return timestamps[closest_time]
        return ""

Time complexity: O(1) for set() and O(log n) for get(). Space complexity: O(m * n)

Binary Search (Array)

class TimeMap:
    def __init__(self):
        self.key_store = {}  # key : list of [val, timestamp]

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

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

Time complexity: O(1) for set() and O(log n) for get(). Space complexity: O(m * n)