LRU Cache

1. Step 1: Initialize LRUCache

   Replace the empty starter with the first real state owned by LRUCache. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.

2. Step 2: Assemble the primary transition

   Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.

3. Step 3: Pass the Wizard Stateful Lru Eviction Order case

   Complete the readable core algorithm for one representative Interview case. The node after the least-recent sentinel is the only eviction candidate, so removal remains constant time.

4. Step 4: Harden the Wizard Stateful Lru Update Recency boundary

   Repair the reviewed boundary and pass the complete submission contract. An update is also an access; refreshing its recency prevents the wrong key from surviving the next eviction.

• Updating an existing key must refresh recency without increasing cache size.
• The hash map and recency list must describe exactly the same live cache entries after every operation.
• linked lists
• hashing and sets

• LeetCode 146 — LRU Cache

• Relink Nodes Safely(opens in a new tab)

  Relink Nodes Safely isolates every untouched node keeps its original next link, and at most one predecessor changes to the removed node’s former successor. That focused state discipline is required when implementing lru cache as a complete Interview Problem.

Use sentinel least/most nodes and a key-to-node map. Remove and append nodes in O(1); get moves to most-recent, put replaces existing nodes and evicts least.next when oversized.

Why it works: The list order always matches increasing recency and the map contains exactly its data nodes. Moving every accessed or written key to the most-recent end preserves that invariant, so least.next is exactly the eviction target.

class Node:
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None
class LRUCache:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}
        self.least, self.most = Node(), Node()
        self.least.next = self.most
        self.most.prev = self.least
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    def _append(self, node):
        previous = self.most.prev
        previous.next = node
        node.prev = previous
        node.next = self.most
        self.most.prev = node
    def get(self, key):
        if key not in self.nodes:
            return -1
        node = self.nodes[key]
        self._remove(node)
        self._append(node)
        return node.value
    def put(self, key, value):
        if key in self.nodes:
            self._remove(self.nodes[key])
        node = Node(key, value)
        self.nodes[key] = node
        self._append(node)
        if len(self.nodes) > self.capacity:
            evicted = self.least.next
            self._remove(evicted)
            del self.nodes[evicted.key]