Get 20 Free Credits on Sign Up! Claim Now
Master the LRU cache interview question in Python with a clear O(1) design, complete implementation, step-by-step eviction trace, targeted tests, common mistakes, and advanced follow-ups.
The least recently used cache problem looks compact, but it tests several skills at once: choosing data structures, defending complexity, maintaining pointer invariants, handling edge cases, and communicating while coding. This guide turns the common LRU cache interview question in Python 2026 candidates are practicing into a repeatable solution you can explain under pressure.
You will build the cache from first principles with a hash map and a doubly linked list, trace an eviction, test failure-prone cases, and prepare for follow-ups such as concurrency, time-to-live expiration, and distributed caching. The goal is not to memorize forty lines of code. It is to understand why every line exists.
Design an LRU cache with a fixed positive capacity. It supports two operations:
get(key): return the value when the key exists; otherwise return -1. Reading an existing key makes it the most recently used item.put(key, value): insert or update a key. The inserted or updated key becomes most recently used. If the cache exceeds capacity, remove the least recently used item.A typical interviewer also requires average O(1) time for both operations.
Before proposing a structure, restate the contract. Ask whether capacity can be zero, whether keys and values are integers, whether -1 is a valid stored value, and whether the cache must be thread-safe. Many coding-platform versions guarantee positive capacity and integer values, but a production API may need different error and miss semantics.
The obvious task is implementing a cache. The deeper evaluation usually covers four areas.
First, can you translate “recently used” into an order that changes after both reads and writes? Second, can you identify why one familiar data structure is insufficient? Third, can you preserve list invariants without losing nodes or leaving stale map entries? Finally, can you narrate trade-offs, test your work, and adapt it when requirements change?
That last point matters in a real interview loop. A correct silent solution is weaker evidence than a correct solution with clear reasoning. If you are preparing for a broader loop, pair this exercise with the communication and design drills in the Amazon SDE II interview preparation guide.
A hash map gives average O(1) lookup by key, but it does not by itself model the required recency operations in a language-independent design. A simple list models order, but finding a node by key takes O(n).
The standard solution combines them:
O(1) time.O(1).Why doubly linked rather than singly linked? To remove an arbitrary node in constant time, you need access to both neighbors. A singly linked list would require finding the predecessor unless you introduced more complicated bookkeeping.
Two sentinel nodes make the pointer logic safer. The head sentinel sits before the most recent real node. The tail sentinel sits after the least recent real node. The list is never structurally empty: when no entries exist, head.next is tail and tail.prev is head.
Strong candidates name the rules their code must preserve:
head is the most recently used.tail is the least recently used.These invariants turn debugging into a focused exercise. If a test fails, ask which rule was broken instead of staring at pointer assignments.
Here is an interview-ready implementation. It rejects non-positive capacity explicitly; if the interviewer guarantees positive capacity, mention that the check is defensive.
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity < 1:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node() # most-recent side
self.tail = Node() # least-recent side
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
before = node.prev
after = node.next
before.next = after
after.prev = before
def _insert_after_head(self, node: Node) -> None:
first = self.head.next
node.prev = self.head
node.next = first
self.head.next = node
first.prev = node
def _mark_recent(self, node: Node) -> None:
self._remove(node)
self._insert_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.nodes:
node = self.nodes[key]
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._insert_after_head(node)
if len(self.nodes) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.nodes[lru.key]
The helpers are intentionally small. _remove handles detachment, _insert_after_head handles promotion, and _mark_recent composes the two. Centralizing pointer changes reduces duplicated logic in get and put.
Notice that a node stores both key and value. The key is required during eviction: the tail tells you which node to remove, and the node’s key tells you which dictionary entry to delete.
Assume capacity is two.
put(10, "A") produces recency order 10.put(20, "B") produces 20 -> 10.get(10) returns "A" and promotes 10, producing 10 -> 20.put(30, "C") temporarily produces 30 -> 10 -> 20.tail: key 20.30 -> 10, and get(20) misses.Say the order aloud while tracing. It demonstrates that a successful get changes recency, a detail candidates frequently miss.
Dictionary lookup, insertion, and deletion are average O(1). Every list operation changes a fixed number of pointers, so it is O(1)). Therefore, getandputare averageO(1)`.
The dictionary and list contain at most capacity real entries, so auxiliary space is O(capacity).
Use the word “average” for Python dictionary operations. Claiming an unconditional worst-case O(1) lookup is imprecise. In most interviews, average constant time is the intended requirement.
Do not stop after the happy path. Run a compact test set that targets each branch and invariant:
cache = LRUCache(2)
assert cache.get(99) == -1 # miss on empty cache
cache.put(1, 10)
cache.put(2, 20)
assert cache.get(1) == 10 # read promotes key 1
cache.put(3, 30) # key 2 should be evicted
assert cache.get(2) == -1
assert cache.get(3) == 30
cache.put(1, 100) # update without growing
assert cache.get(1) == 100
single = LRUCache(1)
single.put(7, 70)
single.put(8, 80)
assert single.get(7) == -1
assert single.get(8) == 80
Also discuss repeated reads, updating the current least-recent key, inserting an existing key when full, and capacity one. A common bug creates a new node during an update but leaves the old node linked. Another removes the evicted node from the list but forgets to delete its dictionary entry.
A concise explanation can sound like this:
“I need key lookup and recency updates in average constant time. A dictionary gives lookup, while a doubly linked list gives constant-time removal and insertion when I already have the node. I will keep the most recent node by the head sentinel and the least recent by the tail sentinel. On a hit or update, I move the node to the front. On a new insertion that exceeds capacity, I remove the node before the tail and delete the same key from the map.”
Then code the list helpers first. Verify their pointer assignments before adding cache logic. This sequence keeps the core risk visible and makes it easier for the interviewer to follow.
For realistic practice, deliver that explanation aloud rather than only typing it. The seven-day AI mock interview plan provides a structured way to review clarity, pacing, and recovery after mistakes.
Using only a dictionary leaves the language-independent ordering problem unresolved. Using a list of keys makes promotion and lookup linear. Re-sorting entries by timestamps makes operations O(n log n) and introduces timestamp ties. Rebuilding the list after every access also violates the time requirement.
Python’s OrderedDict can implement an LRU cache compactly, but jumping to it immediately may hide the data-structure reasoning the question is designed to test. A good answer can mention it after the first-principles solution and explain when library code would be preferable in production.
Avoid overengineering, too. Generics, inheritance, and elaborate abstractions can consume time without improving the evidence the interviewer requested.
The map and list form one logical state, so operations that read or modify them must be synchronized together. A lock around each public operation is a simple starting point. Explain contention and correctness before attempting fine-grained locking. Review race conditions and lock trade-offs with these Python concurrency interview questions.
Store an expiration time per entry. On access, treat an expired entry as a miss and remove it. If expired entries must disappear without access, add background cleanup or an expiry-prioritized structure. Clarify whether LRU eviction and expiration are independent policies.
Least frequently used eviction prioritizes access count rather than recency. An O(1) LFU design typically needs a key-to-node map, frequency buckets, and a way to track the minimum frequency. It is a meaningfully different structure, not a small rename.
One in-process list is no longer enough. You must discuss partitioning, replication, consistency, failure recovery, hot keys, and whether recency is local to a shard or global. A globally exact LRU policy can be expensive; approximate eviction is often a conscious systems trade-off.
Spend five minutes clarifying requirements and deriving the two-structure design. Spend five minutes drawing the sentinels and stating invariants. Use fifteen minutes to implement helpers, get, and put. Spend five minutes tracing a capacity-two example. Use the final five minutes for tests, complexity, and one follow-up.
Repeat the exercise later from a blank editor. On the second attempt, focus on explanation quality and deliberate testing rather than raw speed. If you can recover from one intentionally introduced pointer bug by checking invariants, you understand the design more deeply than someone who only memorized the final code.
Yes. It remains a compact way to demonstrate hash maps, linked lists, API semantics, complexity analysis, testing, and design communication. Even when a specific company does not ask this exact problem, the reasoning transfers to many stateful design questions.
They eliminate special pointer branches for an empty list, the first real node, and the last real node. Every real node always has a predecessor and successor, which makes removal and insertion uniform.
get update recency?Yes, for the standard LRU contract. A successful read makes that item the most recently used. A miss does not change the order.
OrderedDict in the interview?Ask the interviewer. It is useful production knowledge, but many interviews expect you to implement the underlying map-plus-list design. Offer the library version as a follow-up after showing the fundamentals.
The most damaging bug is letting the dictionary and linked list disagree. Typical causes are forgetting to delete an evicted key, duplicating a node during update, or changing only one side of a pointer connection.
Before you say “done,” confirm that hits promote nodes, updates do not increase size, eviction removes the same entry from both structures, sentinels cannot be evicted, capacity-one behavior works, and your complexity claim says average O(1). That disciplined finish is what turns a familiar problem into convincing interview evidence.
Learn to solve a rate limiter interview question in Python with a thread-safe token bucket, deterministic tests, complexity analysis, common mistakes, and distributed-system follow-ups.
Prepare for Python concurrency interviews with 18 practical questions on asyncio, threads, processes, executors, race conditions, cancellation, the GIL, and free-threaded CPython.
Learn how to structure your behavioral interview answers using Situation, Task, Action, Result framework.
Read our blog for the latest insights and tips
Try our AI-powered tools for job hunt
Share your feedback to help us improve
Check back often for new articles and updates
CoPrep AI Interview Assistant completely changed how I approach technical interviews. Before CoPrep AI, I'd blank out under pressure and lose my train of thought mid-answer. Now I have a structured way to tackle any question. The real-time guidance helped me stay calm, articulate my reasoning clearly, and recover when I stumbled. I landed my offer after just three weeks of consistent practice. I genuinely can't recommend it enough.