L18: Implement LRU Cache

Designing an LRU (Least Recently Used) Cache is a classic systems design and data structures problem frequently asked in technical interviews. The core challenge is maintaining a fixed-capacity data store where both lookup (get) and insertion (put) operations execute in $O(1)$ average time complexity, while automatically evicting the least recently used item when capacity is exceeded.

1. Problem Statement & Functional Requirements

An LRU Cache operates much like a physical shelf of books where you always place newly read or newly added books at the front, and push older books toward the back until capacity forces you to discard the one at the very end.

• LRUCache(int capacity): Initializes the LRU cache with a positive given capacity. It cannot store more values than this limit.
• int get(int key): Returns the value of the key if the key exists in the cache. If it does, this key becomes the most recently used. If it does not exist, returns -1.
• void put(int key, int value):
  • If the key already exists in the cache, update its value and mark it as recently used.
  • If the key does not exist, insert the key-value pair.
  • If the cache exceeds its capacity during insertion, evict the least recently used key-value pair before inserting the new one.
• Performance Constraint: Both get and put must run in $O(1)$ average time complexity.

2. Core Mental Model & Data Structure Selection

To achieve $O(1)$ performance for lookups, updates, additions, and deletions, a single data structure is insufficient:

• Hash Map alone: Gives $O(1)$ lookups, but items are unordered; finding and evicting the least recently used item would require scanning all entries, taking $O(N)$ time.
• Doubly Linked List alone: Maintains order and allows $O(1)$ insertions/deletions if a node reference is given, but searching for a key requires traversing the list from head to tail, taking $O(N)$ time.

The Hybrid Solution: Hash Map + Doubly Linked List

By combining a Hash Map with a Doubly Linked List (DLL), we get the best of both worlds:

1. Hash Map: Stores key -> Node Reference. This provides $O(1)$ lookups to find if a key exists and where its node lives in memory.
2. Doubly Linked List: Maintains usage order. The node closest to the head is the most recently used, and the node closest to the tail is the least recently used.

3. Dummy Head and Tail Architecture

To eliminate edge cases involving null checks during node insertions and deletions at boundaries, we initialize our doubly linked list with two dummy nodes:

• Dummy Head: Sits at the absolute front with key-value (-1, -1). Its next pointer points to the first actual data node (or dummy tail if empty).
• Dummy Tail: Sits at the absolute end with key-value (-1, -1). Its previous pointer points to the last actual data node (or dummy head if empty).

4. Step-by-Step Evolution & Dry Run Example

Let us trace an LRU cache with a capacity of 4.

1. put(2, 6): Cache is empty. Insert (2, 6) right after the dummy head. Hash map stores 2 -> Node(2, 6).
2. put(4, 7): Insert (4, 7) after head. Order from MRU to LRU: [4,7] -> [2,6].
3. put(8, 11): Insert (8, 11). Order: [8,11] -> [4,7] -> [2,6].
4. put(7, 10): Insert (7, 10). Order: [7,10] -> [8,11] -> [4,7] -> [2,6]. Capacity (4) is now fully reached.
5. get(2):
   • Found in hash map. Value 6 is returned.
   • Because it was accessed, node (2, 6) is detached from its position and reinserted right after the head (marked most recently used).
   • New Order: [2,6] -> [7,10] -> [8,11] -> [4,7].
6. get(8):
   • Found in hash map. Value 11 is returned.
   • Detach (8, 11) and move it to the front.
   • New Order: [8,11] -> [2,6] -> [7,10] -> [4,7].
7. put(5, 6):
   • Key 5 is not in map, and capacity is already at 4 (size == capacity).
   • Eviction Triggered: Identify the least recently used node, which is tail.previous (4, 7).
   • Erase 4 from the hash map, delete the node from the DLL.
   • Insert new node (5, 6) right after the head and add 5 -> Node(5, 6) to the hash map.
   • New Order: [5,6] -> [8,11] -> [2,6] -> [7,10].

5. Core Doubly Linked List Operations

To keep our code modular, clean, and bug-free, we implement two helper routines on our Doubly Linked List:

A. Deleting an Arbitrary Node

When given a node reference, we bypass it by rewiring its neighbors:

def delete_node(node):
    prev_node = node.prev
    after_node = node.next
    
    prev_node.next = after_node
    after_node.prev = prev_node

B. Inserting a Node Immediately After Head

To mark a node as most recently used, we insert it right between the dummy head and head.next:

def insert_after_head(node):
    cur_after_head = head.next
    
    head.next = node
    node.prev = head
    
    node.next = cur_after_head
    cur_after_head.prev = node

6. Complete Pseudocode Architecture

Below is the complete architectural implementation representing the logic discussed:

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key -> Node reference
        
        # Initialize dummy head and tail
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        
        self.head.next = self.tail
        self.tail.prev = self.head

    def _delete_node(self, node):
        prev_node = node.prev
        after_node = node.next
        prev_node.next = after_node
        after_node.prev = prev_node

    def _insert_after_head(self, node):
        cur_after_head = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = cur_after_head
        cur_after_head.prev = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        
        node = self.map[key]
        
        # Mark as recently used by moving to front
        self._delete_node(node)
        self._insert_after_head(node)
        
        return node.val

    def put(self, key: int, value: int) -> void:
        if key in self.map:
            node = self.map[key]
            node.val = value  # Update value
            
            # Refresh usage order
            self._delete_node(node)
            self._insert_after_head(node)
        else:
            if len(self.map) >= self.capacity:
                # Evict least recently used (node right before tail)
                lru_node = self.tail.prev
                self._delete_node(lru_node)
                del self.map[lru_node.key]
            
            # Create and insert new node
            new_node = Node(key, value)
            self.map[key] = new_node
            self._insert_after_head(new_node)

7. Complexity Analysis

Summary and Key Takeaways

• Problem Goal: Design an LRU Cache supporting get and put in $O(1)$ average time complexity.
• Data Structure Fusion: Combine a Hash Map (for $O(1)$ key lookups and address referencing) with a Doubly Linked List (for $O(1)$ ordering and re-ordering).
• Dummy Nodes: Utilize dummy head and tail pointers to eliminate edge cases during node insertion and deletion.
• Node Reusability: When updating or moving elements, reuse existing node instances rather than destroying and re-allocating new objects to maintain optimal performance.
• Eviction Strategy: The least recently used item always resides immediately preceding the dummy tail (tail.previous).
• Access Ordering: Whenever a key is accessed via get or updated via put, it must be detached from its current location and spliced immediately after the dummy head.