Why this matters: the data structures for this problem are famous, which is precisely why they're not the test. What's graded is whether you can derive the O(1) shape from the requirements out loud, and whether your design separates what the cache stores from how it decides who gets evicted — because that separation is where all the future change in a cache library lands.

Start from the operations and their promises

Three operations, each with a promise the requirements just made:

get(key)      -> value | null-as-miss; refreshes the entry's standing
put(k, v)     -> update if present (refresh standing);
                 insert if new (evict first when at capacity)
remove(key)   -> drop the entry; not a miss, not a use

Two of the three touch recency, and one of them — get — is the hot path. Whatever records "this entry was just used" runs on every read, so it must be O(1) or the cache damages the workloads it exists to help. That single sentence drives the entire structure.

The O(1) shape — and the insight that makes it true

Recency is an ordering: most recently used at one end, the eviction victim at the other. Orderings that change on every access want a doubly-linked list — unlink from wherever you are, relink at the head, both O(1). Lookup wants a hash map. So far, the version everyone memorized.

Here is the part that separates a derived design from a recited one: the map must point at the list node, not just at the value. If the map stores only values, then "refresh this entry's standing" means finding its node — an O(n) walk down the list, on every get. The whole O(1) claim lives or dies on that one pointer:

map:   key -> Node                     (not key -> value)
list:  head <-> ... <-> tail           (head = just used, tail = victim)
Node:  key, value, prev, next          (knows its own key, for eviction)

The node carrying its key matters too: when the tail is evicted, the cache must delete the map entry, and it learns which one from the node itself. Say both of these out loud in the round — they're the difference between knowing the answer and understanding it.

Storage and policy are different jobs

The map-and-list machine actually contains two responsibilities wearing one coat. Storage answers "what's in the cache" — key to entry, capacity accounting. Eviction policy answers "who leaves when we're full" — which is a preference, and preferences are the part of a library that product conversations keep reopening.

So the design decision: put the eviction decision behind its own seam.

EvictionPolicy:
    onAccess(entry)     -- a read or update happened
    onInsert(entry)     -- a new entry arrived
    onRemove(entry)     -- an entry left (any reason)
    chooseVictim() -> entry

The interesting part — and the honest part — is that a bare chooseVictim() is not enough. Least-recently-used cannot exist behind an interface that never tells the policy about accesses. The hooks are the real design: the policy owns the ordering metadata (our linked list), and the storage layer notifies it at the three moments that matter. Designing that interface truthfully, so the policy you actually want is implementable behind it, is the open/closed principle done for a living reason: eviction preferences change; capacity bookkeeping doesn't. And keeping the map ignorant of prev/next pointers is separation of concerns you can point to in the code.

put is two paths, not one

The requirements made updates and inserts genuinely different:

put(existing key)   replace value, refresh standing    -- never evicts
put(new key)        at capacity? evict victim first    -- then insert at head

Collapsing these into one path is the most common correctness bug in this problem — an update at capacity that evicts, or worse, inserts a second node for the same key so the list and map disagree about how many entries exist. Two named paths, two different obligations.

Stats are API, not garnish

The hit-rate requirement needs a definition before it needs a counter: a hit is a get that returns a value; a miss is a get that doesn't. remove is neither. Updates are not hits — they're writes. Give the counters a home (stats() returning hits, misses, evictions) and the definition is enforceable instead of folklore. Interviewers notice candidates who treat observability as part of the contract rather than a bolt-on — it's single responsibility applied to a surface people forget is a surface.

The invariants, stated out loud

- map.size == list.length == entry count <= capacity
- every list node is reachable from the map, and vice versa
- an entry is in the cache iff it is in BOTH structures
- only get/put/remove mutate either structure

The first invariant is the one to enforce in code review of your own design: any operation that touches one structure and not the other is a bug you've just proven exists.

What we rejected, and why

Map-to-value with list search. Already buried above, but name it: it compiles, it passes the small test, and it's O(n) on the hot path — the classic "O(1)" cache that isn't.

Timestamps instead of ordering. Stamp each entry with a last-used time, scan for the oldest at eviction. Reads get cheaper to record, but eviction becomes O(n) and "scan everything while full" is exactly when you can least afford it. An ordering maintained beats an ordering recomputed.