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
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
.
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]
How does quick sort divide the problem into subproblems?
Which technique can we use to find the middle of a linked list?
Solution Implementation
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.