Time Based Key-Value Store medium

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps. Implement the TimeMap class:

• TimeMap(): Initializes the object.
• set(key: str, value: str, timestamp: int): Stores the key key with the value value at the given time timestamp.
• get(key: str, timestamp: int): Returns a value such that it was stored at a time less than or equal to timestamp. If there are multiple such values, it returns the one associated with the largest timestamp less than or equal to timestamp. If there is no value, 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 ie "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"

Example 2

Input ["TimeMap", "set", "set", "get", "get", "get"] [[], ["love", "high", 10], ["love", "low", 20], ["love", 5], ["love", 10], ["love", 15]]

Output [null, null, null, "", "high", "high"]

Explanation TimeMap timeMap = new TimeMap(); timeMap.set("love", "high", 10); timeMap.set("love", "low", 20); timeMap.get("love", 5); // return "" because there is no value with timestamp <= 5 timeMap.get("love", 10); // return "high" timeMap.get("love", 15); // return "high"

Steps

1. Data Structure: Use a dictionary to store the key-value pairs. The value for each key will be a list of (timestamp, value) tuples, sorted by timestamp. This allows efficient retrieval of values based on timestamp.

2. set(key, value, timestamp): Append the (timestamp, value) tuple to the list associated with the given key.

3. get(key, timestamp):

   • If the key doesn't exist, return "".
   • Perform a binary search on the list of (timestamp, value) tuples for the key.
   • Find the largest timestamp less than or equal to the given timestamp.
   • Return the corresponding value.

Explanation

The key to efficiency in this problem is using a sorted list of timestamps for each key. This allows us to use binary search in the get method, resulting in logarithmic time complexity. A simple linear scan would lead to a much slower solution. The binary search efficiently finds the latest value within the specified timestamp constraint.

Code

class TimeMap:

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

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

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

        values = self.data[key]
        l, r = 0, len(values) - 1
        res = ""
        while l <= r:
            mid = (l + r) // 2
            if values[mid][0] <= timestamp:
                res = values[mid][1]
                l = mid + 1
            else:
                r = mid - 1
        return res

Complexity

• Time Complexity:

  • set: O(1) on average (amortized), O(n) in the worst case if many elements need to be shifted for insertion. In practice, O(1) is a reasonable approximation given many inserts.
  • get: O(log n), where n is the number of (timestamp, value) pairs associated with the key. This is due to the binary search.

• Space Complexity: O(N), where N is the total number of (key, value, timestamp) entries stored.