Implementing an LRU Cache

1. The Caching Principle: Why Be Efficient?

A cache is a smaller, faster memory layer that stores copies of frequently accessed data from a larger, slower storage layer. The goal is to serve requests from the fast cache whenever possible, avoiding the expensive trip to the slow backend (like a database or a remote service).

The Least Recently Used (LRU) policy is a common strategy for deciding what to keep in the cache. When the cache is full and a new item needs to be stored, the LRU algorithm evicts the item that has not been accessed for the longest time.

The core requirements for our LRU Cache are:

• A fixed capacity.
• A get(key) operation that retrieves an item's value. If the key exists, this access marks the item as "recently used."
• A put(key, value) operation that inserts or updates an item. This also marks the item as "recently used."
• Crucially, both get and put must operate in average O(1) time complexity.

The Metaphor: A Small, High-Speed Bookshelf

Imagine your main library is a massive, slow-to-navigate university library (the database). An LRU Cache is like having a small bookshelf right next to your desk for the books you're currently using.

• Capacity: Your bookshelf can only hold 10 books.
• get(book): You need a book. You first check your bookshelf. If it's there (cache hit), you grab it instantly. This proves it's useful, so you place it at the most prominent spot on your shelf (making it the most recently used). If it's not there (cache miss), you make the slow trip to the main library, bring the book back, and place it on your shelf.
• put(new_book): You get a new book from the library. You want to add it to your shelf. If the shelf is full, you look for the book that you haven't touched in the longest time (the one gathering dust at the far end) and put it back in your backpack to return to the main library later. Then you place the new book in the most prominent spot.

This constant shuffling ensures your small, fast bookshelf always holds the most relevant books, saving you countless trips to the slow main library.

2. The Architectural Challenge: Achieving O(1)

The O(1) constraint for both get and put makes the choice of data structure non-trivial. Let's analyze why simple approaches fail:

• A Python Dictionary (Hash Map) alone:

  • get(key): Excellent, this is O(1).
  • put(key, value): O(1) for insertion/update.
  • Problem: How do we find the "least recently used" item to evict? We don't have ordering information. We'd have to store timestamps and scan all n items, making eviction O(n).

• A Python List (Array) alone:

  • Eviction: Easy. If we keep the LRU item at index 0, eviction is O(1).
  • Problem: How do we handle a get or put for an item in the middle of the list? We'd have to find it (O(n) scan) and then move it to the end to mark it as most recent (O(n) operation).

To get O(1) for all operations, we need to combine the strengths of both data structures.

3. The Optimal Design: Hash Map + Doubly Linked List

The canonical solution, and the one expected in an interview, is to use a hash map and a doubly linked list in tandem.

• The Doubly Linked List maintains the recency order. We'll keep the Most Recently Used (MRU) item at the head and the Least Recently Used (LRU) item at the tail.
• The Hash Map provides the O(1) lookup. It maps the key to a direct pointer to the corresponding Node in the doubly linked list.

This combination is powerful:

1. To access an item, you use the hash map to jump directly to the correct node in O(1).
2. Once you have the node, you can move it to the head of the list in O(1) because a doubly linked list allows for node removal and insertion by just updating the prev and next pointers of its neighbors.

To see this dynamic in action, let's watch a detailed video walkthrough.

4. Implementation: Building the LRU Cache in Python

Now, let's translate this design into code. We will build this from the ground up, starting with the node structure.

To follow the logic flow for get and put, this flowchart is a helpful guide.

Step 1: The Node Class

Each element in our linked list will be an object containing the key, value, and pointers to the previous and next nodes. It's vital to store the key within the node itself; you'll see why during eviction.

class Node:
    """A node in a doubly linked list."""
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

Step 2: The LRUCache Class and Helper Methods

We'll initialize the cache with its capacity, the hash map (self.cache), and two sentinel nodes: self.head and self.tail. These dummy nodes simplify our logic by removing edge cases for an empty list or when operating near the ends of the list. The actual cached items will always live between head and tail.

We also create two private helper methods: _remove and _add.

• _remove(node): Detaches a node from the list by linking its prev and next neighbors to each other.
• _add(node): Adds a node to the front of the list (right after self.head), making it the new MRU item.

Step 3: The Full Implementation

Here is the complete Python code. Study it carefully, noting how the get and put methods use the helper functions to manipulate the data structures.

class LRUCache:
    def __init__(self, capacity: int):
        """
        Initializes the LRU Cache.
        
        Args:
            capacity (int): The maximum number of items the cache can hold.
        """
        self.capacity = capacity
        self.cache = {}  # Hash map: key -> Node

        # Dummy head and tail nodes to handle edge cases gracefully.
        # MRU items will be near the head, LRU items near the tail.
        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):
        """Removes a node from the doubly linked list."""
        prev_node, next_node = node.prev, node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add(self, node: Node):
        """Adds a node to the front of the list (right after the head)."""
        # Wire up the new node's pointers
        node.prev = self.head
        node.next = self.head.next
        
        # Insert the node into the list
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        """
        Retrieves an item from the cache and marks it as most recently used.
        Returns -1 if the key is not found.
        """
        if key in self.cache:
            node = self.cache[key]
            # Move the accessed node to the front (MRU)
            self._remove(node)
            self._add(node)
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        """
        Inserts or updates an item in the cache.
        If capacity is exceeded, evicts the least recently used item.
        """
        # If the key already exists, update its value and move it to the front.
        if key in self.cache:
            self._remove(self.cache[key])
        
        # Create a new node and add it to the cache and the list.
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add(new_node)
        
        # If capacity is exceeded, perform eviction.
        if len(self.cache) > self.capacity:
            # The LRU node is the one just before the tail sentinel.
            lru_node = self.tail.prev
            self._remove(lru_node)
            
            # CRITICAL: Remove the key from the hash map as well!
            del self.cache[lru_node.key]

To reinforce your understanding of the implementation details, reading through a well-documented text explanation can be very helpful.

5. Interview Focus: Analysis and Trade-offs

Simply writing the code is not enough in an elite interview. You must be able to analyze its performance and discuss potential issues.

Complexity Analysis

• Time Complexity: O(1) for both get and put.
  • get: Involves one hash map lookup (O(1)), one node removal (O(1)), and one node addition (O(1)). Total is O(1).
  • put: Involves a hash map lookup (O(1)), potentially a node removal (O(1)), a node creation (O(1)), a node addition (O(1)), and potentially an eviction which is also O(1). Total is O(1).
• Space Complexity: O(capacity).
  • The hash map stores up to capacity key-node mappings.
  • The doubly linked list stores up to capacity nodes.
  • The total memory usage scales linearly with the specified capacity.

Common Pitfalls

Interviewers often watch for these specific mistakes:

1. Forgetting to update the hash map on eviction: If you only remove the node from the list, the hash map will contain a "dangling pointer" to a node that shouldn't exist, leading to bugs and memory leaks.
2. Not moving a node on access/update: A get or a put on an existing key must update its recency by moving it to the front of the list. Forgetting this violates the LRU principle.
3. Incorrect pointer manipulation: Mixing up prev and next assignments is easy to do. Drawing the pointers on a whiteboard during an interview is a great way to avoid this.

Conclusion

Today you have designed, implemented, and analyzed a core system design component. Building an LRU cache is a microcosm of the engineering challenges faced at scale: you must choose the right tools (data structures) to meet strict performance requirements and reason about their trade-offs.

Key Takeaways:

• An LRU Cache evicts the least recently used item to make space, requiring O(1) get and put operations.
• The optimal architecture combines a hash map for O(1) lookups with a doubly linked list for O(1) reordering.
• Using sentinel (dummy) nodes for the head and tail of the linked list greatly simplifies the pointer logic by eliminating edge cases.
• During eviction, you must remove the target item from both the linked list and the hash map to maintain consistency.

Next Lesson Preview

We've now designed a highly efficient cache that lives on a single server. But what happens when our system is so large that it spans multiple servers, cities, or even continents? How do we keep data consistent? If the network between two data centers fails, should our service go down, or should it continue operating, even at the risk of showing stale data?

In our next lesson, we will confront these fundamental dilemmas of distributed systems by exploring the famous CAP Theorem, which defines the unavoidable trade-offs between Consistency, Availability, and Partition Tolerance.