How to Implement LRU Cache for Technical Interviews

Understanding the LRU Cache Problem and Real-World Applications

In the high-stakes world of system architecture, memory is a finite resource. Whether you are designing a database buffer pool, a web browser's history, or a CPU's instruction cache, you will inevitably face the same critical question: "When the storage is full, what do we throw away?"

The answer is often the LRU (Least Recently Used) Cache. It is a cornerstone algorithm in computer science that balances speed and storage efficiency. Mastering LRU isn't just about passing an interview; it's about understanding how modern systems manage the delicate trade-off between concurrent applications performance and resource constraints.

The Technical Challenge: $O(1)$ Complexity

A naive implementation of LRU might use a simple list. However, finding an item in a list takes linear time, or $O(n)$. In high-performance systems, this is unacceptable. To achieve constant time complexity, $O(1)$, we must combine two data structures:

• 🔑
  Hash Map (Dictionary): For instant lookup of keys to nodes.
• 🔗
  Doubly Linked List: To maintain the order of usage (Head = Most Recent, Tail = Least Recent).

Implementation: Python LRU Cache

Here is a robust implementation using a Doubly Linked List and a Hash Map. This pattern is essential for anyone looking to implement graph data structures or complex memory management systems.

 class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {} # Hash Map for O(1) lookup
        # Dummy head and tail to simplify edge cases
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_to_head(self, node):
        """Adds a node right after the head (Most Recently Used position)"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """Removes a node from the linked list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            # Move accessed node to head (mark as recently used)
            self._remove_node(node)
            self._add_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Update existing value
            node = self.cache[key]
            node.value = value
            self._remove_node(node)
            self._add_to_head(node)
        else:
            # Create new node
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
            # Evict if over capacity
            if len(self.cache) > self.capacity:
                # Remove the node before tail (Least Recently Used)
                lru_node = self.tail.prev
                self._remove_node(lru_node)
                del self.cache[lru_node.key]

Real-World Applications

"The LRU Cache is the perfect example of Space-Time Tradeoff. We use extra memory (the Hash Map) to save processing time (avoiding linear searches)."

Key Takeaways

• Definition: LRU evicts the item that hasn't been accessed for the longest time.
• Structure: Requires a Hash Map + Doubly Linked List for $O(1)$ performance.
• Usage: Critical for databases, OS memory management, and caching layers.
• Advanced: For deeper understanding of memory structures, explore B-Tree implementation concepts.

Why Naive Data Structures Fail at Constant Time Cache Operations

The Naive Implementation Trap

Let's look at the code. This is what a "Junior" implementation looks like. It works, but it scales terribly.

class NaiveLRUCache:
  def __init__(self, capacity):
    self.capacity = capacity
    self.cache = []  # Storing tuples: (key, value)

  def get(self, key):
    # … BOTTLENECK: Linear Search O(n)
    # We must scan the entire list to find the key
    for i, (k, v) in enumerate(self.cache):
      if k == key:
        # Move to front – expensive operation
        item = self.cache.pop(i)
        self.cache.insert(0, item)
        return v
    return -1

  def put(self, key, value):
    # … BOTTLENECK: Linear Search O(n)
    # Check if key exists before adding
    for i, (k, v) in enumerate(self.cache):
      if k == key:
        self.cache[i] = (key, value)
        # Move to front
        item = self.cache.pop(i)
        self.cache.insert(0, item)
        return
    # Add new item
    if len(self.cache) >= self.capacity:
      self.cache.pop()  # Remove LRU – last item
    self.cache.insert(0, (key, value))

Notice the for loops? That is the enemy of speed. To fix this, we need a data structure that combines the fast lookup of a Hash Map with the fast reordering of a Linked List. This is a classic Space-Time Tradeoff.

Key Takeaways

• The Array Problem: Accessing an element by index is $O(1)$, but searching by value is $O(n)$.
• The Linked List Problem: Insertion/Deletion is $O(1)$ if you have the pointer, but finding that pointer is $O(n)$.
• The Solution: You need a Doubly Linked List (for order) combined with a Hash Map (for $O(1)$ lookup). This is the foundation of the standard LRU Cache.
• Deep Dive: To understand the underlying mechanics of these structures, explore Graph Data Structure implementation concepts, which rely heavily on node pointers.

The Put Operation: Insertion and Eviction Logic

Welcome to the heart of the LRU Cache. While the get operation is about retrieval, the put operation is where the real architectural gymnastics happen. You aren't just storing data; you are managing a finite resource.

When you call put(key, value), you are essentially asking the system to perform a delicate balancing act. You must handle two distinct scenarios: updating an existing entry (which requires re-ordering) or inserting a new one (which might trigger a cascade of deletions).

The Dual Nature of Insertion

To implement this efficiently, we rely on the concept of Composition. We are combining a Hash Map for $O(1)$ lookup and a Doubly Linked List for $O(1)$ ordering. This pattern is a classic example of Object Composition over inheritance.

Implementation: The Pythonic Approach

Here is the core logic. Notice how we handle the "unlink and relink" pointers. If you mess up the order of pointer assignment, you will lose parts of your list (memory leaks). This pointer manipulation is fundamental to understanding Graph Data Structures.

# The Put Operation Logic
def put(self, key, value):
    # 1. Check if key exists
    if key in self.cache_map:
        # Update value
        node = self.cache_map[key]
        node.value = value
        # Move to head (mark as recently used)
        self._move_to_head(node)
        return

    # 2. Create new node
    new_node = Node(key, value)
    self.cache_map[key] = new_node
    self._add_to_head(new_node)

    # 3. Check capacity
    self.size += 1
    if self.size > self.capacity:
        # 4. Evict the tail (LRU)
        tail = self._remove_tail()
        del self.cache_map[tail.key]
        self.size -= 1

Key Takeaways

Optimizing Edge Cases with Sentinel Head and Tail Nodes

In the world of low-level data structures, the most common source of bugs isn't complex logic—it's boundary conditions. When implementing a Doubly Linked List for an LRU Cache, you constantly face the "Null Pointer" nightmare: "Is this the head? Do I need to update the head pointer? Is the list empty?"

The "Null Check" Problem vs. The Sentinel Solution

Without sentinels, inserting a node at the head requires a conditional check: if head is None. With sentinels, the head is never None. It is always the dummy node. This unifies your logic, making your code cleaner and less prone to graph traversal errors.

Implementation: The "Ghost" Nodes

Notice how the initialization code below creates two nodes that hold no meaningful data (value 0). They are the anchors of your universe. Every insertion or deletion operation now happens between these two sentinels.

# Sentinel Node Class
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):
        self.capacity = capacity
        self.cache_map = {} # 1. Create Dummy Head and Tail
# They act as permanent boundaries
        self.head = Node()
        self.tail = Node() # 2. Link them together immediately
# The list is never empty, it always has at least these two
        self.head.next = self.tail
        self.tail.prev = self.head # 3. Helper method to remove a node
# Works for ANY node, even head/tail neighbors, because sentinels exist
        def _remove(self, node):
            prev_node = node.prev
            next_node = node.next
            prev_node.next = next_node
            next_node.prev = prev_node

Why This Matters for Complexity

By using sentinels, we ensure that every operation—whether adding to the front, removing from the back, or moving a node to the front—remains strictly $O(1)$. We never have to traverse the list to find the head or tail; we simply access self.head.next or self.tail.prev.

In the world of high-performance systems, "it works" is the bare minimum. "It works at scale" is the goal. When we design an LRU Cache, we aren't just storing data; we are engineering a trade-off between memory and speed.

Let's dissect the complexity. Why do we combine a Hash Map with a Doubly Linked List? Because in isolation, neither is perfect. Together, they create a machine where every operation is instantaneous.

# The Magic of O(1) Operations
def get(self, key):
    if key not in self.cache_map:
        return -1 # 1. Lookup is O(1) via Hash Map
    node = self.cache_map[key] # 2. Move to head is O(1) via DLL pointers
    self._move_to_head(node)
    return node.value

def put(self, key, value):
    if key in self.cache_map:
        node = self.cache_map[key]
        node.value = value
        self._move_to_head(node)
    else:
        # 1. Create new node
        node = Node(key, value)
        # 2. Add to Map (O(1))
        self.cache_map[key] = node
        # 3. Add to Head of DLL (O(1))
        self._add_to_head(node)
        # 4. Check Capacity
        if len(self.cache_map) > self.capacity:
            # Remove Tail (LRU) - O(1)
            removed = self._remove_tail()
            del self.cache_map[removed.key]

Complete LRU Cache Implementation Using Hash Map Doubly Linked List

Memory is a finite resource. In high-performance systems, you cannot afford to scan a list to find data. You need instant access. This is where the LRU (Least Recently Used) Cache shines. It is the gold standard for caching strategies, balancing speed and memory constraints.

To achieve $O(1)$ time complexity for both get and put operations, we must combine two powerful data structures: a Hash Map for instant lookup and a Doubly Linked List for maintaining usage order. This pattern is foundational for building concurrent applications where latency must be predictable.

The Architecture of Speed

The magic lies in the synergy. The Hash Map stores the key and points directly to the Node in the Linked List. When you access a key, you find the Node in $O(1)$ time via the Map, then move that Node to the front of the List in $O(1)$ time using pointer manipulation. If the cache is full, you simply remove the Node at the Tail (Least Recently Used) and delete its key from the Map.

class Node: def __init__(self, key, value):
    self.key = key
    self.value = value
    self.prev = None
    self.next = None

class LRUCache: def __init__(self, capacity: int):
    self.capacity = capacity
    self.cache_map = {} # Key -> Node
    # Dummy head and tail to simplify edge cases
    self.head = Node(0, 0)
    self.tail = Node(0, 0)
    self.head.next = self.tail
    self.tail.prev = self.head

def _remove_node(self, node):
    # Unlink node from its current position
    prev_node = node.prev
    next_node = node.next
    prev_node.next = next_node
    next_node.prev = prev_node

def _add_to_front(self, node):
    # Insert node right after head (Most Recent)
    node.prev = self.head
    node.next = self.head.next
    self.head.next.prev = node
    self.head.next = node

def get(self, key: int) -> int:
    if key in self.cache_map:
        node = self.cache_map[key]
        self._remove_node(node)
        self._add_to_front(node)
        return node.value
    return -1

def put(self, key: int, value: int) -> None:
    if key in self.cache_map:
        # Update existing
        node = self.cache_map[key]
        node.value = value
        self._remove_node(node)
        self._add_to_front(node)
    else:
        # Create new
        new_node = Node(key, value)
        self.cache_map[key] = new_node
        self._add_to_front(new_node)
    # Evict if over capacity
    if len(self.cache_map) > self.capacity:
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        del self.cache_map[lru_node.key]

Why This Matters in Production

This implementation is not just an academic exercise. It is the backbone of database buffer pools, web server caching layers, and even how to implement rate limiter with sliding windows. By understanding the pointer manipulation required here, you gain the ability to design systems that scale efficiently without relying solely on external services.

Notice how we use dummy head and tail nodes. This eliminates the need for special if checks when adding to an empty list or removing the only element, reducing bug surface area significantly.

System Design Context and Advanced Interview Variations

You have mastered the mechanics of the LRU Cache. Now, let's zoom out. In the real world, data structures are never isolated; they are the gears inside a massive machine. As a Senior Architect, you must understand where this pattern fits in the broader infrastructure and how interviewers will twist it to test your depth.

The Cache-Aside Pattern

In production, you rarely implement a local LRU cache for everything. Instead, you use the Cache-Aside Pattern. The application checks the cache first. If the data is missing (Cache Miss), it fetches from the database and populates the cache. This ensures consistency and performance.

However, when scaling to multiple servers, a local in-memory cache becomes insufficient. This is where distributed caching systems like Redis come into play. Understanding concurrency in this context is vital. If you are building multi-threaded services, you must refer to how to build concurrent applications to ensure your cache operations are thread-safe without killing performance with heavy locking.

# Thread-Safe LRU Access (Conceptual)
import threading
class ThreadSafeLRU:
    def __init__(self, capacity):
        self.cache = {}
        self.capacity = capacity
        self.lock = threading.RLock() # Reentrant Lock for recursion safety
    def get(self, key):
        with self.lock: # Acquire lock for thread safety
            if key not in self.cache:
                return None # Move to front logic here...
            return self.cache[key]
    def put(self, key, value):
        with self.lock:
            if key in self.cache:
                # Update value and move to front
                pass
            else:
                if len(self.cache) >= self.capacity:
                    self.evict_lru()
                self.cache[key] = value

Advanced Interview Variations

Interviewers love to pivot from "Implement LRU" to "How does this scale?". Here are the common twists:

• Thread Safety: As shown above, how do you handle concurrent reads/writes? ($O(1)$ access must remain safe).
• Distributed Consistency: If Node A updates the cache, how does Node B know to invalidate its local copy?
• Rate Limiting: The LRU structure is often adapted for how to implement rate limiter with sliding windows, where you track request timestamps instead of data values.