LRU Cache

1. The Problem

Design a cache with a fixed capacity. When the cache is full and a new key arrives, evict the Least Recently Used item. Both get(key) and put(key, value) must run in O(1).

# LRUCache(capacity=2)
# put(1, 1)   → cache: {1:1}
# put(2, 2)   → cache: {1:1, 2:2}
# get(1)      → 1    (now 1 is most recently used)
# put(3, 3)   → evict key 2 (LRU), cache: {1:1, 3:3}
# get(2)      → -1   (not found)
# put(4, 4)   → evict key 1, cache: {4:4, 3:3}
# get(1)      → -1
# get(3)      → 3
# get(4)      → 4

2. The Key Insight

We need two things simultaneously:

• O(1) lookup — a hash map from key → node
• O(1) order tracking — a doubly linked list where head = LRU, tail = MRU

When we access or insert a key, we move its node to the tail. When we evict, we remove from the head. With pointers to both neighbors, every move and removal is O(1).

3. Solution 1 — OrderedDict (Pythonic)

Python's OrderedDict maintains insertion order and supports moving a key to the end in O(1). This is the clean interview answer if you're allowed to use stdlib.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # Mark as most recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # Remove LRU (first item)

4. Solution 2 — Doubly Linked List + HashMap

If the interviewer says "implement without OrderedDict", you need this. Two sentinel nodes (dummy head and tail) eliminate edge-case checks.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}  # key → Node
        self.head = Node()  # dummy LRU sentinel
        self.tail = Node()  # dummy MRU sentinel
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):  # Insert before dummy tail = MRU
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_to_tail(node)
        if len(self.map) > self.cap:
            lru = self.head.next  # First real node = LRU
            self._remove(lru)
            del self.map[lru.key]

5. Trace

# capacity=2
# Doubly linked list: head ↔ [nodes] ↔ tail
# Left of tail = MRU. Right of head = LRU.
#
# put(1,1): map={1:N1}, list: head ↔ N1 ↔ tail
# put(2,2): map={1:N1,2:N2}, list: head ↔ N1 ↔ N2 ↔ tail
# get(1):   move N1 to tail → head ↔ N2 ↔ N1 ↔ tail
# put(3,3): over capacity, evict head.next=N2 (key=2)
#           map={1:N1,3:N3}, list: head ↔ N1 ↔ N3 ↔ tail
# get(2):   key 2 not in map → return -1  ✓