Time Based Key-Value Store
Design a class TimeMap that stores several values per key, each tagged with a timestamp. set(key, value, timestamp) stores value for key at that timestamp. get(key, timestamp) returns the value stored for key at the latest timestamp that is less than or equal to the given one, or the empty string if no such value exists. Timestamps passed to set strictly increase from call to call.
Examples
TimeMap(); set("lamp", "on", 2); get("lamp", 1); get("lamp", 2); set("lamp", "off", 6); get("lamp", 5); get("lamp", 9) returns "", "on", "on", "off"
Nothing was stored for "lamp" at or before time 1. At time 5 the latest entry is still "on" from time 2, and at time 9 it is "off" from time 6.
TimeMap(); get("door", 4) returns ""
A key that was never set has no value at any time.
TimeMap(); set("a", "x", 1); set("b", "y", 3); get("a", 3); get("b", 2) returns "x", ""
Each key keeps its own history. "b" has no entry at or before time 2.
Constraints
- 1 <= key.length, value.length <= 100
- 1 <= timestamp <= 10^7
- Timestamps across all set calls are strictly increasing.
- At most 2 * 10^5 calls will be made to set and get.
Hints
The timestamps for each key arrive in increasing order. What does that give you for free?
Store each key's history as a sorted list and use binary search to find the latest entry at or before the query time.
Search with lo and hi over the list. When times[mid] <= timestamp, record values[mid] and set lo = mid + 1; otherwise set hi = mid - 1. Return the last recorded value, or the empty string.
Drill This: Your Approach First
Approach
Map each key to a list of (timestamp, value) pairs. Because timestamps only grow, appending in set keeps every list sorted. For get, binary search the key's list for the last pair whose timestamp is at most the query: keep lo and hi, and whenever the middle timestamp qualifies, record its value and search right for a later one. set is O(1), get is O(log m) for a key with m entries, and storage is O(total sets).
Time
O(1) set, O(log m) get
Space
O(total sets)
Pitfall
Solutions
class TimeMap {
private final Map<String, List<Integer>> times = new HashMap<>();
private final Map<String, List<String>> values = new HashMap<>();
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<Integer> ts = times.get(key);
if (ts == null) return "";
List<String> vals = values.get(key);
String answer = "";
int lo = 0, hi = ts.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (ts.get(mid) <= timestamp) {
answer = vals.get(mid);
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return answer;
}
}from collections import defaultdict
class TimeMap:
def __init__(self):
self.store = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.store[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
entries = self.store.get(key, [])
answer = ""
lo, hi = 0, len(entries) - 1
while lo <= hi:
mid = (lo + hi) // 2
if entries[mid][0] <= timestamp:
answer = entries[mid][1]
lo = mid + 1
else:
hi = mid - 1
return answer