Time-based key-value store

Expected question

"Implement set(key, value, timestamp) and get(key, timestamp) — return the largest value with time ≤ timestamp."

Variant forms

• "Design a time-travel key-value store with strictly increasing timestamps per key."
• "Add get_latest(key) and get_range(key, t1, t2)."
• "How do you store history efficiently if most keys have few versions?"
• "Make set/get thread-safe when different keys are updated concurrently."
• "What if timestamps can arrive out of order?"
• "Support delete(key, timestamp) tombstones."
• "Binary search vs tree map per key — trade-offs?"
• "How would you persist this structure for crash recovery? (Staff extension)"

The question, as it might actually be asked

Implement: - set(key, value, timestamp) — timestamps for a key are strictly increasing - get(key, timestamp) — largest value with time ≤ timestamp, or null

How you'd talk while coding

I'd confirm timestamps are non-decreasing per key — that's the assumption that makes append + binary search work. Brute is linear scan of (ts, val) pairs. Correct is a list per key and bisect_right for upper bound. I'd say "set is append; get is log n on that key's history" before coding. Tests: set a@1, b@2; get@1→a, get@3→b, get@0→None. Staff+ stop line: "I'll put a lock around the map for concurrent callers. Out-of-order timestamps need an explicit reject-or-reorder policy — I won't invent Cassandra here."

Where this actually gets asked

Common Meta/FAANG-style medium. Staff signal is API clarity, binary-search correctness, and a memory/GC note — not jumping to a distributed versioned store.

Problem

Implement:

• set(key, value, timestamp) — timestamps for a key are strictly increasing
• get(key, timestamp) — largest value with time ≤ timestamp, or null

Clarifying questions you should ask first

1. Are timestamps strictly increasing per key? (usually yes — confirm)
2. Integer timestamps?
3. Concurrent sets on same key?
4. Need delete / range scan?

Approach ladder

Reference solution (Python)

from __future__ import annotations
import bisect
from threading import RLock

class TimeMap:
    def __init__(self) -> None:
        self._data: dict[str, list[tuple[int, str]]] = {}
        self._lock = RLock()

    def set(self, key: str, value: str, timestamp: int) -> None:
        with self._lock:
            arr = self._data.setdefault(key, [])
            if arr and timestamp < arr[-1][0]:
                raise ValueError("timestamps must be non-decreasing per key")
            arr.append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str | None:
        with self._lock:
            arr = self._data.get(key)
            if not arr:
                return None
            i = bisect.bisect_right(arr, (timestamp, chr(0x10FFFF))) - 1
            if i < 0:
                return None
            return arr[i][1]

Complexity: set O(1) amortized append; get O(log n) per key history.

Verbal tests to narrate

1. set a@1, b@2; get@1→a; get@3→b; get@0→None
2. Multiple keys independent
3. Duplicate timestamp policy — confirm with interviewer (overwrite vs reject)

Staff+ deep dive

What not to discuss

• Building Cassandra in 40 minutes
• Ignoring the non-decreasing timestamp assumption without asking

What's expected at each level

• Mid-level: Linear scan works.
• Senior: Binary search + clean API.
• Staff+: Concurrency + memory bounds + bisect edge cases.
• Principal: Relates to real config/feature-flag versioning systems.

Follow-up questions to expect

• "Timestamps arrive out of order?" — I'd define reject vs insert-and-sort before coding. The reference assumes non-decreasing.
• "How is get O(log n)?" — Per-key ordered history, upper-bound binary search.
• "Readers during append?" — Lock the history, or publish an immutable snapshot for readers.
• "When do you stop?" — Correct versioned get/set, tests, one retention note. Not a database design.

Related

• 00-staff-plus-coding-bar.md