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.

Finished this one? 0 / 76 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