Problem Statement
LRU Cache
A cache is a small box where you keep things you use often so you can grab them fast. But the box has limited room. An LRU cache (Least Recently Used cache) has a rule for what to throw out when the box is full: kick out the item you have not touched in the longest time. Think of a desk with space for only a few papers. Every time you read or write a paper, you move it to the top of the pile. When the desk is full and a new paper comes in, the one sitting forgotten at the bottom gets tossed. We need two operations: get(key) to read a value, and put(key, value) to store one, and both must run in O(1) time, meaning the work takes the same tiny amount of time no matter how many items are in the cache. To pull this off we combine two tools. A hash map (a lookup table that jumps straight to any item by its key, instantly) gives us fast finding. A doubly linked list (a chain of nodes where each node points to the one before it and the one after it) lets us reorder items fast. The most recently used item sits at the head (front) of the chain, and the least recently used sits at the tail (back), ready to be evicted.
Signals to notice
Brute force first
List + linear scan to find/evict — per operation. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
Hash map (key → node) + doubly linked list (ordered by recency). Get: look up in map, move to front. Put: add to front, evict from back if over capacity. Both. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on ops on LRUCache(2): put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4)
put(1,1): add 1 to front. map={1} | order: [1] (front→back)
put(2,2): add 2 to front. map={1,2} | order: [2,1]
get(1)→1: move 1 to front. order: [1,2] (2 now LRU)
put(3,3): add 3 to front, size 3>2 → evict tail.prev=2. map={1,3} | order: [3,1]
get(2)→-1: 2 not in map (evicted)
put(4,4): add 4 to front, size 3>2 → evict tail.prev=1. map={3,4} | order: [4,3]
get(1)→-1: 1 not in map (evicted)
get(3)→3: move 3 to front. order: [3,4]. Then get(4)→4: move 4 to front. order: [4,3]What must stay true
The doubly linked list maintains access order: most recent at front, least recent at back. The hash map gives access to any node for direct removal and reinsertion. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
get(key): if key in map: node=map[key]; remove(node); addFront(node); return node.val; else return -1
put(key,val): if key in map: remove(map[key])
node=Node(key,val); addFront(node); map[key]=node
if size(map) > capacity: lru=tail.prev; remove(lru); del map[lru.key]
# list order = front(MRU) ... tail(LRU); map gives O(1) node accessPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Using a singly linked list — you need removal from the middle, which requires a doubly linked list with previous pointers. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.