Time Based Key-Value Store
Design a store that remembers every value a key has ever had, together with the time it was written, and can answer "what did this key hold at time t?".
Implement the class TimeMap:
new TimeMap()creates an empty store.set(key, value, timestamp)records thatkeywas set tovalueattimestamp.get(key, timestamp)returns the value thatkeyhad attimestamp: the one written with the largest timestamp that is at most the one asked for. If the key was never written at or before that time, return an empty string"".
For any one key, the calls to set always use strictly increasing timestamps. Different keys are independent.
Each test is a sequence of calls. The first call creates the object. Calls that return nothing are shown as null in the expected output, and their return value isn't checked.
Constraints
- Keys and values are non-empty lowercase strings or short words, at most 100 characters.
1 <= timestamp <= 10^7- At most
2 * 10^5calls in total.
Examples
Example 1
Input: ["TimeMap","set","set","get","get","get","get","get"]
[[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]Nothing existed at time 5. At 10 and 15 the answer is high; from 20 on it is low.
Example 2
Input: ["TimeMap","get","set","get","get","get"]
[[],["x",1],["x","a",1],["x",0],["x",1],["y",1]]
Output: [null,"",null,"","a",""]An unknown key, or a time before the first write, answers with an empty string.
Example 3
Input: ["TimeMap","set","set","set","get","get","get","get"]
[[],["a","p",1],["b","q",2],["a","r",3],["a",2],["b",2],["a",3],["b",9]]
Output: [null,null,null,null,"p","q","r","q"]Each key has its own history: a at time 2 is p, while b at time 2 is q.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Map and Set Arrays: create, read, update
class TimeMap {
constructor() {
}
/**
* Stores the value for the key at the given time. Timestamps for one key are strictly increasing.
* @param {string} key
* @param {string} value
* @param {number} timestamp
* @return {void}
*/
set(key, value, timestamp) {
}
/**
* @param {string} key
* @param {number} timestamp
* @return {string} the value stored with the largest timestamp that is at most the one given, or ""
*/
get(key, timestamp) {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.