Time Based Key-Value Store
Problem
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"
Pseudocode
- don't understand code, please review
Solution
var TimeMap = function () {
this.map = new Map();
};
/**
* @param {string} key
* @param {string} value
* @param {number} timestamp
* @return {void}
*/
TimeMap.prototype.set = function (key, value, timestamp) {
if (!this.map.has(key)) {
this.map.set(key, []);
}
this.map.get(key).push([timestamp, value]);
};
/**
* @param {string} key
* @param {number} timestamp
* @return {string}
*/
TimeMap.prototype.get = function (key, timestamp) {
if (!this.map.has(key)) {
return "";
}
if (timestamp < this.map.get(key)[0][0]) {
return "";
}
let left = 0;
let right = this.map.get(key).length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (this.map.get(key)[mid][0] <= timestamp) {
left = mid + 1;
} else {
right = mid;
}
}
if (right > left) {
return "";
}
return this.map.get(key)[right - 1][1];
};
/**
* Your TimeMap object will be instantiated and called as such:
* var obj = new TimeMap()
* obj.set(key,value,timestamp)
* var param_2 = obj.get(key,timestamp)
*/
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated