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 {
public:
void put(string key, string value, int timestamp) {
if (map.find(key) == map.end()) {
map[key] = {
}
;
}
map[key][timestamp] = value;
}
string get(string key, int timestamp) {
if (map.find(key) == map.end()) {
return "-1";
}
auto values = map[key];
auto it = values.upper_bound(timestamp);
if (it == values.begin()) {
return "-1";
}
--it;
return it->second;
}
private:
map<string, map<int, string>> map;
}
;Follow-up:
How would you optimize the solution if the number of keys is very large?
