LRU Cache Interview Question Explained: Step-by-Step Solution

The LRU (Least Recently Used) Cache is one of the most commonly asked interview questions at top tech companies. It appears frequently at Google, Meta, Amazon, Anthropic, Stripe, and virtually every company that interviews software engineers. There's a good reason for this: it tests multiple skills simultaneously.

First, it tests your understanding of data structures — specifically, how to combine a hashmap with a doubly linked list to achieve O(1) for both get and put operations. Second, it tests your ability to design a clean API and handle edge cases. Third, the implementation requires careful pointer manipulation, which reveals your attention to detail and ability to write bug-free code under pressure.

If you're preparing for technical interviews, this is a must-know problem. Let's break it down completely.

The problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement two operations: get(key) — returns the value if the key exists, otherwise returns -1; and put(key, value) — inserts or updates the value. If the cache reaches its capacity, it should evict the least recently used item before inserting a new one.

Both get and put must run in O(1) average time complexity. This is the key constraint that makes the problem interesting — without it, you could use a simple array and scan for the LRU item.

The 'least recently used' policy means: every time you access a key (via get or put), that key becomes the most recently used. When you need to evict, you remove the key that was accessed longest ago. Think of it like a stack of papers on your desk — every time you use a paper, it goes to the top. The paper at the bottom is the one you haven't touched in the longest time.

Your first instinct might be to use a HashMap — it gives O(1) get and put. But a HashMap doesn't maintain insertion or access order. You need to know which key was least recently used, and a HashMap can't tell you that.

What about using a HashMap + a timestamp for each entry, then scanning for the oldest? The scan would be O(n), violating our time complexity requirement.

What about an OrderedDict (Python) or LinkedHashMap (Java)? These actually work and are valid interview answers — but the interviewer will typically ask you to implement the ordering mechanism yourself. That's where the doubly linked list comes in.

The key insight: use a HashMap for O(1) key lookups, and a doubly linked list to maintain the usage order. The HashMap maps keys to nodes in the linked list, and the linked list is ordered from most recently used (head) to least recently used (tail).

The doubly linked list supports three operations in O(1): (1) Remove a node from anywhere in the list (given a reference to it), (2) Add a node to the front (head) of the list, and (3) Remove the node from the back (tail) of the list.

Here's how the operations work: For get(key) — look up the key in the HashMap. If it exists, move the corresponding node to the front of the linked list (mark it as most recently used) and return the value. If it doesn't exist, return -1.

For put(key, value) — if the key already exists, update the value and move the node to the front. If the key doesn't exist, create a new node, add it to the front of the list, and add the key-node mapping to the HashMap. If the cache is now over capacity, remove the node at the tail of the linked list (least recently used) and delete its key from the HashMap.

Here's the clean, interview-ready Python implementation: class Node: def __init__(self, key: int, val: int): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = {} # key -> Node # Dummy head and tail to avoid edge cases self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: Node): node.prev.next = node.next node.next.prev = node.prev def _add_to_front(self, node: Node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._add_to_front(node) return node.val def put(self, key: int, value: int): if key in self.cache: self._remove(self.cache[key]) node = Node(key, value) self.cache[key] = node self._add_to_front(node) if len(self.cache) > self.cap: lru = self.tail.prev self._remove(lru) del self.cache[lru.key]

The key design decisions: (1) Using dummy head and tail nodes eliminates null checks and edge cases — this is a common technique that interviewers love to see. (2) Storing the key in the Node allows us to delete from the HashMap when evicting from the tail. (3) The _remove and _add_to_front helpers keep the code clean and avoid duplication.

Time complexity: Both get() and put() are O(1). HashMap lookup is O(1). Removing a node from the doubly linked list is O(1) because we have a direct reference. Adding to the front is O(1). Everything is constant time.

Space complexity: O(capacity). We store at most 'capacity' nodes in the linked list and 'capacity' entries in the HashMap. Each node stores a key-value pair plus two pointers.

This is optimal — you can't do better than O(1) for both operations, and you need at least O(capacity) space to store the cache entries.

Interviewers often extend the basic LRU cache with follow-ups. Here are the most common ones and how to approach them:

Thread safety: How would you make this thread-safe? Use a lock (mutex) around get and put. For better performance, consider a read-write lock or lock-free data structures. Mention that Python's GIL provides some protection but isn't sufficient for a production cache.

TTL (Time-to-Live): How would you add expiration? Store a timestamp with each node. On get(), check if the entry has expired. You could also add a background thread that periodically scans for expired entries, or use a separate data structure (like a min-heap ordered by expiration time) for efficient cleanup.

LFU (Least Frequently Used): How would you change this to LFU? You'd need to track access frequency for each key and evict the least frequently used. The optimal solution uses a HashMap of frequency buckets, each containing a linked list of nodes with that frequency. This is a harder follow-up — LeetCode 460.

Distributed LRU Cache: How would you distribute this across multiple machines? Use consistent hashing to determine which machine stores each key. Each machine runs its own LRU cache. Discuss tradeoffs: cache misses when a machine goes down, replication for availability, and the invalidation problem.

Start by clarifying: Ask about the expected operations, time complexity requirements, and whether the cache needs to be thread-safe. Even though you know the answer, asking shows good habits.

Explain your approach before coding: 'I'll use a HashMap for O(1) lookups combined with a doubly linked list to maintain usage order. The front of the list is most recently used, the back is least recently used.' This takes 30 seconds and immediately tells the interviewer you know what you're doing.

Use dummy nodes: Mention that you're using sentinel/dummy head and tail nodes to simplify edge case handling. This is a sign of experience.

Test with a small example: After implementing, trace through put(1,1), put(2,2), get(1), put(3,3) with capacity=2. Show that key 2 gets evicted (not key 1, because get(1) made it recently used).

Know the complexity cold: Be ready to explain why every operation is O(1) without hesitation. If you pause on this, it signals you might not fully understand the solution.