Design a time-based key-value store that stores multiple values for the same key at different timestamps and retrieves the value for a key at a given timestamp (or the latest before it).
set("foo","bar",1), set("foo","bar2",4), get("foo",1)→"bar", get("foo",3)→"bar", get("foo",4)→"bar2"
Store values in a list of (timestamp, value) pairs per key. Use binary search to find the latest timestamp <= given timestamp.
- Store Map>.
- On set: append (timestamp, value) to the list for key.
- On get: binary search in the list for the largest timestamp <= query timestamp.
- Return empty string if no valid timestamp found.
import java.util.*;
class TimeMap {
Map<String, List<int[]>> map = new HashMap<>();
List<String> vals = new ArrayList<>();
public void set(String key, String value, int timestamp) {
map.computeIfAbsent(key, k -> new ArrayList<>())
.add(new int[]{timestamp, vals.size()});
vals.add(value);
}
public String get(String key, int timestamp) {
List<int[]> list = map.getOrDefault(key, Collections.emptyList());
int lo = 0, hi = list.size() - 1, res = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (list.get(mid)[0] <= timestamp) { res = list.get(mid)[1]; lo = mid + 1; }
else hi = mid - 1;
}
return res == -1 ? "" : vals.get(res);
}
}
- Time Complexity: set: O(1), get: O(log N)
- Space Complexity: O(N) total