How to Implement an LRU Cache for Coding Interviews: A Step-by-Step Guide

In the world of high-performance computing, time is memory. When your application needs data, it doesn't always want to wait for a disk read or a network round-trip. This is where the Cache comes in. But caches have a hard limit on size. When the cache is full, which item do you throw away to make room for the new one?

The industry standard answer is Least Recently Used (LRU). It operates on a simple, intuitive heuristic: "If you haven't used it in a while, you probably won't need it soon."

The Algorithmic Logic

To implement LRU efficiently, we cannot simply scan a list every time (that would be $O(n)$). We need a data structure that allows us to find an item and move it to the front in constant time, $O(1)$.

The standard architectural pattern combines two structures:

• Hash Map (Dictionary): For instant lookup of keys.
• Doubly Linked List: To maintain the order of usage (Head = MRU, Tail = LRU).

Implementation in Python

While Python's collections.OrderedDict can simulate this, understanding the underlying mechanics is crucial for system design interviews. Here is a conceptual breakdown of the logic.

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):
        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):
        """Inserts node right after head (MRU 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):
        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, value):
        if key in self.cache:
            self._remove_node(self.cache[key])
        
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)
        
        if len(self.cache) > self.capacity:
            # Evict the Least Recently Used (Tail)
            lru_node = self.tail.prev
            self._remove_node(lru_node)
            del self.cache[lru_node.key]
            

Real-World Use Cases

LRU isn't just an interview question; it powers the infrastructure of the internet.

Key Takeaways

• Definition: LRU evicts the item that has not been used for the longest period of time.
• Complexity: A naive list implementation is $O(n)$, but a Hash Map + Doubly Linked List achieves $O(1)$ for both get and put operations.
• Trade-off: LRU is excellent for "temporal locality" (things used recently will be used again) but can be memory-intensive due to the overhead of pointers in the linked list.
• Next Step: Ready to code it? Check out our guide on how to implement lru cache in python for a deep dive into the syntax.

Imagine you are in a high-stakes coding interview. The interviewer asks you to build a system that tracks the most recently used items in a cache. You instinctively reach for a Python List or a Java ArrayList.

Stop. This is the "Naive Trap." While intuitive, a linear list forces your system to scan every single item to check for existence. In a production environment with millions of users, this $O(n)$ complexity is a performance bottleneck that will crash your server.

The Math Behind the Failure

To understand why we fail, we must look at the memory layout.

# ❌ NAIVE APPROACH: O(n)
# Searching a list requires scanning every element
def check_user_naive(user_id, user_list):
    for user in user_list:
        if user['id'] == user_id:
            return True
    return False

# ✅ OPTIMIZED APPROACH: O(1)
# Searching a dictionary (Hash Map) is instant
def check_user_optimized(user_id, user_dict):
    # The hash function calculates the memory address directly
    if user_id in user_dict:
        return True
    return False

In the world of caching, the Get operation is deceptive. A novice implementation simply looks up a value and returns it. But in an LRU (Least Recently Used) cache, a "Get" is actually a two-part transaction: Read and Reorder.

If you retrieve a key but fail to update its position, you break the fundamental contract of the cache. The node you just accessed is now the "most recently used," and it must be promoted to the front of the line immediately.

Notice the critical step: Update LRU. This is where the magic happens. We leverage the doubly linked list structure to perform this reordering in constant time.

Because we have a direct reference to the node via the Hash Map, we don't need to traverse the list to find it. We simply manipulate the pointers of its neighbors. This ensures the entire operation remains $O(1)$.

The Pointer Manipulation Logic

The animation above visualizes the _move_to_head method. To move Node B from the middle to the front without breaking the chain, we perform a specific sequence of pointer updates:

• Step 1: Detach. Connect Node A's next pointer directly to Node B's next (which is Tail).
• Step 2: Reattach. Connect Node B's prev pointer to the Head, and Head's next to Node B.
• Step 3: Link Back. Ensure Node B's next points to Node A.

This intricate dance is why understanding pointer manipulation is vital for systems programming.

Handling Put Operations and Capacity Constraints

If the get operation is the heartbeat of the LRU cache, the put operation is its metabolism. It is significantly more complex because it must handle two distinct scenarios: updating existing data and managing the strict memory limits of the system.

The Logic of Insertion and Eviction

When you call put(key, value), the system must perform a rigorous decision tree. It first checks if the key already exists. If it does, we update the value and promote the node to the head (most recently used). If the key is new, we add it to the head. However, if the cache is full, we must perform the critical Eviction step: removing the least recently used item from the tail before we can make space.

This entire process maintains the strict $O(1)$ time complexity requirement. If we were to scan the list to find the tail, we would degrade to $O(n)$, destroying the performance benefits we worked so hard to achieve.

Implementation Strategy

The implementation relies on the helper methods we established earlier: _add_to_front, _remove_node, and _remove_tail. Notice how the main put method delegates the pointer manipulation to these helpers. This keeps the logic clean and reduces the risk of "pointer spaghetti" where you lose track of references.

For a deeper dive into the full implementation details, you can review our companion guide on how to implement lru cache in python.

def put(self, key, value):
    # Case 1: Key already exists
    if key in self.map:
        node = self.map[key]
        node.value = value
        # Move to front to mark as recently used
        self._move_to_front(node)
        return

    # Case 2: New Key
    new_node = Node(key, value)
    self.map[key] = new_node
    self._add_to_front(new_node)

    # Case 3: Capacity Exceeded (Eviction)
    if len(self.map) > self.capacity:
        # Remove the least recently used node (Tail)
        tail_node = self._remove_tail()
        # Clean up the hash map reference
        del self.map[tail_node.key]
        

You have mastered the data structure. Now, let's talk about architecture. In the real world, an LRU Cache isn't just a coding interview puzzle; it is the primary defense against database overload.

When you design a system, you are constantly fighting the Latency Gap. Your application server might process a request in milliseconds, but a disk read from a database can take 100x longer. The LRU Cache sits in the middle, acting as a high-speed buffer that absorbs the majority of read traffic.

The Two Paths: Hit vs. Miss

Understanding the flow is critical. When a request comes in, the system takes one of two paths. The efficiency of your system depends entirely on the Hit Rate.

Real-World Application: Database Optimization

One of the most common uses of LRU is in Database Buffer Pools. When a database engine (like MySQL or PostgreSQL) executes a query, it stores the result pages in memory.

If you run the same query twice, the second run is instant because the data is already in the LRU buffer. However, if you run a massive, complex query that fills up the buffer, it will evict the older, less frequently used data. This is why understanding how to read and optimize sql query execution plans is vital—you don't want your "hot" data being evicted by a one-time report.