981. Time Based Key-Value Store
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 keykey
with the valuevalue
at the given timetimestamp
.String get(String key, int timestamp)
Returns a value such thatset
was 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 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 <= 100
key
andvalue
consist of lowercase English letters and digits.1 <= timestamp <= 107
- All the timestamps
timestamp
ofset
are strictly increasing. - At most
2 * 105
calls will be made toset
andget
.
Imagine we have the following timestamps: [5, 10, 15]
.
If we query, say, 20
, upper_bound
returns end()
, so the result is the label for 15
(prev(end())
).
Now, if we query 3
, upper_bound
returns begin()
, and that means we do not have a label (the result is an empty string).
Another interesting case is when we query the exact timestamp, say, 10
. upper_bound will return 15
and prev(15)
will gives us the correct label. We could have used lower_bound
, but we will have to add an equality check.
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.