How do you design an LRU cache? | Interview Question

Q: How do you design an LRU cache?

**Target Audience:** Developers preparing for coding and system design interviews who know maps and classes in Python. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Picture a small desk with room for exactly five books, and a huge library down the hall. Fetching a book from the library takes ten minutes; grabbing one from the desk takes a second. When you need a sixth book and the desk is full, one book has to go back to the library. Which one? A sensible rule: **send back the book you have not touched for the longest time.** The book you opened a minut

The problem

Question presented to candidate: "Design an LRU cache class in Python with get(key) and put(key, value), both O(1). When it is full, put must evict the least recently used key. Then tell me what you would change for a real service."

What a strong answer should cover:

LRU definition and the two jobs: O(1) lookup by key and O(1) maintenance of recency order.
The standard structure: a dict from key to node plus a doubly linked list ordered by recency, with eviction at the old end.
Both get and put count as a use; updating an existing key never evicts; a miss leaves the order alone.
The Python shortcut collections.OrderedDict with move_to_end(key) and popitem(last=False), and why a plain dict is awkward (assigning to an existing key does not move it).
Beyond the coding round: LRU vs FIFO/LFU, thrashing on scans, locks for threads, TTL, and functools.lru_cache for memoising functions.

Clarifying questions expected:

Is capacity counted in entries or bytes, and can it be 0?
Does put on an existing key count as a use?
Is the cache shared between threads?

Code / implementation expected: Yes — an LRUCache class in Python 3, using OrderedDict or a hand-written dict plus doubly linked list.

lru
design

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for coding and system design interviews who know maps and classes in Python.
Difficulty: Hard
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Picture a small desk with room for exactly five books, and a huge library down the hall. Fetching a book from the library takes ten minutes; grabbing one from the desk takes a second. When you need a sixth book and the desk is full, one book has to go back to the library. Which one?

A sensible

The solution is hidden so you can try first

15 min read · 14 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonLRU trace: every get and put, with the eviction and the recency order

Practice

PythonHit rate on one workload: LRU vs FIFO, and the loop that defeats LRU

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.