← Back to DevBytes
Developer Tutorial July 12, 2026 11 min read

Interview Guide: LRU Cache Problems and Solutions

Understanding LRU Cache: The Core Concept

An LRU Cache (Least Recently Used Cache) is a data structure that stores a fixed number of items and evicts the least recently accessed entry when the cache reaches capacity and a new item needs to be inserted. The fundamental rule is simple: if you haven't used something in a while, and the cache is full, it's the first thing to go. This policy mirrors real-world behavior patterns where recently accessed data tends to be accessed again soon — a phenomenon known as temporal locality.

At its heart, an LRU Cache must support two operations with optimal time complexity:

Both operations must typically run in O(1) time complexity to be considered an efficient solution in technical interviews.

Why the LRU Cache Problem Matters in Interviews

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

This problem sits at the intersection of multiple critical computer science domains. Interviewers love it because it tests a candidate's ability to:

Top-tier companies including Google, Meta, Amazon, Microsoft, and Stripe have all asked variants of this problem. Mastering it gives you a reliable template you can adapt for related problems like LFU Cache, TTL-based expiration, or multi-level caching systems.

Data Structure Breakdown: Hash Map + Doubly Linked List

The brilliant insight behind the O(1) LRU Cache is the marriage of two complementary data structures:

1. Hash Map (Dictionary)

Maps keys directly to node references (pointers). This gives us O(1) lookup to find any node in the linked list without traversing. Without this, finding a node to mark it as recently used would be O(n).

2. Doubly Linked List

Maintains the order of items from most-recently-used (head) to least-recently-used (tail). Why doubly linked? Because we need O(1) removal of any node from the middle of the list (when an existing key is accessed and needs to move to the front). With a singly linked list, removing an arbitrary node requires finding its predecessor, which is O(n). The double links let us splice a node out using only references to the node itself and its immediate neighbors.

Here's how the two structures collaborate:

Complete Implementation in Java

Let's walk through a production-quality implementation. This is the canonical solution expected in interviews.

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    
    // Internal node class for the doubly linked list
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final Map<Integer, Node> cache;  // key -> node reference
    private final Node head;  // dummy head (most recent side)
    private final Node tail;  // dummy tail (least recent side)
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        
        // Initialize dummy nodes that simplify edge cases
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;  // not found
        }
        // Move to front (most recently used)
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = cache.get(key);
        
        if (node != null) {
            // Key exists: update value and move to front
            node.value = value;
            moveToHead(node);
            return;
        }
        
        // Key doesn't exist: check capacity
        if (cache.size() == capacity) {
            // Evict least recently used (node before dummy tail)
            Node lru = tail.prev;
            removeNode(lru);
            cache.remove(lru.key);
        }
        
        // Create and insert new node
        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        addToHead(newNode);
    }
    
    // --- Helper methods for list manipulation ---
    
    private void addToHead(Node node) {
        // Wire node between dummy head and current first real node
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(Node node) {
        // Splice out: link node.prev and node.next directly
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void moveToHead(Node node) {
        // Two-step process: remove from current position, then add to head
        removeNode(node);
        addToHead(node);
    }
}

Notice the use of dummy head and tail nodes. These sentinel nodes eliminate null checks at the boundaries. Without them, adding to an empty list or removing the last element requires special-case branching. With dummies, the list always has at least two nodes (head and tail), so head.next and tail.prev are never null. This pattern is widely considered a best practice for linked list implementations.

Python Implementation with the Same Approach

Here's the equivalent implementation in Python, which many interviewers also accept. The structure mirrors the Java version exactly.

class LRUCache:
    
    class Node:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        
        # Dummy head and tail
        self.head = self.Node(0, 0)
        self.tail = self.Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        self._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
            return
        
        # Eviction check
        if len(self.cache) == self.capacity:
            lru = self.tail.prev
            self._remove_node(lru)
            del self.cache[lru.key]
        
        # Insert new node
        new_node = self.Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)
    
    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

Language-Specific Shortcuts: Java's LinkedHashMap

In a real Java interview, if the interviewer allows it, you can leverage LinkedHashMap which already combines a hash map with a linked list and supports access-ordering. This turns the problem into a remarkably concise solution:

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;
    
    public LRUCache(int capacity) {
        // Constructor args: initialCapacity, loadFactor, accessOrder
        // accessOrder=true means ordering is based on access, not insertion
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // Called after every put. Return true to remove eldest.
        return size() > capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
}

Caveat: While this solution is elegant and shows deep library knowledge, many interviewers will ask you to implement the underlying mechanics yourself. Use this only if you've already demonstrated the from-scratch version or if the interviewer explicitly says standard library solutions are acceptable. It's valuable to know both approaches.

Step-by-Step Walkthrough with Concrete State Examples

Let's trace through a concrete example to solidify understanding. Suppose we initialize LRUCache(2) with capacity 2.

Initial State

HEAD <-> TAIL
cache: {}
size: 0 / capacity: 2

After put(1, 10)

A new node with key=1, value=10 is created, added to the head, and inserted into the cache map.

HEAD <-> [Node(key=1, val=10)] <-> TAIL
cache: {1 -> Node(1,10)}
size: 1 / capacity: 2

After put(2, 20)

Still below capacity. New node goes to head. The list now has two real nodes: Node(2) at head (most recent), Node(1) at tail side (least recent).

HEAD <-> [Node(key=2, val=20)] <-> [Node(key=1, val=10)] <-> TAIL
cache: {2 -> Node(2,20), 1 -> Node(1,10)}
size: 2 / capacity: 2

After get(1)

Key 1 exists. We find its node via the hash map, remove it from its current position (just before tail), and move it to head. Node(1) becomes most recent; Node(2) shifts toward tail.

HEAD <-> [Node(key=1, val=10)] <-> [Node(key=2, val=20)] <-> TAIL
cache: {1 -> Node(1,10), 2 -> Node(2,20)}
size: 2 / capacity: 2

After put(3, 30) — triggers eviction

Cache is full. The least recently used node is Node(2) (it sits just before dummy tail). We remove Node(2) from the list, delete key 2 from the hash map, then insert Node(3) at head.

HEAD <-> [Node(key=3, val=30)] <-> [Node(key=1, val=10)] <-> TAIL
cache: {3 -> Node(3,30), 1 -> Node(1,10)}
size: 2 / capacity: 2
// Key 2 was evicted

This trace demonstrates that every operation maintains the invariant: the list head is always the most recently used item, and the node just before the dummy tail is always the least recently used item.

Common Pitfalls and How to Avoid Them

During implementation, candidates frequently stumble on several subtle issues. Being aware of these will set you apart:

Interview Follow-Up Questions and Extensions

Once you've presented the basic solution, interviewers often probe deeper. Prepare for these variations:

Thread-Safe LRU Cache

How would you make this cache thread-safe? The naive approach is to wrap every method with synchronized, but that creates a bottleneck. A more sophisticated answer uses ReentrantReadWriteLock, allowing multiple concurrent reads while serializing writes. You might also discuss using ConcurrentHashMap combined with an atomic linked structure, though this is significantly more complex.

LFU (Least Frequently Used) Cache

This is the natural evolution. Instead of evicting based on recency, LFU evicts based on access frequency. It typically requires a frequency map and a doubly linked list per frequency group. Mentioning that you've thought about this shows breadth.

Time-Based Expiration (TTL)

What if entries should expire after a fixed duration regardless of access? This adds a third dimension. You might maintain a separate priority queue ordered by expiration time, or run a background cleanup thread that periodically scans for expired entries.

Capacity Planning

How do you determine the right capacity? This shifts the discussion to systems design: hit rate curves, memory constraints, and workload analysis. A good answer references that you'd instrument hit/miss ratios in production and tune accordingly.

Best Practices for Interview Success

Conclusion

The LRU Cache problem is a quintessential data structure design exercise that demonstrates your ability to synthesize fundamental building blocks into a cohesive, efficient system. The canonical solution — a hash map paired with a doubly linked list guarded by dummy nodes — achieves the coveted O(1) time complexity for both core operations and has become a staple of technical interviews at leading technology companies. By internalizing the pointer manipulation patterns, understanding the eviction semantics, and anticipating follow-up questions about thread safety and alternative policies, you transform this problem from a source of anxiety into a reliable opportunity to showcase engineering maturity. Master the implementation in your preferred language, practice tracing through state transitions aloud, and you'll approach any LRU Cache interview with confidence and clarity.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles