Time Based Key-Value Store

Solving tips

Exploit the strictly-increasing-timestamp guarantee: each key's history is already sorted, so set is a plain O(1) append with no sorting or sorted-insert needed.
get is a predecessor query (largest timestamp <= query): use bisect_right on the timestamps, then the candidate is index bisect_right - 1; index 0 means no valid write, return "".
Use bisect_right, not bisect_left, so a write at exactly the query timestamp is returned rather than skipped.
Store parallel times/values lists per key (or use bisect key= on Python 3.10+) so you compare plain ints; get is O(log n), space O(N).

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 "".

A crucial guarantee: 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

Hint 1

Per key you need the full history of writes, not just the latest value. What does the strictly-increasing-timestamp guarantee give you for free about that history?

Hint 2

Each key's history is a list already sorted by timestamp. "Largest timestamp ≤ query" is a predecessor query on a sorted list — which algorithm answers that in O(log n)?

Hint 3

Keep `dict: key -> list of (timestamp, value)` and answer `get` with `bisect_right` on the timestamps: the candidate is the entry just before the insertion point; if the insertion point is 0, no write qualifies and you return `""`.

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 best 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 insight: the problem guarantees strictly increasing timestamps per key, so each key’s history is already sorted — no sorting step needed, appends keep it sorted for free. “Largest timestamp ≤ query” is then a predecessor query, the textbook use of binary search (the classical O(log n) halving of a sorted interval): 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].

call	hi	mid	times[mid] ≤ t?	result
`get("foo", 3)`	1	0	1 ≤ 3 yes → answer 0, lo 1	then mid 1: 4 ≤ 3 no → hi 0; loop ends → `"bar"`
`get("foo", 4)`	1	0	1 ≤ 4 yes → answer 0, lo 1	then mid 1: 4 ≤ 4 yes → answer 1 → `"bar2"`
`get("foo", 5)`	1	same as t=4		`"bar2"`

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`

The insight: 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 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 binary search’s home turf. 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 sorted-structure query power with none of the maintenance cost.