From FizzBuzz to LRU Cache: Coding Interview Questions in 5 Levels

Now the famous one. The LRU Cache problem combines HashMaps, linked lists, and design thinking. It appears regularly at Google, Amazon, Meta, and other top-tier interviews because it is the smallest possible problem that forces a candidate to combine two data structures deliberately.

The requirement. Both get(key) and put(key, value) must run in O(1). When capacity is exceeded the least recently used item is evicted. LRU caches power browser caches, database buffer pools, operating system page caches, CDNs, and almost every memory tier in production systems.

Why arrays alone fail. Searching is O(n), deletion is O(n), and updating order is inefficient. A linked list alone solves the ordering problem but still costs O(n) to find a key. A HashMap alone solves lookup but cannot track usage order.

The optimal combination. A HashMap maps keys to nodes. A doubly linked list orders nodes from most recently used to least recently used. Every access moves the node to the front; every eviction removes from the back. Both operations are O(1).

Node and class.

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


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache    = {}

        # Sentinel nodes — left = LRU side, right = MRU side
        self.left  = Node(0, 0)
        self.right = Node(0, 0)
        self.left.next  = self.right
        self.right.prev = self.left

    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    def insert(self, node):
        # Insert just before the right sentinel (MRU end)
        prev, nxt = self.right.prev, self.right
        prev.next = node
        node.prev = prev
        node.next = nxt
        nxt.prev  = node

    def get(self, key):
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].value
        return -1

    def put(self, key, value):
        if key in self.cache:
            self.remove(self.cache[key])

        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.capacity:
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

Complexity: get and put are both O(1), space O(capacity).

Interview talking points. Explain why arrays fail, why linked lists alone are not enough, why the list must be doubly linked, and how the HashMap accelerates lookup. Communication here matters as much as code — even a perfect solution loses points when the candidate cannot articulate the trade-offs.

Frequent mistakes. Forgetting to update pointers, removing the wrong node, breaking the chain when the list has one item, mishandling duplicate keys in put, and forgetting to remove the evicted entry from the HashMap when the list pops it.