981. Time Based Key-Value StoreMedium

Time Based Key-Value Store

MediumHash TableDesignBinary Search·GoogleAmazon

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.
set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
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"]

Constraints:

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 10⁷
All the timestamps timestamp of set are strictly increasing.
At most 2 * 10⁵ calls will be made to set and get.

Optimal Approach — Hash Map + Binary Search

O(1) Set, O(log N) Get

✂️

Searching a Timestamp Array

Time O(log N)Space O(N)

Because the problem guarantees that set calls have strictly increasing timestamps, any array we append to will automatically be sorted by timestamp! Thus, we can store values in a dictionary mapping keys to lists of [value, timestamp].

For the get() operation, we retrieve this array and run binary search to find the greatest timestamp that is less than or equal to the target timestamp.

1Access the list of pairs for the requested key.
2Initialize boundaries: l = 0, r = len(values) - 1.
3Calculate m = (l + r) // 2. If values[m].timestamp <= target, since the value is valid, we capture it in res. We then search to the right l = m + 1 to try and find an even closer timestamp!
4If values[m].timestamp > target, it's invalid (too far in the future). We must search to the left: r = m - 1.

READYPress ▶ or step forward to begin.

✓

—

values[v:t]

target_t

Executing Code

class TimeMap:

    def __init__(self):

        self.store = {} # key: list of [val, timestamp]

    def set(self, key, value, timestamp):

        if key not in self.store:

            self.store[key] = []

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

    def get(self, key, timestamp):

        res = ""

        values = self.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

Discussion

…

Loading comments…

LeetMotion