Time Based Key-Value Store

Problem

Design a key-value store where every write is stamped with a time, and reads ask for the value “as of” a given time. Implement a class TimeMap with:

• set(key, value, timestamp) — store value under key at time timestamp.
• get(key, timestamp) — return the value written to key with the largest timestamp_prev <= timestamp. If no write to key happened at or before that time, return "".

For each key, all set calls arrive with strictly increasing timestamps.

Examples

• set("foo","bar",1); get("foo",1) → "bar"; get("foo",3) → "bar" At time 3 the latest write at-or-before is still the one from time 1.
• Continuing: set("foo","bar2",4); get("foo",4) → "bar2"; get("foo",5) → "bar2" The write at time 4 supersedes the earlier one for queries at time ≥ 4.
• get("missing", 10) → ""; and after only set("a","x",5), get("a", 4) → "" Unknown key, or a query time earlier than the first write, both return the empty string.

Constraints

• 1 <= len(key), len(value) <= 100, lowercase letters and digits.
• 1 <= timestamp <= 10^7; timestamps for set are strictly increasing per key.
• Up to 2 * 10^5 total calls to set and get — each get must beat a linear scan over that key’s history.

Think about it first

TL;DR

Per-key sorted history + binary search (bisect_right) on timestamps — O(1) amortized set, O(log n) get, O(N) space for N writes.

Approach 1 — Brute force

This is a design problem, so the brute force is the naive design: append every write to the key’s history, and answer get by scanning that history for the largest timestamp at or before the query.

from collections import defaultdict
from typing import Dict, List, Tuple


class TimeMap:
    def __init__(self) -> None:
        self.store: Dict[str, List[Tuple[int, str]]] = 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:
        best_time, best_value = -1, ""
        for t, v in self.store.get(key, []):
            if best_time < t <= timestamp:
                best_time, best_value = t, v
        return best_value

• Time: set O(1); get O(k) where k = writes to that key. Space: O(N).

With up to 2·10^5 calls concentrated on one key, the gets alone are O(N²) ≈ 4·10^10 comparisons in the worst case — far too slow.

Approach 2 — Sorted history + hand-rolled binary search

The problem guarantees strictly increasing timestamps per key, so each key’s history is already sorted; appends keep it sorted with no extra work. “Largest timestamp ≤ query” is a predecessor query, which binary search answers in O(log n): find the last index whose timestamp is <= timestamp.

Store timestamps and values in two parallel lists per key so the search compares plain integers.

from collections import defaultdict
from typing import Dict, List


class TimeMap:
    def __init__(self) -> None:
        self.times: Dict[str, List[int]] = defaultdict(list)
        self.values: Dict[str, List[str]] = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        times = self.times.get(key)
        if not times:
            return ""
        lo, hi = 0, len(times) - 1
        answer = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if times[mid] <= timestamp:
                answer = mid          # candidate; try to find a later one
                lo = mid + 1
            else:
                hi = mid - 1
        if answer == -1:
            return ""
        vals = self.values[key]
        return vals[answer]

Walkthrough of the question’s sequence: after set("foo","bar",1) and set("foo","bar2",4), times["foo"] = [1, 4].

And get("missing", 10) returns "" at the empty-history check.

• Time: set O(1) amortized; get O(log k). Space: O(N).

Approach 3 — The same design via bisect_right

Python’s bisect module already implements the predecessor search: bisect_right(times, t) returns the insertion point after any entry equal to t, so the predecessor is at index bisect_right(...) - 1, and an insertion point of 0 means no write exists at or before t.

import bisect
from collections import defaultdict
from typing import Dict, List, Tuple


class TimeMap:
    def __init__(self) -> None:
        self.store: Dict[str, List[Tuple[int, str]]] = 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:
        history = self.store.get(key)
        if not history:
            return ""
        i = bisect.bisect_right(history, timestamp, key=lambda pair: pair[0])
        if i == 0:
            return ""
        entry = history[i - 1]
        return entry[1]

Tracing get("foo", 3) with history = [(1, "bar"), (4, "bar2")]: bisect_right on the timestamps [1, 4] with 3 returns 1; history[0] is (1, "bar") → "bar". For get("foo", 4) it returns 2 → (4, "bar2") → "bar2". Same complexities as Approach 2; this is the version to write in an interview once you can articulate what bisect_right returns. (The key= parameter needs Python ≥ 3.10; on older versions keep a separate timestamp list as in Approach 2.)

Common pitfalls

• Using bisect_left instead of bisect_right: a write at exactly the query timestamp must be returned, and bisect_left would place the insertion point before it, skipping it.
• Forgetting the two “no answer” cases — unknown key, and query time earlier than the key’s first write (insertion point 0). Both must return "", not raise.
• Re-sorting or inserting in sorted order on every set: the strictly-increasing guarantee makes plain append correct and O(1); sorted-insert turns set into O(k).
• Binary searching a list of (timestamp, value) tuples with a bare integer and no key= — the tuple-vs-int comparison raises TypeError in Python 3.

Pattern takeaway

“Latest state at or before time t” is a predecessor query, and predecessor queries on sorted data are answered with binary search. When a design problem hands you data that arrives already ordered (timestamps, versions, log offsets), append to a list and bisect at read time: you get O(log n) queries without paying to keep the structure sorted.