Problem 20 · Binary Search

Time Based Key-Value Store

MediumClassic DSA & systems

01Problem

Design a store with set(key, value, timestamp) and get(key, timestamp) that returns the value with the largest timestamp <= the given one, or an empty string.

02Key insight

Per key, keep (timestamp, value) versions in sorted order (timestamps arrive increasing) and use bisect_right for floor lookups; this is MVCC snapshot reads in miniature.

03Solution

solution.pypython24 lines

import bisect
from collections import defaultdict

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:
        times = self._times[key]
        if times and timestamp < times[-1]:  # tolerate out-of-order writes
            i = bisect.bisect_right(times, timestamp)
            times.insert(i, timestamp)
            self._values[key].insert(i, value)
        else:
            times.append(timestamp)
            self._values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        times = self._times.get(key)
        if not times:
            return ""
        i = bisect.bisect_right(times, timestamp)
        return self._values[key][i - 1] if i else ""

Try it first.

Timeset O(1) amortised (O(n) if out of order), get O(log n)

SpaceO(total versions)

tests.py · 3 passing

tests.pypython6 lines

tm = TimeMap()
tm.set("foo", "bar", 1)
assert tm.get("foo", 1) == "bar" and tm.get("foo", 3) == "bar"
tm.set("foo", "bar2", 4)
assert tm.get("foo", 4) == "bar2" and tm.get("foo", 5) == "bar2"
assert tm.get("foo", 0) == "" and tm.get("missing", 10) == ""

04Staff-level follow-up

How does this scale to a production versioned store? Persist as an LSM keyed by (key, inverted timestamp) so a floor read is one seek; add TTL/compaction of old versions and a garbage-collection watermark like Snowflake/Delta time travel.