146 - LRU Cache

Difficulty: Medium | Pattern: Hash Map + Doubly Linked List | Company tags: Amazon, Google, Microsoft, Facebook, Apple

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) — Initialize the LRU cache with positive size capacity.
• int get(int key) — Return the value of the key if it exists, otherwise return -1. Mark the key as recently used.
• void put(int key, int value) — Update or insert the value if the key is present. When the cache reaches its capacity, evict the least recently used key before inserting a new one.

Both get and put must run in O(1) average time complexity.

Example:

LRUCache cache = new LRUCache(2)  // capacity = 2
cache.put(1, 1)   // cache: {1=1}
cache.put(2, 2)   // cache: {1=1, 2=2}
cache.get(1)      // return 1; 1 is now most recent
cache.put(3, 3)   // evicts key 2; cache: {1=1, 3=3}
cache.get(2)      // return -1 (not found)

Key Insight: Hash Map + Doubly Linked List

To achieve O(1) get and put:

• Hash map: maps key to node (O(1) lookup)
• Doubly linked list: maintains usage order. Head = most recently used, Tail = least recently used
• On get: move accessed node to head in O(1)
• On put: insert at head; if over capacity, remove tail node

The doubly (not singly) linked list is needed because removing a node requires updating the predecessor's next pointer — O(1) only if we can reach the predecessor directly.

Algorithm Flow

Solution (Python)

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        # Sentinel head and tail (dummy nodes, never removed)
        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 _insert_at_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_at_head(node)
        return node.val

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

Python Shortcut: OrderedDict

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

In interviews, the doubly-linked-list solution is preferred — it demonstrates design understanding.

Key Design Points

1. Dummy head/tail sentinels eliminate edge cases for empty list operations
2. _remove and _insert_at_head are the only primitives needed
3. For put of existing key: remove old node first, then insert updated node at head
4. The hash map stores key → node (not key → value) so removal is O(1)

Complexity

• Time: O(1) for both get and put
• Space: O(capacity)

Key Terms

Term	Definition
LRU (Least Recently Used)	Eviction policy that discards the item that has gone longest without being accessed.
Doubly linked list	List where each node has prev and next pointers, allowing O(1) removal from any position.
Sentinel node	Dummy head/tail node that removes null-checks for boundary insert/remove operations.
Amortized O(1)	Average per-operation cost, achieved here via direct hash map lookups instead of scans.
Cache eviction	The act of removing an entry to make room, triggered when capacity is exceeded.

FAQ

Q: Why not use a singly linked list? A: Removing a node in O(1) requires updating the previous node's next pointer. A singly linked list can't reach the predecessor without a scan, breaking the O(1) guarantee.

Q: Why use sentinel head/tail nodes instead of tracking head/tail as None? A: Sentinels guarantee every real node always has a valid prev and next, so insert/remove logic doesn't need special-case branches for the first or last real node.

Q: Can OrderedDict fully replace the manual implementation in an interview? A: It works and is O(1), but most interviewers want the doubly-linked-list + hash map version to confirm you understand the underlying mechanics, not just library usage.

Q: How would you make this thread-safe? A: Wrap get and put in a lock (e.g., threading.Lock) since both mutate shared state (the map and the list); fine-grained locking is possible but significantly more complex.

Q: What changes for an LFU (Least Frequently Used) cache instead of LRU? A: LFU needs to track access frequency per key, typically with a hash map of frequency to a linked list of keys at that frequency, plus a pointer to the minimum frequency bucket — more bookkeeping than LRU's single ordering.

Quick Revision

• Goal: O(1) get and put with LRU eviction at capacity.
• Data structures: hash map (key -> node) + doubly linked list (usage order).
• Head of list = most recently used; tail = least recently used.
• get: look up in map, if found move node to head, return value; else return -1.
• put: if key exists, remove old node; create/insert new node at head; evict tail's neighbor if over capacity.
• Sentinel head/tail nodes avoid null checks.
• _remove and _insert_at_head are the only two list primitives needed.
• Map stores key -> node (not key -> value) so eviction can delete by key in O(1).
• Time: O(1) per operation; Space: O(capacity).

Related Problems

• 460 - LFU Cache — same eviction-cache pattern but ranks by frequency, not recency.
• 432 - All O`one Data Structure — related hash map + linked list design pattern for O(1) increment/decrement with max/min lookup.
• Related pattern: any "design a data structure with O(1) operations" problem generally combines a hash map for lookup with a linked structure for ordering.