981. Time Based Key-Value Store
HashTable + TreeMap. In Java, we can use TreeMap.floorKey(timestamp) to find the largest timestamp smaller than the given timestamp.
Referred to this solution.
Time: O(1) for set, O(logn) for get. Space = O(n)
class TimeMap {
private Map<String, TreeMap<Integer, String>> map;
/** Initialize your data structure here. */
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
if (!map.containsKey(key)) {
map.put(key, new TreeMap<>());
}
map.get(key).put(timestamp, value); // we can "put" directly
}
public String get(String key, int timestamp) {
TreeMap<Integer, String> treeMap = map.get(key);
if (treeMap == null) {
return "";
}
Integer floor = treeMap.floorKey(timestamp);
if (floor == null) {
return "";
}
return treeMap.get(floor);
}
}
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap obj = new TimeMap();
* obj.set(key,value,timestamp);
* String param_2 = obj.get(key,timestamp);
*/