Time Based Key-Value Store
Problem Description
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 keykeywith the valuevalueat the given timetimestamp.String get(String key, int timestamp)Returns a value such thatsetwas called previously, withtimestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largesttimestamp_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
Constraints:
1 <= key.length, value.length <= 100keyandvalueconsist of lowercase English letters and digits.- 1 <= timestamp <= 107
- All the timestamps
timestampofsetare strictly increasing. - At most 2 * 105 calls will be made to
setandget.
Solve it on LeetCode
Approaches
1. Using HashMap with Linear Search (Basic)
Intuition:
The simplest approach to solve this problem is to use a HashMap where the keys are strings and the values are lists of pairs (timestamp, value). To perform the get operation, we can iterate over the list for a particular key and find the largest timestamp that is less than or equal to the given timestamp.
Steps:
- We'll use a
HashMap<String, List<Pair<Integer, String>>>to store keys with their associated timestamp-value pairs. - For the
setoperation, we'll add a pair of(timestamp, value)to the list corresponding to the key. - For the
getoperation, we'll iterate through the list associated with the given key and check for the largest timestamp that is less than or equal to the given timestamp.
Code:
- Time Complexity:
set: O(1) amortized time complexity.get: O(n) where n is the number of timestamp-value pairs for the key.- Space Complexity: O(n) to store all timestamp-value pairs.
2. Using HashMap with Binary Search (Optimal)
Intuition:
An optimized approach improves the get operation by using binary search. Given that the timestamps are stored in sorted order by insertion, we can utilize binary search to quickly locate the largest timestamp that is less than or equal to the given timestamp.
Steps:
- Similar to the previous approach, we'll use a
HashMapwith lists of pairs for each key. - For the
setoperation, the implementation remains the same. - For the
getoperation, use binary search on the list of pairs for the given key instead of linear search.
Code:
- Time Complexity:
set: O(1) amortized time complexity.get: O(log n), where n is the number of timestamp-value pairs for the key due to binary search.- Space Complexity: O(n) to store all timestamp-value pairs.