Time Based Key Value Store
The drill: A key-value store where writes carry a timestamp and reads ask for whatever value was current at some earlier moment — set stores a stamped write, get answers what was true at or before this time, or the empty string if nothing existed yet.
This drill builds a key-value store where every write is stamped with a timestamp instead of simply overwriting whatever was there before — a key can carry many values across its history, one per moment it was set.
Reading a key doesn't ask for its current value; it asks what the value was at or before some specified timestamp, and the store has to reconstruct that answer from everything it's recorded so far.
If a read's timestamp lands before the key was ever written, the honest answer is an empty string — there's no value yet to report at that point in time.
Writes for any given key always arrive in increasing timestamp order on this course, so each key's history is naturally sorted the moment it's queried.
- set and get calls together can number in the thousands per run
- timestamps for a single key always arrive strictly increasing
- a query timestamp earlier than any write for that key returns empty string
- keys and values are plain strings, values reused across writes freely
HINT 1 THE NUDGE
Every write for a key lands with a timestamp; a read isn't asking for THE value, it's asking which stamped write was the most recent one at or before a given moment. Replaying the full history answers that, but slowly.
HINT 2 THE STRUCTURE
Writes for a key always arrive with strictly increasing timestamps, so each key's history is already sorted by the time it gets queried. Sorted history plus a “closest at or before” question is a binary-search shape.
HINT 3 ONE STEP FROM THE ANSWER
Keep each key's timestamps (and matching values) in a growing sorted list; binary-search for the rightmost timestamp not exceeding the query and read the value beside it, or the empty string if the query lands before the first write.
TimeMap stores stamped writes per key, then binary-searches each key's sorted timestamps for what was true at or before a moment.
class TimeMap:
def __init__(self):
self.times: Dict[str, List[int]] = {}
self.vals: Dict[str, List[str]] = {}
def set(self, key: str, value: str, timestamp: int) -> None:
self.times.setdefault(key, []).append(timestamp)
self.vals.setdefault(key, []).append(value)
def get(self, key: str, timestamp: int) -> str:
stamps = self.times.get(key)
if not stamps:
return ""
i = bisect.bisect_right(stamps, timestamp) - 1
return self.vals[key][i] if i >= 0 else ""class TimeMap:
def __init__(self):
self.store: Dict[str, List[Tuple[int, str]]] = {}
def set(self, key: str, value: str, timestamp: int) -> None:
self.store.setdefault(key, []).append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
best = ""
for ts, val in self.store.get(key, []): # replay every stamped write
if ts <= timestamp:
best = val
return bestclass TimeMap {
private final Map<String, List<Integer>> times = new HashMap<>();
private final Map<String, List<String>> vals = new HashMap<>();
public TimeMap() {
}
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
vals.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<Integer> ts = times.get(key);
if (ts == null || ts.isEmpty()) {
return "";
}
int lo = 0, hi = ts.size() - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ts.get(mid) <= timestamp) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans == -1 ? "" : vals.get(key).get(ans);
}
}class TimeMap {
private final Map<String, List<Integer>> times = new HashMap<>();
private final Map<String, List<String>> vals = new HashMap<>();
public TimeMap() {
}
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
vals.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<Integer> ts = times.get(key);
if (ts == null) {
return "";
}
String best = "";
for (int i = 0; i < ts.size(); i++) { // replay every stamped write
if (ts.get(i) <= timestamp) {
best = vals.get(key).get(i);
}
}
return best;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED