Keyed Stores

What is this?

A library keeps every edition of every book it has ever held. Asked for "the edition that was current in March 2019", the librarian does not read the whole shelf — the editions sit in date order, so she jumps to roughly the right place and steps back one. That works because the writes arrive in order, which is what makes the reads cheap.

Every problem here is a version of that bargain. You get to choose which operation does the work, and the choice is the answer.

flowchart TD A["a keyed store with two operations"] --> B{"which is called more?"} B -->|"writes"| C["cheap insert, scan on read"] B -->|"reads"| D["maintain an index, pay on write"] C --> E["Two Sum III: count map + scan find"] D --> F["Two Sum III: precomputed sums"] A --> G["append-only timestamps
→ binary search the history"] A --> H["stale entries at the front
→ discard lazily on read"]

💡 Fun fact: Time Based Key-Value Store is only easy because of a single line in the problem statement: timestamps arrive strictly increasing. That guarantee means each key's history is already sorted, so set is an O(1) append and get is an O(log n) binary search for the largest timestamp not exceeding the query. Remove that guarantee and set needs an insertion into a sorted structure. Noticing which stated constraint is doing the work is most of what these questions test.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: decide which operation pays the cost, then pick the index that makes the other cheap — a sorted history for versioned reads, a count map for membership, or a queue with lazy eviction when staleness only matters at the front.

1. Versioned reads by binary search

store = defaultdict(list)                 # key -> [(timestamp, value), ...] ascending

def set(key, value, timestamp):
    store[key].append((timestamp, value))          # O(1) — timestamps increase

def get(key, timestamp):
    history = store[key]
    lo, hi = 0, len(history)
    while lo < hi:                                  # find the FIRST entry newer than t
        mid = (lo + hi) // 2
        if history[mid][0] <= timestamp:
            lo = mid + 1
        else:
            hi = mid
    return history[lo - 1][1] if lo else ""         # step back one; nothing before → ""

The search finds the first entry after the requested time and steps back one — the standard way to express "the largest value not exceeding the query" without a separate equality case. The if lo else "" handles a query older than every write.

2. Choosing where the cost lands

Two Sum III cannot make both add and find constant time, and the interview is about saying so:

Design	`add`	`find`	Choose when
count map, scan keys on find	`O(1)`	`O(n)`	writes dominate
precompute all pairwise sums	`O(n)`	`O(1)`	reads dominate

The count map version needs one subtlety: when the complement equals the value itself, that value must appear at least twice. Missing that reports find(4) as true for a store containing a single 2.

3. Lazy eviction

First Unique Number keeps a queue of candidates and a count map. Numbers whose count has risen above one are not removed when they stop being unique — they are simply skipped when they reach the front:

def show_first_unique():
    while queue and counts[queue[0]] > 1:
        queue.popleft()                    # discard stale entries, permanently
    return queue[0] if queue else -1

Each number is discarded at most once across the whole lifetime, so the amortised cost is O(1) even though a single call may pop several. Eager removal would require finding an arbitrary element in a queue, which is exactly what a queue cannot do.

4. A 30-second worked example (versioned get)

set("foo", "bar", 1)
set("foo", "baz", 4)
history["foo"] = [(1, "bar"), (4, "baz")]

get("foo", 3):  first entry with timestamp > 3 is index 1  → step back → "bar" ✓
get("foo", 4):  first entry with timestamp > 4 is index 2  → step back → "baz" ✓
get("foo", 0):  first entry with timestamp > 0 is index 0  → lo == 0   → ""    ✓

All three cases — between writes, exactly on a write, and before any write — fall out of the same search with no special handling.

5. Where you'll actually meet this

Versioned storage. Point-in-time reads in databases, feature-flag history and configuration snapshots.
Time-travel debugging. "What was this value at this moment?" over an append-only event log.
Caching layers. Membership and frequency tracking where writes vastly outnumber reads, or the reverse.
Stream deduplication. Tracking the first item still satisfying a property, with stale entries retired lazily.
Audit trails. Append-only histories queried by timestamp.

6. Problems in this chapter

▶ Time Based Key-Value Store

set(key, value, timestamp) and get(key, timestamp) returning the newest value at or before that time. Append on write, binary search on read.
Pattern: per-key sorted history. Target: O(1) set, O(log n) get.

▶ Two Sum III - Data Structure Design

add(number) and find(target). Choose the count-map design or the precomputed-sums design, and justify it by the access pattern.
Pattern: deliberate cost placement. Target: O(1)/O(n) or O(n)/O(1).

▶ First Unique Number

Report the first still-unique number in a stream. A queue of candidates plus a count map, discarding stale front entries on read.
Pattern: lazy eviction. Target: O(1) amortised per operation.

7. Common pitfalls 🚫

Sorting the history on every set. The increasing-timestamp guarantee makes it unnecessary — but check that the problem actually gives it.
Returning the wrong side of the binary search. You want the last entry <= t, which is "first entry > t, minus one".
Missing the empty result. A query before any write must return "", not crash.
Forgetting the self-pair case in Two Sum III: x + x requires two copies of x.
Claiming both operations are O(1). They cannot both be; the interviewer is waiting for you to notice.
Eagerly removing from the queue. Queues have no cheap arbitrary removal — skip stale entries at the front instead.
Re-counting on every read. Maintain the counts as numbers arrive.

8. Key takeaways

Decide which operation pays, say so, and design around it.
A guarantee in the statement is usually load-bearing — increasing timestamps are what make appends valid.
"Last entry ≤ t" is "first entry > t, minus one". Learn one form of the search.
Lazy eviction converts an impossible removal into an amortised skip.
Keep a parallel index — the count map beside the queue is what makes staleness detectable.
Handle the self-pair and the empty cases explicitly; both are routinely missed.
Why interviewers like it: there is no single correct design, so the answer is your reasoning about the access pattern rather than the code.

Order: Time Based Key-Value Store → Two Sum III - Data Structure Design → First Unique Number.

Intermediate