Appearance
4.11.6 — Time Based Key-Value Store
LeetCode 981 · Medium
The problem
Design a store that remembers the history of every key. It has two operations.
set(key, value, timestamp)records thatkeyhadvalueat momenttimestamp.get(key, timestamp)returns the value set at the latest timestamp that is not after the one asked for. If there is none, it returns the empty string"".
set("foo", "bar", 1)
get("foo", 1) → "bar"
get("foo", 3) → "bar" (nothing newer than time 1 yet, so time 1 still applies)
set("foo", "bar2", 4)
get("foo", 4) → "bar2"
get("foo", 5) → "bar2"
get("foo", 0) → "" (nothing was set at or before time 0)There are up to 200,000 calls in total. Timestamps are between 1 and 10,000,000. One promise matters a lot: for any one key, set is always called with increasing timestamps.
What the problem is really asking
Think of a dictionary that never forgets. When a key is updated, the old value is not overwritten. The new value is added with its time stamp. A question like "what was foo at time 3?" means "find the most recent update at or before time 3".
So the real question is: in a key's list of updates, how do you quickly find the last one whose timestamp is at most the asked-for time?
The brute force, and where it wastes work
Store each key's updates in a list. For get, walk the list backwards until you find a timestamp at or before the target.
python
def get(self, key, timestamp):
for t, v in reversed(self.store.get(key, [])):
if t <= timestamp:
return v
return ""set is quick, but get is O(n) for a key with n updates. With 200,000 calls on one busy key, that adds up to billions of steps.
The waste in one sentence: the list is already sorted by time, so binary search could find the answer in about 17 steps instead of walking up to 200,000.
The idea
Use two structures, each doing one job.
- A hash map from each key to that key's list of updates. This finds the right list in O(1).
- A list of
(timestamp, value)pairs per key. Because timestamps arrive in increasing order, simply adding each new pair to the end keeps the list sorted. Nothing ever needs to be sorted or shifted.
Then get is a binary search over that list. But it is not looking for an exact match. It is looking for the largest timestamp that is at most the target. This kind of search is called a floor search, because it finds the "floor" under the target: the highest value that does not go above it.
How the floor search works
A normal binary search gives up with −1 when the exact value is missing. Here, a missing exact match is the usual case. People rarely ask for a time that was set exactly. So the search must keep track of the best answer it has seen so far.
- When the middle timestamp is at or before the target, it is a valid answer. Remember it. But a later valid one might exist, so keep searching to the right.
- When the middle timestamp is after the target, it is too new. Search to the left.
When the range runs out, the remembered answer is the latest valid one.
The solution
python
class TimeMap:
def __init__(self):
self.store = {} # (1)
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = []
self.store[key].append((timestamp, value)) # (2)
def get(self, key: str, timestamp: int) -> str:
entries = self.store.get(key, []) # (3)
answer = "" # (4)
low, high = 0, len(entries) - 1
while low <= high: # (5)
mid = low + (high - low) // 2
if entries[mid][0] <= timestamp: # (6)
answer = entries[mid][1]
low = mid + 1
else: # (7)
high = mid - 1
return answer # (8)ts
class TimeMap {
private store = new Map<string, Array<[number, string]>>(); // (1)
set(key: string, value: string, timestamp: number): void {
if (!this.store.has(key)) this.store.set(key, []);
this.store.get(key)!.push([timestamp, value]); // (2)
}
get(key: string, timestamp: number): string {
const entries = this.store.get(key) ?? []; // (3)
let answer = ""; // (4)
let low = 0, high = entries.length - 1;
while (low <= high) { // (5)
const mid = low + Math.floor((high - low) / 2);
if (entries[mid][0] <= timestamp) { // (6)
answer = entries[mid][1];
low = mid + 1;
} else { // (7)
high = mid - 1;
}
}
return answer; // (8)
}
}Line by line
(1) The map from each key to its list of (timestamp, value) pairs.
(2) Add the new pair to the end. Timestamps for a key always increase, so the end is exactly where it belongs. The list stays sorted for free, and set is O(1).
(3) The key's history. .get(key, []) returns an empty list if the key was never set, so the loop below simply does not run.
(4) Start the answer as "". This is a deliberate choice. It might seem tidy to start with the first entry's value, but that assumes there is always a valid entry. There is not. In the example, get("foo", 0) must return "", because nothing was set at or before time 0. Starting with "" handles that case with no extra code.
(5) Shape A from 4.11.1, with both ends as real positions.
(6) The middle entry is at or before the target. It is a valid answer, so remember its value. Then look for a later valid entry to the right.
(7) The middle entry is after the target. Too new. Look to the left.
(8) The latest valid value, or "" if none was found.
Trace
The history for "foo" is [(1, "bar"), (4, "bar2")].
get("foo", 3):
| Step | low | high | mid | Timestamp at mid | At or before 3? | Action | answer |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | yes | remember "bar", low = 1 | "bar" |
| 2 | 1 | 1 | 1 | 4 | no | high = 0 | "bar" |
| end | 1 | 0 | return | "bar" |
get("foo", 0):
| Step | low | high | mid | Timestamp at mid | At or before 0? | Action | answer |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | no | high = −1 | "" |
| end | 0 | −1 | return | "" |
Complexity, derived
Time. set does one map lookup and one add-to-end, both constant on average, so O(1). get does one map lookup and a binary search over that key's n entries, about \log_2 n steps, so O(\log n).
Space. Every set stores one pair, and nothing is ever deleted. So the memory is O(N) for N calls to set.
Edge cases
- A key that was never set. An empty list, and the answer is
"". - A time before the first update. No entry qualifies, and the answer is
"". - A time after the last update. The last entry is the answer.
- An exact match. It qualifies in line (6), so it is remembered. Then the search moves right, finds nothing later that qualifies, and keeps it.
The library version
Python's bisect module already does the boundary part.
python
import bisect
def get(self, key, timestamp):
entries = self.store.get(key, [])
i = bisect.bisect_right(entries, (timestamp, chr(127)))
return entries[i - 1][1] if i else ""bisect_right returns the position just after every entry that sorts at or below (timestamp, chr(127)). So i - 1 is the last entry at or before the target. chr(127) is a character that sorts after every normal letter. Pairing it with the timestamp makes sure an entry with exactly that timestamp is counted as "at or below".
Write the manual loop in an interview. The point of the question is the floor search, and bisect skips it. Mention the library version afterwards.
What if the timestamps were not in order?
The promise of increasing timestamps does real work. Without it, set would have to insert each pair in its correct place. In a plain list that costs O(n), because everything after the insert point shifts along. A balanced search tree would make it O(\log n). See 4.13.2.
Noticing which promise makes the easy solution possible is a good habit. It is the same reasoning as spotting "the list is sorted" in 4.5.2.
Variations you will meet
- Snapshot Array. Take a "snapshot" of an array, then ask what a position held at snapshot
s. Each position keeps its own list of(snapshot, value)pairs, and a lookup is this floor search. - Databases that keep old versions. Many databases keep several versions of a row, each stamped with the moment it was written. A reader finds the latest version written before the reader began. That lookup is this floor search.
- Stock price history. "What was the price at 10:15?" means "the last trade at or before 10:15".
The general lesson: when you need "the latest entry not after X" in a sorted list, binary search and remember the best valid candidate as you go.
What the interviewer will push on
"Why is set O(1)?" Timestamps arrive in increasing order, so adding to the end keeps the list sorted.
"How does your search handle a time that was never set exactly?" It closes in on the latest timestamp at or before the target, remembering the best valid answer as it goes.
"What do you start the answer as?" "", a value that cannot be confused with real data. Not the first entry.
"What if timestamps arrived out of order?" Inserting becomes O(n) in a list, or O(\log n) in a balanced tree.
"How does memory grow?" Forever, since nothing is deleted. A real system would throw away versions that no reader can still ask for.
One thing to volunteer: name the search. "This is a floor search, the largest timestamp not after the target, not an exact-match search." That is the piece that carries over to other problems.
Next: 4.11.7 Median of Two Sorted Arrays. The hardest binary search in the set, where you search for a cut rather than a value.