Design an LRU Cache with O(1) get and put — why doubly linked list + hash map?

Q: Design an LRU Cache with O(1) get and put — why doubly linked list + hash map?

**Target Audience:** Developers preparing for coding interviews who know classes and references in Python and want to justify the LRU design, not just recite it. **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 Think of a queue of people at a coffee shop where the barista has a strange rule: **whoever just ordered goes to the back of the line, and when the shop is full, the person at the front has to leave.** The person at the front is the one who has waited longest since their last order, the "least recently used" customer. Two things must be fast. When s

The problem

Question presented to candidate: "Implement an LRU cache in Python with get and put both in O(1), without using OrderedDict. Explain why you need a doubly linked list together with a hash map, and what would go wrong with an array or a singly linked list."

What a strong answer should cover:

The three required operations: find by key, move any entry to the most-recent end, evict the least-recent end, all in O(1).
Why each alternative fails: list of keys (O(n) shifts), dict only (no order), heap or tree (O(log n)), singly linked list (O(n) to find the predecessor).
Doubly linked list with sentinel head and tail; the dict maps key to node; the node stores its key for eviction.
Exact steps: unlink is 2 pointer writes, push front 4; eviction is tail.prev plus del self.map[node.key].
Python details: a small Node class with __slots__, dict.get for the lookup, identity checks with is for sentinels, and OrderedDict as the library equivalent.

Clarifying questions expected:

May I use OrderedDict, or should I build the list myself?
Does put on an existing key count as a use?
Can capacity be 0?

Code / implementation expected: Yes — an LRUCache class with a Node class, a dict and two sentinels in Python 3.

lru
hash map
Amazon

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 interviews who know classes and references in Python and want to justify the LRU design, not just recite it.
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

Think of a queue of people at a coffee shop where the barista has a strange rule: whoever just ordered goes to the back of the line, and when the shop is full, the person at the front has to leave. The person at the front is the one who has waited

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.

PythonHand-written hash map + doubly linked list with sentinels, checked after every call

Practice

PythonArray vs singly vs doubly linked list: hidden steps per access as capacity grows