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"
Constraints:
1 <= key.length, value.length <= 100key and value consist of lowercase English letters and digits.1 <= timestamp <= 107timestamp of set are strictly increasing.2 * 105 calls will be made to set and get.This approach uses a HashMap where each key points to a sorted list of timestamp-value pairs. The 'set' function appends the value along with the timestamp to the list associated with the key. The 'get' function retrieves the value at a particular timestamp by performing a binary search to find the rightmost timestamp less than or equal to the requested timestamp.
In the Python solution, we employ the 'bisect_right' function from the 'bisect' module to perform a binary search. The key-value pairs are stored such that each key corresponds to a list of (timestamp, value) tuples. The 'set' method stores the new data point in logarithmic time complexity due to the sorted insertion. The 'get' method uses binary search to efficiently find the largest timestamp less than or equal to the given timestamp.
JavaScript
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.
This approach is similar, but instead of using a helper library for the binary search, we implement it manually. This approach provides more control over the binary search process.
In C++, we use an unordered_map to keep track of all the keys. Every key maps to a vector of pairs, where each pair is a timestamp and its corresponding value. By manually coding the binary search, we find the accurate position to get the right timestamp in logarithmic time complexity.
Java
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.
| Approach | Complexity |
|---|---|
| HashMap with Sorted Timestamps | Time Complexity: |
| HashMap with Manual Binary Search | Time Complexity: |
Time Based Key-Value Store - Leetcode 981 - Python • NeetCode • 130,463 views views
Watch 9 more video solutions →Practice Time Based Key-Value Store with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor