Design a time-based key-value store. set(key, val, timestamp) stores with timestamp. get(key, timestamp) returns the value with the largest timestamp <= given timestamp.
set("foo","bar",1), get("foo",1)→"bar", get("foo",3)→"bar", set("foo","bar2",4), get("foo",4)→"bar2", get("foo",5)→"bar2"
HashMap>. Binary search on the list for each get.
- Map> store.
- set: append {timestamp, valIndex} to list.
- get: binary search for largest timestamp <= query.
import java.util.*;
class TimeMap {
Map<String, List<long[]>> store = new HashMap<>();
List<String> vals = new ArrayList<>();
public void set(String key, String value, int timestamp) {
store.computeIfAbsent(key, k->new ArrayList<>()).add(new long[]{timestamp, vals.size()});
vals.add(value);
}
public String get(String key, int timestamp) {
List<long[]> list = store.getOrDefault(key, Collections.emptyList());
int lo=0, hi=list.size()-1, idx=-1;
while (lo<=hi) {
int mid=lo+(hi-lo)/2;
if (list.get(mid)[0]<=timestamp) { idx=(int)list.get(mid)[1]; lo=mid+1; }
else hi=mid-1;
}
return idx==-1 ? "" : vals.get(idx);
}
}
- Time Complexity: set: O(1), get: O(log N)
- Space Complexity: O(N)