Gemini vs DeepSeek for Coding

To build a Least Recently Used (LRU) cache from scratch with optimal performance, we need to combine two data structures:

1. A Hash Map (Dictionary): To allow $O(1)$ fast lookups of keys.
2. A Doubly Linked List (DLL): To maintain the usage order and allow $O(1)$ insertions and deletions of nodes.

By mapping the cache keys to the specific nodes in the doubly linked list, we can instantly locate a node and move it to the "most recently used" position without iterating through the list.

Python Implementation

class Node:
    """A node for the Doubly Linked List."""
    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 = {}  # Hash map: key -> Node
        
        # Initialize dummy head and tail nodes to avoid edge cases
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove_node(self, node: Node):
        """Helper to remove an existing node from the linked list."""
        prv = node.prev
        nxt = node.next
        prv.next = nxt
        nxt.prev = prv

    def _add_node_to_head(self, node: Node):
        """Helper to insert a node right after the dummy head (Most Recently Used)."""
        nxt = self.head.next
        
        # Connect node to head and the old first node
        node.next = nxt
        node.prev = self.head
        
        # Connect head and the old first node to the new node
        self.head.next = node
        nxt.prev = node

    def get(self, key: int) -> int:
        """Return the value of the key if it exists, otherwise return -1."""
        if key in self.cache:
            node = self.cache[key]
            # Since it was just accessed, move it to the most recently used position
            self._remove_node(node)
            self._add_node_to_head(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        """Update the value of the key if it exists, or insert the new key-value pair."""
        if key in self.cache:
            # If key exists, update value and move to head
            node = self.cache[key]
            node.value = value
            self._remove_node(node)
            self._add_node_to_head(node)
        else:
            # If key doesn't exist, create a new node
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_node_to_head(new_node)
            
            # Check if we exceeded capacity
            if len(self.cache) > self.capacity:
                # The LRU node is the one right before the dummy tail
                lru_node = self.tail.prev
                self._remove_node(lru_node)
                del self.cache[lru_node.key] # Delete from cache map

Time Complexity Explanation

Both primary operations (get and put) operate in $O(1)$ (Constant Time). Here is the step-by-step breakdown of why:

1. get(key) Operation: $O(1)$

• Checking the Hash Map: Finding if the key exists inside the Python dictionary takes $O(1)$ average time.
• Updating the List: If the key exists, we find the exact Node object via the hash map. Passing this node directly to _remove_node() updates 2 pointers, taking $O(1)$ time.
• Moving to Head: Passing the node to _add_node_to_head() updates 4 pointers, taking $O(1)$ time.
• Total: $O(1) + O(1) + O(1) = O(1)$

2. put(key, value) Operation: $O(1)$

• Updating an existing key: Just like get, finding the node via the hash map, updating its value, removing it, and adding it to the head only requires constant-time dictionary lookups and pointer reassignments. ($O(1)$)
• Adding a new key:
  • Inserting a new entry into the hash map takes $O(1)$.
  • Appending the new node right after the head takes $O(1)$.
• Evicting the LRU element (if capacity is exceeded):
  • Finding the Least Recently Used item takes $O(1)$ because it is guaranteed to be exactly self.tail.prev.
  • Removing it from the Doubly Linked List takes $O(1)$ pointer reassignments.
  • Deleting the key from the hash map takes $O(1)$ time (this is why we store the key inside the Node object—so we know exactly which dictionary key to delete when we evict the tail node).
• Total: $O(1)$

Space Complexity: $O(C)$

Where $C$ is the capacity of the cache. At any given time, the dictionary contains at most $C$ key-value pairs, and the doubly linked list contains at most $C$ nodes (plus the 2 dummy nodes).

I'll provide a Python implementation of an LRU cache and explain its time complexity.

class Node:
    """Doubly linked list node for LRU cache"""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """
    LRU Cache implementation using doubly linked list and hash map.
    
    Attributes:
        capacity: Maximum number of items the cache can hold
        cache: Dictionary mapping keys to nodes
        head: Most recently used node (dummy head)
        tail: Least recently used node (dummy tail)
    """
    
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("Capacity must be positive")
        
        self.capacity = capacity
        self.cache = {}  # key -> Node mapping
        
        # Initialize dummy head and tail nodes
        self.head = Node(0, 0)  # Most recently used side
        self.tail = Node(0, 0)  # Least recently used side
        
        # Connect head and tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _add_node(self, node: Node):
        """Add node right after head (most recent position)"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node: Node):
        """Remove node from the linked list"""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
    
    def _move_to_head(self, node: Node):
        """Move node to head (most recent position)"""
        self._remove_node(node)
        self._add_node(node)
    
    def _pop_tail(self) -> Node:
        """Remove and return the tail node (least recently used)"""
        lru_node = self.tail.prev
        self._remove_node(lru_node)
        return lru_node
    
    def get(self, key: int) -> int:
        """
        Get value for key if exists, otherwise return -1
        Time Complexity: O(1)
        """
        if key not in self.cache:
            return -1
        
        node = self.cache[key]
        # Move accessed node to head (most recent)
        self._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        """
        Insert or update key-value pair
        Time Complexity: O(1)
        """
        if key in self.cache:
            # Key exists, update value and move to head
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # New key, create new node
            new_node = Node(key, value)
            
            if len(self.cache) >= self.capacity:
                # Cache is full, remove LRU item
                lru_node = self._pop_tail()
                del self.cache[lru_node.key]
            
            # Add new node to cache and linked list
            self.cache[key] = new_node
            self._add_node(new_node)
    
    def size(self) -> int:
        """Return current number of items in cache"""
        return len(self.cache)
    
    def print_cache(self):
        """Print current cache state for debugging"""
        print("Cache Contents (MRU -> LRU):")
        current = self.head.next
        while current != self.tail:
            print(f"  {current.key}: {current.value}")
            current = current.next
        print(f"Total items: {self.size()}/{self.capacity}")


# Example usage and testing
def test_lru_cache():
    print("Testing LRU Cache Implementation\n")
    
    # Create cache with capacity 3
    cache = LRUCache(3)
    
    print("1. Initial state:")
    cache.print_cache()
    print()
    
    print("2. Adding items (1: 'A', 2: 'B', 3: 'C'):")
    cache.put(1, 'A')
    cache.put(2, 'B')
    cache.put(3, 'C')
    cache.print_cache()
    print()
    
    print("3. Getting key 2 (should move it to MRU position):")
    print(f"   Value for key 2: {cache.get(2)}")
    cache.print_cache()
    print()
    
    print("4. Adding new item 4: 'D' (should evict LRU item 1):")
    cache.put(4, 'D')
    cache.print_cache()
    print()
    
    print("5. Getting non-existent key 1:")
    print(f"   Value for key 1: {cache.get(1)}")
    cache.print_cache()
    print()
    
    print("6. Updating existing key 3 to 'C-Updated':")
    cache.put(3, 'C-Updated')
    cache.print_cache()
    print()
    
    print("7. Getting all current keys:")
    print(f"   Key 2: {cache.get(2)}")
    print(f"   Key 3: {cache.get(3)}")
    print(f"   Key 4: {cache.get(4)}")
    print()
    
    print("8. Adding another item 5: 'E' (should evict LRU item 4):")
    cache.put(5, 'E')
    cache.print_cache()


if __name__ == "__main__":
    test_lru_cache()

Time Complexity Analysis

Data Structure Components:

1. Doubly Linked List: Maintains order of items (MRU to LRU)
2. Hash Map (Dictionary): Provides O(1) key lookup

Operation Time Complexities:

1. get(key)

• Time Complexity: O(1)
• Operations:
  1. Dictionary lookup: O(1)
  2. Remove node from current position: O(1) (using doubly linked list)
  3. Add node to head: O(1)
• Total: O(1)

2. put(key, value)

• Time Complexity: O(1)

• Case A: Key exists (update)

  1. Dictionary lookup: O(1)
  2. Update value: O(1)
  3. Move to head: O(1)

• Case B: New key, cache not full

  1. Create new node: O(1)
  2. Add to dictionary: O(1)
  3. Add to head of list: O(1)

• Case C: New key, cache full (eviction needed)

  1. Remove tail node: O(1)
  2. Remove from dictionary: O(1)
  3. Add new node to dictionary: O(1)
  4. Add new node to head: O(1)

3. Auxiliary Methods

• _add_node(): O(1) - adds node after head
• _remove_node(): O(1) - removes given node using prev/next pointers
• _move_to_head(): O(1) - combination of remove and add
• _pop_tail(): O(1) - removes node before tail

Space Complexity: O(n)

• Where n = capacity of cache
• Storage for:
  • Dictionary: O(n)
  • Linked list nodes: O(n)
  • Dummy head/tail nodes: O(1)

Key Design Insights:

1. Why doubly linked list?

   • O(1) removal of any node (given the node reference)
   • O(1) addition to head
   • Easy to maintain order

2. Why hash map?

   • O(1) lookup to find any node
   • Combined with linked list for O(1) operations

3. LRU Eviction Strategy:

   • Always remove tail (oldest) when cache is full
   • Always move accessed nodes to head (most recent)

This implementation provides optimal O(1) time complexity for both get and put operations, which is the best possible for an LRU cache implementation.