LeetCode Time Based key-Value Store Solution
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
1TimeMap timeMap = new TimeMap();
2
3timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.
4
5timeMap.get("foo", 1); // return "bar"
6
7timeMap.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".
8
9timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
10
11timeMap.get("foo", 4); // return "bar2"
12
13timeMap.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
.
Problem Link: https://leetcode.com/problems/time-based-key-value-store/
Solution
To look for the location pos
of the timestamp
entry, we must find the timestamp pair less than or equal to timestamp
.
Hence we repeatly update pos
to mid
, if the timestamp
at histories[mid]
is less than or equal to the given timestamp
(histories[mid][0] <= timestamp
), to find the greatest timestamp
less than or equal to timestamp
.
In the binary search loop, we will continue to find the desired timestamp
on the right side of the loop if histories[mid][0] <= timestamp
,
and search the left side otherwise.
Implementation
1class TimeMap(object):
2
3 def __init__(self):
4 self.histories = dict()
5
6 def set(self, key, value, timestamp):
7 if not key in self.histories:
8 self.histories[key] = []
9 self.histories[key].append([timestamp, value])
10
11
12 def get(self, key, timestamp):
13 if not key in self.histories: return ""
14 left, right, pos = 0, len(self.histories[key])-1, -1
15 while left <= right:
16 mid = (left+right) // 2
17 if self.histories[key][mid][0] <= timestamp:
18 left = mid + 1
19 pos = mid
20 else:
21 right = mid - 1
22 if pos == -1: return ""
23 return self.histories[key][pos][1]