Time Based Key-Value Store
Create a time-based key-value store class that supports two operations: put and get. The put operation takes three parameters: key, value, and timestamp. The get operation takes two parameters: key and timestamp. The get operation should return the value of the key at the given timestamp if it exists, otherwise it should return -1.
Constraints:
- 1 <= key <= 10^5
- 1 <= value <= 10^5
- 1 <= timestamp <= 10^7
- At most 10^5 calls to put and get
Examples:
Input: ["TimeKeyStore","put","get","get","put","get"] [["foo","bar",1],["foo",1],["foo",3],["foo",2],["foo","bar",4],["foo",4]]
Output: [null,null,"bar","bar",null,"bar"]
Explanation: TimeKeyStore timeKeyStore = new TimeKeyStore(); timeKeyStore.put("foo","bar",1); timeKeyStore.get("foo",1); timeKeyStore.get("foo",3); timeKeyStore.put("foo","bar",4); timeKeyStore.get("foo",4);
Solutions
Hash Table
We use a hash table to store the key-value pairs. For each key, we store a list of values and timestamps. When we put a new value, we append it to the list. When we get a value, we use binary search to find the latest value that is less than or equal to the given timestamp.
class TimeKeyStore {
constructor() {
this.map = new Map();
}
put(key, value, timestamp) {
if (!this.map.has(key)) {
this.map.set(key, []);
}
this.map.get(key).push([value, timestamp]);
}
get(key, timestamp) {
if (!this.map.has(key)) {
return -1;
}
const values = this.map.get(key);
let left = 0;
let right = values.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (values[mid][1] <= timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (right === -1) {
return -1;
}
return values[right][0];
}
}
Follow-up:
How would you optimize the solution if the number of keys is very large?
