LRU Cache

Least Recently Used Cache

Design a fixed-size key-value store that drops the entry nobody has touched for the longest time. Both operations must run in constant time.

Overview

A cache keeps a small number of items close at hand so that the next request for one of them is fast. It has a fixed capacity, so when it is full and a new item arrives, something has to go. The LRU rule picks the entry that was used least recently: if nobody has asked for it in a while, it is the best guess for what nobody will ask for next.

The interview version asks for two operations, get(key) and put(key, value), both in O(1) time. That constraint is the whole problem. A dict alone finds a key in one step but cannot tell you which key is oldest. A list alone keeps order but needs a scan to find a key. The classic answer combines the two: a hash map for lookup and a doubly linked list for recency order, with every node shared by both.

Interviewers use this problem to watch how you combine data structures, whether you handle pointer updates without bugs, and whether you can make a small class safe for many threads. A strong answer names the two structures in the first minute, explains why the node must carry its key, and writes the code with sentinel nodes so there are no special cases.

Scoping the problem

Before writing code, ask these questions; each answer changes the design a little.

What counts as a use: reads only, or writes too? — Decides whether put on an existing key moves it to the front — Both
What does get return on a miss? — None, a default, or -1 as in the LeetCode version — Caller's choice; the code below takes a default
Is capacity fixed after construction? — A shrinking capacity means evicting several entries at once — Fixed
Will many threads share one cache? — Adds a lock, and decides how fine-grained it is — Yes, one lock
Do entries expire on their own (TTL)? — Needs a timestamp per node and an expiry check — Follow-up, not the core
What are the keys? — Anything hashable; the cache never inspects them — Hashable objects

Two structures, one node

The hash map answers 'where is this key?' in one step. The linked list answers 'which key was used least recently?' in one step: it is the one at the back. Each cache entry is one node, and both structures point at that same node.

The list has to be doubly linked. To unlink a node in O(1) you need its predecessor, and only a prev pointer gives you that without a scan from the head. The two sentinel nodes (a head and a tail that never hold data) remove the special cases for an empty list and for the first or last node.

How get and put move nodes

Every successful get and every put ends with the touched node at the front of the list. Eviction takes the node at the back, then uses the key stored in that node to delete the dict entry.

The trace below runs the code on a cache of capacity 2. The order column lists keys from most recent to least recent.

1 — put(a, 1) — a — a — insert at front
2 — put(b, 2) — a, b — b, a — insert at front
3 — get(a) — a, b — a, b — hit; a moves to the front
4 — put(c, 3) — a, c — c, a — full; b at the back is evicted
5 — put(a, 10) — a, c — a, c — update in place, then move to the front

Why the node stores its key

Eviction starts from the list, not from the dict. The list hands back the oldest node, and the cache must now delete that node's entry from the dict. If the node held only a value, the only way to find the matching dict entry would be to scan every entry and compare pointers, which is O(n). Storing the key in the node keeps eviction O(1). Interviewers listen for this sentence.

value only — scan the dict for the entry whose node is this one — O(n)
key and value — del map[node.key] — O(1)

Thread safety

One threading.Lock in LRUCache wraps each public method. Both structures change together on every call, so a lock around get is needed too: a plain read still moves a node. Python's Lock is not reentrant, so the private helpers never take the lock again; only the public methods do. The lock supports with, which releases it even when an exception is raised.

One lock per cache (the code below) — Every operation; simplest to reason about — All threads serialize on one lock
Segment the key space into N caches, each with its own lock — Operations on different segments run in parallel — LRU order is only approximate across segments
No lock, one owning thread — Nothing needs protection — Other threads must send requests through a queue

The same idea in the standard libraries

You should be able to write the two-structure version by hand, and also know that you would rarely ship it. Say both in the interview.

Python collections.OrderedDict — move_to_end(key) on a hit, popitem(last=False) to evict the oldest — The docs say its reordering is efficient and that it suits LRU caches
Python functools.lru_cache — A decorator; keeps the maxsize most recent calls, default 128 — Thread-safe; maxsize=None turns eviction off
Java LinkedHashMap with access order — The special constructor orders entries from least to most recently accessed; override removeEldestEntry to evict — Not synchronized; wrap it or lock around it
Redis allkeys-lru — Samples a few keys at random and evicts the one idle longest — An approximation of LRU, chosen to save memory; maxmemory-samples (5 in the docs' example) tunes it

What you will be able to do

Explain in one minute why a dict plus a doubly linked list gives O(1) get and put.
Write the cache with sentinel nodes and no special cases, and trace it on a small input.
Say why the node stores its key and what breaks without it.
Make the class safe for many threads with one lock, and describe the finer-grained options.
Name the built-in versions in Python, Java and Redis, and when to use them instead.

Functional requirements

get(key) returns the value if the key is present, otherwise a default; a hit makes the entry the most recently used
put(key, value) inserts a new entry or updates an existing one, and makes it the most recently used
When the cache is full, put evicts the least recently used entry before inserting
Capacity is fixed at construction and must be positive
Keys may be any hashable object

Non-functional requirements

get and put run in O(1) time on average, including eviction
Memory is O(capacity): one node and one dict entry per stored key
Safe for concurrent get and put from many threads
The two internal structures are never exposed; callers see only get, put and len

Interview questions

Why does the list have to be doubly linked? A singly linked list is simpler.
How would you add a time-to-live so entries expire on their own?
Would you use OrderedDict or LinkedHashMap instead of writing the list yourself?
Your cache has one lock. How would you reduce contention with many threads?
When is LRU the wrong eviction policy?
What bugs do people write in this problem, and how do you avoid them?