Problem Description

You need to design a data structure that implements an LRU (Least Recently Used) cache. An LRU cache has a fixed capacity and removes the least recently used item when it needs to make space for a new item.

The cache should support two operations:

1. get(key): Retrieve the value associated with a given key

   • If the key exists in the cache, return its value
   • If the key doesn't exist, return -1
   • When you access a key, it becomes the most recently used item

2. put(key, value): Insert or update a key-value pair

   • If the key already exists, update its value
   • If the key doesn't exist, add the new key-value pair
   • When the cache reaches its capacity limit, remove the least recently used item before adding the new one
   • Both inserting and updating make the key the most recently used item

Important constraint: Both get and put operations must run in O(1) average time complexity.

The key insight is that "recently used" means any operation (get or put) on an item makes it the most recent. Items that haven't been accessed for the longest time are considered least recently used and will be evicted first when the cache is full.

For example, if you have a cache with capacity 2:

• put(1, 1) → cache: {1=1}
• put(2, 2) → cache: {1=1, 2=2}
• get(1) returns 1 and makes key 1 most recent
• put(3, 3) → evicts key 2 (least recent), cache: {1=1, 3=3}

Intuition

To achieve O(1) time complexity for both operations, we need to think about what data structures give us constant-time access and updates.

A hash table immediately comes to mind for O(1) lookups - we can store key-value pairs and retrieve them instantly. However, a hash table alone doesn't maintain any ordering information. We need to track which items were used recently and which weren't.

For maintaining order, we could consider using an array or list where the most recently used item is at one end and the least recently used is at the other. But here's the problem: when we access an item in the middle, we'd need to move it to the front, which takes O(n) time in an array.

This is where the doubly linked list becomes crucial. With a doubly linked list:

• We can remove a node from anywhere in the list in O(1) time (if we have a reference to the node)
• We can add a node to the head or tail in O(1) time
• The order of nodes naturally represents the usage order

The key insight is combining these two data structures:

• Hash table: Maps keys to node references in the linked list, giving us O(1) access to any node
• Doubly linked list: Maintains the usage order, with the head being most recently used and tail being least recently used

When we get or put an existing key, we:

1. Find the node instantly via the hash table (O(1))
2. Remove it from its current position in the list (O(1))
3. Add it to the head of the list (O(1))

When the cache is full and we need to evict, we simply remove the tail node (O(1)).

The dummy head and tail nodes in the implementation are a clever trick to avoid null checks and edge cases when the list is empty or has only one element. They act as sentinels, making the add and remove operations uniform regardless of the list state.

Solution Approach

The implementation uses a hash table combined with a doubly linked list to achieve O(1) operations.

Data Structures:

1. Node Class: Represents each cache entry with:

   • key and val: Store the key-value pair
   • prev and next: Pointers to maintain the doubly linked list

2. LRUCache Class maintains:

   • cache: A hash table (dictionary) mapping keys to their corresponding nodes
   • head and tail: Dummy sentinel nodes to simplify list operations
   • size: Current number of items in the cache
   • capacity: Maximum allowed items

Key Helper Methods:

1. remove_node(node): Removes a node from its current position in the list

   node.prev.next = node.next
   node.next.prev = node.prev

   This bypasses the node by connecting its neighbors directly to each other.

2. add_to_head(node): Adds a node right after the dummy head

   node.next = self.head.next
   node.prev = self.head
   self.head.next = node
   node.next.prev = node

   This inserts the node between the head and the first actual node.

Main Operations:

1. get(key):

   • Check if key exists in the hash table
   • If not found, return -1
   • If found, move the node to the head (marking it as most recently used):
     • Remove it from current position
     • Add it to the head
   • Return the node's value

2. put(key, value):

   • If key exists: Update the existing node
     • Remove it from current position
     • Update its value
     • Move it to the head
   • If key doesn't exist: Create a new node
     • Create new node with the key-value pair
     • Add it to the hash table
     • Add it to the head of the list
     • Increment size
     • If capacity exceeded: Evict the LRU item
       • The LRU item is at tail.prev (the node just before the dummy tail)
       • Remove it from the hash table
       • Remove it from the linked list
       • Decrement size

The dummy head and tail nodes eliminate edge cases:

• The list is never truly empty (always has head and tail)
• No null checks needed when adding or removing nodes
• The actual cache items exist between head and tail

This design ensures all operations maintain O(1) time complexity while keeping track of usage order efficiently.

Example Walkthrough

Let's walk through a concrete example with an LRU cache of capacity 2 to see how the data structure works internally.

Initial State:

• Cache capacity: 2
• Hash table: {} (empty)
• Linked list: [head] ↔ [tail] (only dummy nodes)

Operation 1: put(1, 10)

• Create new node with key=1, value=10
• Add to hash table: {1: node1}
• Insert node after head: [head] ↔ [1,10] ↔ [tail]
• Size becomes 1

Operation 2: put(2, 20)

• Create new node with key=2, value=20
• Add to hash table: {1: node1, 2: node2}
• Insert node after head: [head] ↔ [2,20] ↔ [1,10] ↔ [tail]
• Size becomes 2
• Note: Node 2 is now most recently used (closest to head)

Operation 3: get(1) → returns 10

• Look up key 1 in hash table - found!
• Remove node1 from its current position: [head] ↔ [2,20] ↔ [tail]
• Add node1 after head: [head] ↔ [1,10] ↔ [2,20] ↔ [tail]
• Return value 10
• Note: Node 1 is now most recently used

Operation 4: put(3, 30) (capacity exceeded!)

• Size is 2, capacity is 2 → need to evict
• LRU item is at tail.prev which is node2 (key=2)
• Remove node2 from hash table: {1: node1}
• Remove node2 from list: [head] ↔ [1,10] ↔ [tail]
• Create new node with key=3, value=30
• Add to hash table: {1: node1, 3: node3}
• Insert node3 after head: [head] ↔ [3,30] ↔ [1,10] ↔ [tail]

Operation 5: get(2) → returns -1

• Look up key 2 in hash table - not found!
• Return -1 (key 2 was evicted earlier)

Final State:

• Hash table: {1: node1, 3: node3}
• Linked list: [head] ↔ [3,30] ↔ [1,10] ↔ [tail]
• Most recently used: key 3
• Least recently used: key 1

This example demonstrates how:

• The hash table provides O(1) lookups
• The linked list maintains usage order (head = most recent, tail = least recent)
• Every access (get or put) moves items to the head
• Eviction always happens at the tail when capacity is exceeded

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) for both get and put operations.

• The get operation performs the following steps:

  • Checking if key exists in the cache dictionary: O(1)
  • Removing the node from its current position: O(1) (updating 2 pointers)
  • Adding the node to the head: O(1) (updating 4 pointers)

• The put operation performs the following steps:

  • Checking if key exists in the cache dictionary: O(1)
  • If key exists: remove node O(1), update value, add to head O(1)
  • If key doesn't exist: create new node, add to dictionary O(1), add to head O(1)
  • If capacity exceeded: remove from dictionary O(1), remove tail node O(1)

All operations involve only pointer manipulations and dictionary operations, which are constant time.

Space Complexity: O(capacity)

• The cache dictionary stores at most capacity key-node pairs
• The doubly linked list contains at most capacity nodes (plus 2 sentinel nodes)
• Each node stores a constant amount of data (key, value, and two pointers)
• Total space used is proportional to the capacity of the cache

Common Pitfalls

1. Forgetting to Update the Hash Map When Evicting LRU Item

One of the most common mistakes is removing the LRU node from the linked list but forgetting to remove it from the hash map. This leads to the hash map containing stale references to nodes that no longer exist in the list.

Incorrect Implementation:

def put(self, key: int, value: int) -> None:
    if key not in self.cache:
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)
        self.size += 1
      
        if self.size > self.capacity:
            lru_node = self.tail.prev
            self._remove_node(lru_node)  # Only removes from list
            # FORGOT: self.cache.pop(lru_node.key)
            self.size -= 1

Why it's problematic:

• The hash map will still contain the evicted key
• Future get() calls might return nodes that aren't in the list
• Memory leak as the hash map grows unbounded
• Breaks the invariant that hash map size equals list size

Correct Solution: Always remove from both data structures when evicting:

if self.size > self.capacity:
    lru_node = self.tail.prev
    self.cache.pop(lru_node.key)  # Remove from hash map FIRST
    self._remove_node(lru_node)   # Then remove from list
    self.size -= 1

2. Not Moving Existing Nodes to Head on Update

Another frequent error is updating the value of an existing key without moving it to the head of the list, failing to mark it as recently used.

Incorrect Implementation:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        # Just update the value without moving the node
        self.cache[key].value = value
        return  # WRONG: Node stays in its current position

Why it's problematic:

• Violates the LRU principle - updating a value counts as "using" it
• The updated item might get evicted soon even though it was just accessed
• Leads to incorrect cache behavior

Correct Solution: Always move updated nodes to the head:

if key in self.cache:
    node = self.cache[key]
    self._remove_node(node)  # Remove from current position
    node.value = value       # Update value
    self._add_to_head(node)  # Move to head as most recently used

3. Incorrect Pointer Updates in Add/Remove Operations

Pointer manipulation in doubly linked lists is error-prone. A common mistake is updating pointers in the wrong order or missing some updates.

Incorrect _add_to_head Implementation:

def _add_to_head(self, node: Node) -> None:
    # WRONG ORDER: Breaks the chain
    self.head.next = node
    node.next = self.head.next  # This now points to itself!
    node.prev = self.head
    node.next.prev = node

Correct Solution: Update pointers in the right sequence:

def _add_to_head(self, node: Node) -> None:
    # Save the current first node
    node.next = self.head.next  # Point to current first
    node.prev = self.head       # Point back to head
    self.head.next = node        # Head points to new node
    node.next.prev = node        # Old first points back to new node

4. Not Handling the Case When Capacity is 0

Some implementations fail when initialized with capacity 0, leading to crashes or undefined behavior.

Solution: Add a guard clause in the put method:

def put(self, key: int, value: int) -> None:
    if self.capacity == 0:
        return  # Cannot store anything
    # ... rest of the implementation

5. Memory Leak from Circular References

Without properly clearing node references when removing them, Python's garbage collector might not free memory due to circular references between nodes.

Better Practice:

def _remove_node(self, node: Node) -> None:
    node.prev.next = node.next
    node.next.prev = node.prev
    # Clear references to help garbage collection
    node.prev = None
    node.next = None

These pitfalls highlight the importance of maintaining consistency between the hash map and linked list, properly managing node positions based on usage, and careful pointer manipulation.