LRU Cache — LeetCode 146 FAANG Design Classic

Problem Statement#

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement the LRUCache class with the following methods.

• LRUCache(capacity) — initialize the cache with positive capacity
• get(key) — return the value if it exists, otherwise return -1, and mark the key as most recently used
• put(key, value) — insert or update the key. If size exceeds capacity, evict the least recently used key

Both operations must run in O(1) average time.

Constraints:

• 1 less-equal capacity, key, value less-equal 10000
• Up to 200000 calls

Input:  ["LRUCache","put","put","get","put","get","put","get","get","get"]
        [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Why This Problem Matters#

LRU Cache is the single most-asked LRU cache interview question at FAANG. Google, Meta, Amazon, and Apple all rotate it through phone screens and onsite loops. The reason is simple: it tests whether you can compose two data structures, maintain an invariant across them, and reason about both time and space.

It is also a stepping stone to real system design. Memcached, Redis, page caches in Linux, and database buffer pools all use LRU or its near relatives. Showing you understand the data structure underneath earns instant credibility in the bigger system design conversation.

The Core Insight#

A single hashmap gives O(1) lookup but cannot tell you which key was used least recently. A single linked list gives O(1) reorder but O(n) lookup. The trick is to combine them.

Use a doubly linked list to store entries in recency order. The head is most recent, the tail is least recent. Use a hashmap from key to DLL node to jump straight to any node in O(1). On every operation, move the touched node to the head. On overflow, evict the tail and remove its key from the map.

The invariant: hashmap keys equal DLL node keys, and the DLL is ordered by access recency.

Visual Dry Run#

Capacity 2. Operations: put 1 1, put 2 2, get 1, put 3 3, get 2.

Solution (Optimal)#

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: int):
        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: int) -> int:
        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: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return
        if len(self.cache) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
};
 
LRUCache.prototype.get = function(key) {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
};
 
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key);
    } else if (this.cache.size === this.capacity) {
        const oldest = this.cache.keys().next().value;
        this.cache.delete(oldest);
    }
    this.cache.set(key, value);
};

Time: O(1) for both get and put — hashmap lookup plus constant DLL pointer updates. Space: O(capacity) — one node per stored key.

Common Mistakes#

• Using a singly linked list, which forces O(n) removal
• Forgetting to delete the evicted key from the hashmap
• Not maintaining sentinel head and tail nodes, leading to null pointer bugs
• Updating the DLL but forgetting the map on capacity overflow
• Treating get as read-only and not bumping recency

Interview Tips#

• Draw the doubly linked list and hashmap on the whiteboard
• State the invariant aloud before coding
• Use sentinel nodes to remove edge cases at head and tail
• In JavaScript, mention that Map iteration order equals insertion order which simplifies the code
• Mention thread safety as a follow-up — real LRU caches need locks or lock-free structures

Follow-up Questions#

• Make it thread-safe — consider a striped lock per bucket
• Add TTL — store expiry timestamp on each node and lazy expire on access
• Make it size-aware where each entry has variable byte size
• Implement an LFU variant — see LeetCode 460
• Distribute it across machines — consistent hashing plus per-shard LRU

Key Takeaways#

• LRU Cache is LeetCode 146, the top design problem at FAANG
• Doubly linked list plus hashmap gives O(1) get and put
• Sentinel head and tail nodes eliminate boundary cases
• The invariant is hashmap keys equal DLL keys
• Python uses a manual DLL for clarity, JavaScript can lean on Map insertion order
• Eviction touches both the DLL tail and the map
• Memcached and Redis use LRU variants in production