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.
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public
class TimeKeyStore {
private Map<String, TreeMap<Integer, String>> map;
public TimeKeyStore() {
map = new HashMap<>();
}
public void put(String key, String value, int timestamp) {
map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
}
public String get(String key, int timestamp) {
if (!map.containsKey(key)) {
return "-1";
}
TreeMap<Integer, String> values = map.get(key);
Map.Entry<Integer, String> entry = values.floorEntry(timestamp);
return entry == null ? "-1" : entry.getValue();
}
}Follow-up:
How would you optimize the solution if the number of keys is very large?
