CODING CHALLENGE · N°13

LRU Cache

Medium SystemsCachingData Structures

The eviction policy behind every cache with a size limit: when you run out of room, throw out whatever was used least recently. The trick is doing get and put in O(1) — an ordered hash map (Python dict / JS Map) gives you exactly that.

The problem

Implement a fixed-capacity LRU (least-recently-used) cache as a driver: lru_cache(capacity, ops) replays a list of operations and returns the results of the get calls (in order). Each op is a list: ["get", key] returns the stored value or -1 if absent, and counts as a use (the key becomes most-recently-used). ["put", key, value] inserts or updates the key (also most-recently-used); if that pushes the cache over capacity, evict the least-recently-used key. Only get results go into the returned list.

EXAMPLE 1

Input capacity=2, ops=[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]

Output [1, -1, -1, 3, 4]

put(3) evicts key 2; put(4) evicts key 1 — the classic trace

EXAMPLE 2

Input capacity=1, ops=[["put",1,1],["put",2,2],["get",1],["get",2]]

Output [-1, 2]

capacity 1 → each put evicts the previous key

EXAMPLE 3

Input capacity=2, ops=[["get",5]]

Output [-1]

a miss returns -1

CONSTRAINTS

Both get and put mark the key as most-recently-used.
On overflow, evict the least-recently-used key (the one untouched the longest).
A Python dict (or JS Map) preserves insertion order — pop and re-insert a key to move it to the most-recently-used end; the first key is the LRU.
Return only the values produced by get operations, in order.

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_cache(capacity, ops). Replay the ops against an LRU cache of the given capacity and return the list of results from the get calls.

HINTS — 4 IDEAS

Keep a dict/Map from key → value; its iteration order is your recency order (oldest first).
On get: if present, pop the key and re-insert it (now newest) before returning its value; else return -1.
On put: if the key exists, pop it first; set key → value (newest); then if size > capacity, delete the first (oldest) key.
The oldest key is next(iter(cache)) in Python / cache.keys().next().value in JS.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Combine two structures: a hash map for O(1) lookup by key, and a doubly linked list ordered by recency. The map stores nodes, not values, so from a key you can splice its node out and move it to the front in O(1). On get or put, move the touched node to the front (most recent); when you exceed capacity, evict the tail (least recent) and delete it from the map.

Complexity

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

Common mistakes

Backing it with an array or plain list — moving an element to the front is then O(n), losing the O(1) guarantee.
Updating recency only on put and not on get — a read must also mark the entry as recently used.
Off-by-one on capacity — evict when size exceeds capacity, and remember to update the map, not just the list.

Where this shows up

LRU is the default eviction policy across the stack — CPU caches, Redis and Memcached, database buffer pools, and browser caches all use it or a variant. The hash-map-plus-doubly-linked-list combo is the textbook way to get O(1) on both ordering and lookup, and it shows up any time you must bound memory while keeping the hot set.

▶  Watch it explained

Finished this one? 0 / 75 Challenges done

Explore the topic

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

Caching & Performance