Why this matters: this problem's design act opens with a decision most machine-coding problems don't have — a genuine algorithm choice, where every option is used in production somewhere and each has a different answer to the same question: what happens when traffic bursts? Choosing without comparing is the requirements failure interviewers watch for. So the design starts with the enumeration.

The enumeration: four algorithms, one honest table

The limit is "100 per minute." Four standard ways to enforce it:

fixed window       count per clock-aligned minute; reset at :00
                   burst truth: 100 at 11:59:59 + 100 at 12:00:01
                   = 200 in two seconds across the boundary
sliding log        store every request timestamp; count the last 60s
                   burst truth: exact — but O(events) memory per key
sliding window     current + weighted previous window count
  counter          burst truth: close to exact; approximation at edges
token bucket       capacity C, refill r/sec; request costs a token
                   burst truth: up to C at once, then refill-rate trickle

Each line's second half is the part that earns points. Fixed window is the cheapest and its boundary burst — double the limit across a window edge — must be stated by whoever proposes it, not discovered by the interviewer. Sliding log is exact and confesses to per-key memory proportional to traffic. Token bucket makes burst an explicit, tunable property: the capacity is the burst allowance.

The choice here: token bucket. Defended in one breath: O(1) time and O(1) state per key, burst behavior that's a dial rather than a defect, and a natural fit for the retry-hint requirement (the state tells you when the next token arrives). The others aren't wrong — they're different points in the trade space, and having placed them there is what makes the choice yours.

Time is a parameter, not an ambient fact

The first structural decision, and the one that quietly determines whether this library is testable:

tryAcquire(nowNanos) -> Decision

The algorithm never reads a clock; the current time arrives as an argument. Two payoffs. Every behavior claim becomes a unit test — "89 tokens after 5.3 seconds" is assertable by passing timestamps, no sleeping, no flaky clock coupling. And clock policy (the monotonic source from our requirements) lives at the library boundary in one place, instead of scattered now() calls deep in arithmetic. This is dependency inversion at its most practical: the algorithm depends on an abstract "current time," and the boundary decides what that means.

Lazy refill: the design carrying the whole memory story

A naive token bucket refills on a schedule — some timer adds tokens to every bucket every interval. Multiply by the requirement: millions of keys. A million timers, or one timer walking a million buckets, most of them for keys that haven't been seen in hours — the design collapses under its own bookkeeping.

The correct shape refills lazily, at read time:

on tryAcquire(now):
    elapsed = now - lastRefillTime
    tokens  = min(capacity, tokens + elapsed * refillRate)
    lastRefillTime = now
    then: tokens >= 1 ? consume, allow : deny

No timers, no background threads, no work for idle keys — a bucket that hasn't been touched in an hour catches up in one multiplication when it's next seen. Idle keys cost nothing but their memory, which the store section below bounds too. This is the single highest-value idea in the problem: say it early and plainly.

Config resolution: a chain, resolved once

Requirements gave a default limit plus per-key-pattern overrides. The resolution order must be explicit — most specific wins:

exact-key override  >  pattern/tier override  >  library default

The performance decision rides on when resolution happens. Walking a chain of maps on every allow() puts config lookup on the hot path; resolving once, when a key's state is first created, and caching the resolved limit on that state, makes the hot path config-free. The trade to state honestly: config changes then apply to new key states, not live ones — acceptable under our startup-configured requirements, and worth saying aloud rather than leaving implicit.

The keyed store: bounded, because eviction is lossless

Millions of keys, each with a small state — the remaining question is lifecycle. Created on first sight, obviously. But never destroyed means the library leaks by design: keys are open-ended (tokens, IPs), and yesterday's traffic shouldn't own today's memory.

The design insight that makes eviction safe: an idle bucket is reconstructible. A bucket untouched for longer than capacity / refillRate is full — indistinguishable from a brand-new one. Evicting it loses nothing; if the key returns, first-sight creation rebuilds exactly the state eviction destroyed. So the store can bound itself aggressively — an idle-time sweep or an LRU-style bound — with zero correctness cost. (The same lockstep discipline as the cache chapter's store, for the same reason: a map nobody prunes is a slow leak wearing a data structure's clothes.)

The retry hint, derived not guessed

Requirements marked "retry in how long?" as nice-to-have — with the token bucket it's nearly free: if a request is denied with t tokens short, the wait is t / refillRate. One division, computed from state already in hand. An algorithm choice that makes a wishlist feature cheap is worth a sentence in the round — it shows the choice had consequences you tracked.

Invariants, stated out loud

- 0 <= tokens <= capacity, always
- refill is monotonic: elapsed time never decreases tokens
- one key -> one state; resolved config cached on it
- the store's size is bounded; eviction is lossless by the
  full-bucket argument