CODING CHALLENGE · N°71

LRU Cache, Constraint by Constraint

Medium FDEInterviewData Structures

The incremental-coding round, packaged: a cache that becomes bounded, then least-recently-used, then instrumented — each stage invalidating the shape of the last. Tests whether your first version can absorb the next requirement. Hidden tests cover the final behaviour.

The problem

Implement a class LRU that grows through four stated stages. (1) LRU(capacity) with get(key) returning the value or None/null, and put(key, value). (2) Never hold more than capacity entries. (3) When full, an insert evicts the least recently used key; both get and put count as a use, and writing an existing key updates its value and refreshes recency without changing the size. (4) stats() returns hits and misses: a get that finds a key is a hit, one that does not is a miss, and put affects neither.

EXAMPLE 1

Input cap 2; put a,b; get a; put c

Output b evicted

a was used more recently than b

EXAMPLE 2

Input cap 2; put a; put a again

Output size stays 1

a write to an existing key is not an insert

EXAMPLE 3

Input get on a missing key

Output None + miss counted

stats distinguishes hits from misses

CONSTRAINTS

get and put must both count as a use for recency purposes.
Writing an existing key updates the value and refreshes recency; the size must not change.
stats() returns hits and misses from get only — put counts as neither.
A capacity of 0 must hold nothing: every get misses.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement LRU with get, put, size() and stats() meeting all four stages at once.

HINTS — 4 IDEAS

Insertion-ordered maps give you recency for free: on a use, delete the key and re-insert it so it becomes most-recent.
Evict by taking the first key of the map — that is the least recently used one.
Handle the existing-key write before the capacity check, or you will evict on a write that adds nothing.
Capacity 0 is the edge case that catches most implementations: the insert must be a no-op, not an eviction of itself.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

The incremental round is not about the final data structure — it is about whether your first version could absorb the second requirement. Build a plain dictionary first, then add a capacity bound, then recency, then instrumentation, and notice which of those additions forced a rewrite.

The clean shape keeps insertion order as the recency order: a hit moves the key to the most-recent end, a write of an existing key updates the value and refreshes recency without changing size, and an insert past capacity evicts the least-recent key. Python’s dict and JavaScript’s Map both preserve insertion order, so delete-then-reinsert is the whole trick.

Complexity

O(1) amortised for get and put; O(capacity) space.

Common mistakes

Treating a write to an existing key as an insert — the size must not change and the key must become most-recent.
Counting a miss as a hit in stats(), or counting an eviction as a miss.
Refreshing recency on put but not on get, so a hot read-only key gets evicted.
Writing a clever compressed first version that cannot absorb the next constraint — the exact failure this round format is designed to catch.

Where this shows up

Anthropic’s reported coding assessment and Sierra’s live incremental round both escalate constraints on a small problem rather than asking one hard question. The signal is adaptability: interviewers watch whether your first solution was over- or under-engineered and how gracefully you refactor when the ground moves. Narrating what breaks before you refactor is worth more than the refactor itself.

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Interview Prep Forward Deployed Engineering