LeetCode LRU Cache: Hash Map + Doubly Linked List

LeetCode 146 LRU Cache is rated Medium and is a classic systems-flavored interview question. It tests whether you can combine two data structures to achieve constant-time operations and whether you can implement a doubly linked list without bugs. The same pattern shows up in LFU Cache, design problems for browser history, and database buffer pools.

The Problem

Design a data structure that supports two operations in O(1) average time:

• get(key): return the value if the key exists, otherwise return -1. A successful get marks the key as most recently used.
• put(key, value): insert or overwrite the value. If the cache exceeds its capacity, evict the least recently used key before inserting.

Example:

LRUCache cache = LRUCache(2)
cache.put(1, 1)         # cache: {1=1}
cache.put(2, 2)         # cache: {1=1, 2=2}
cache.get(1)            # returns 1, cache: {2=2, 1=1}
cache.put(3, 3)         # evicts key 2, cache: {1=1, 3=3}
cache.get(2)            # returns -1

Brute Force

The simplest approach uses a Python dict and tracks recency with a list of keys.

class LRUCacheBrute:
    def __init__(self, capacity):
        self.capacity = capacity
        self.store = {}
        self.order = []  # least recent at index 0

    def get(self, key):
        if key not in self.store:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.store[key]

    def put(self, key, value):
        if key in self.store:
            self.order.remove(key)
        elif len(self.store) >= self.capacity:
            oldest = self.order.pop(0)
            del self.store[oldest]
        self.store[key] = value
        self.order.append(key)

list.remove is O(n), so both get and put become O(n). The interviewer wants O(1).

Optimal Solution

Combine a hash map keyed by cache key, mapping to nodes in a doubly linked list ordered by recency. The head sentinel points to the most recently used node; the tail sentinel points to the least recently used. Every operation becomes constant time.

class Node:
    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):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        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_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_front(node)
        return node.value

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

Sentinel head and tail nodes eliminate the special cases of inserting into or removing from an empty list.

Walk Through an Example

Capacity 2. Start with an empty list: head <-> tail.

put(1, 1): insert node 1 at front. List: head <-> 1 <-> tail. Map: {1: node1}.

put(2, 2): insert node 2 at front. List: head <-> 2 <-> 1 <-> tail.

get(1) returns 1. We move node 1 to the front. List: head <-> 1 <-> 2 <-> tail.

put(3, 3): insert node 3 at front. List: head <-> 3 <-> 1 <-> 2 <-> tail. Size exceeds capacity, so evict tail.prev, which is node 2. List: head <-> 3 <-> 1 <-> tail. Map: {1: node1, 3: node3}.

get(2) returns -1 because key 2 is no longer in the map.

Edge Cases

• Capacity of 1: every put evicts the previous key. The sentinel design handles this cleanly.
• Repeated puts on the same key: detect with key in self.cache, remove the old node, then insert the new one at the front.
• Get on a missing key: do not mutate the list, just return -1.
• Capacity 0: the problem usually disallows this, but if asked, every put should immediately evict; you can short-circuit by storing nothing.

Complexity Analysis

• get: O(1) average due to hash map lookup plus constant-time list splicing.
• put: O(1) average. Insertion, optional removal, and eviction are each constant time.
• Space: O(capacity) for both the map and the list.

How to Explain It in an Interview

State the goal first: O(1) on both operations. Hash maps give O(1) lookup, but they do not track order. A doubly linked list gives O(1) insertion and removal at arbitrary positions if you have a pointer to the node, and it lets you maintain recency order. Combine them by storing the node itself in the map.

Walk through the invariant: the node nearest the head sentinel is the most recently used, the node nearest the tail sentinel is the least recently used. Every successful get moves a node to the front. Every put either updates an existing node and moves it to the front or inserts a new node and evicts from the back if the cache is full.

If asked why not use Python’s OrderedDict, explain it works and is acceptable, but the manual implementation demonstrates you understand the underlying data structures and would be necessary in languages without an ordered hash map.

Related Problems

• LeetCode 460 LFU Cache, which adds frequency tracking.
• LeetCode 432 All O`one Data Structure for ordered key buckets.
• LeetCode 1472 Design Browser History, which uses linked-list-like state.
• LeetCode 706 Design HashMap for related design skills, see also Hashing and Hash Maps.

Wrap up

LRU Cache is a rite of passage in design interviews. Practice writing the doubly linked list helpers first until the splicing is automatic, then layer the hash map on top. After that, attempt LFU Cache, which forces you to nest the same pattern by frequency. Revisit Linked Lists Common Operations if pointer juggling is still uncomfortable.