4.11.6 — Time Based Key-Value Store

LeetCode 981 · Medium

The problem

Design a store with two operations:

• set(key, value, timestamp) — record a value for a key at a moment in time.
• get(key, timestamp) — return the value that was set at the largest timestamp less than or equal to the one asked for. Return "" if there is none.

set("foo", "bar", 1)
get("foo", 1)    →  "bar"
get("foo", 3)    →  "bar"      (nothing newer than 1, so 1 still applies)
set("foo", "bar2", 4)
get("foo", 4)    →  "bar2"
get("foo", 5)    →  "bar2"
get("foo", 0)    →  ""         (nothing at or before 0)

All calls to set for a given key arrive with strictly increasing timestamps. That promise is what makes the solution simple.

The pattern

Two structures, each doing one job:

• A hash map from key to a list, giving O(1) access to that key's history.
• A list of (timestamp, value) pairs per key, which is already sorted because set is promised to arrive in increasing time order.

Then get is a binary search over that list, looking not for an exact match but for the largest timestamp not exceeding the target. That variant has a name — a floor search, or bisect_right minus one — and it is the reusable idea on this page.

Because the list arrives sorted for free, set is O(1): just append. Nothing needs to be sorted or shifted.

The floor search

Ordinary binary search returns −1 when the value is absent. Here absence is normal — you almost never ask for a timestamp that exists exactly — so the search must converge on a position instead.

Use the boundary shape and carry the best candidate found so far:

low, high = 0, len(entries) - 1
answer = ""
while low <= high:
    mid = (low + high) // 2
    if entries[mid][0] <= timestamp:
        answer = entries[mid][1]     # valid candidate — remember it
        low = mid + 1                # but try for a later one
    else:
        high = mid - 1               # too new — look earlier
return answer

Every time you find a timestamp at or below the target, it is a legal answer, so record it. Then keep pushing right to see whether a later legal one exists. When the loop ends, answer holds the latest valid value.

Initialise answer to "", not to the first entry. Report 4 recorded this exact trap: seeding the tracker with index 0 assumes there is always a valid historical entry, and there is not — get("foo", 0) in the example above must return "". Use a value that cannot be confused with real data.

The solution

Python

class TimeMap:
    def __init__(self):
        self.store = {}                       # key → list of (timestamp, value)

    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))     # already in order

    def get(self, key: str, timestamp: int) -> str:
        entries = self.store.get(key, [])
        answer = ""
        low, high = 0, len(entries) - 1

        while low <= high:
            mid = low + (high - low) // 2
            if entries[mid][0] <= timestamp:
                answer = entries[mid][1]
                low = mid + 1
            else:
                high = mid - 1

        return answer

TypeScript

class TimeMap {
  private store = new Map<string, Array<[number, string]>>();

  set(key: string, value: string, timestamp: number): void {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key)!.push([timestamp, value]);
  }

  get(key: string, timestamp: number): string {
    const entries = this.store.get(key) ?? [];
    let answer = "";
    let low = 0, high = entries.length - 1;

    while (low <= high) {
      const mid = low + Math.floor((high - low) / 2);
      if (entries[mid][0] <= timestamp) {
        answer = entries[mid][1];
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }

    return answer;
  }
}

self.store.get(key, []) handles a key that was never set, returning an empty list so the loop simply does not run.

The library version

Python has this search built in:

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 insertion point after any equal entries, so i - 1 is the last entry at or below the target. The chr(127) is a sentinel that sorts after any ordinary string, making sure an exact timestamp match is included.

Write the manual loop in an interview. The point of the question is the floor search, and reaching for bisect skips it. Mention it afterwards.

Complexity

set is O(1). get is O(\log n) for n entries under that key. Space is O(\text{total entries}).

What if the timestamps were not sorted?

The promise of increasing timestamps is doing real work. Without it, set would have to insert into the right position, which is O(n) in an array because of the shifting, or O(\log n) with a balanced tree or a skip list (4.13.2).

Noticing which constraint makes the easy solution legal is a good habit. It is the same reasoning as spotting "the array is sorted" in 4.5.2.

Where this goes next

This is a small version of a real thing:

• Multi-version concurrency control — a database keeps several versions of a row, each stamped with the transaction that wrote it, and a reader finds the latest version visible to it. That lookup is this floor search. Chapter 7.4.
• Time-series databases — a query for "the value at time T" is exactly this.
• Snapshot reads and event sourcing — find the last snapshot at or before a point, then replay forward.

The honest limitation: memory grows forever, because nothing is ever deleted. A real system runs a compaction job that discards versions no reader can still see.

What the interviewer will push on

"Why is set O(1)?" Timestamps arrive in increasing order, so appending keeps the list sorted.

"How does your binary search handle a missing exact match?" It converges on the largest timestamp at or below the target, remembering the best candidate as it goes.

"What do you initialise the answer to?" A sentinel that cannot be a real value, not index 0.

"What if timestamps arrived out of order?" Insertion becomes O(n) in an array, or you switch to a balanced tree.

"How would this scale?" Memory is unbounded without compaction; naming that is the systems answer.

One thing to volunteer: name the search variant. "This is a floor search — the largest key not exceeding the target — rather than an exact-match search." That is the transferable piece.

Next: 4.11.7 Median of Two Sorted Arrays — the hardest binary search in the set, and the one where you search for a cut rather than a value.