How to Solve the LRU Cache Interview Question Step by Step

"Design an LRU cache" is one of the most common coding interview questions at mid-size and large tech companies. It sits between data structures and design: you must support get(key) and put(key, value) in O(1) time, and when the cache is full, evict the least recently used item. Here's a step-by-step way to reason about it so you're not just reciting a memorized answer.

Step 1: Restate the requirements

Start by confirming the contract with your interviewer:

Ask whether capacity can be zero and whether keys and values are integers. These small questions take ten seconds and prevent bugs later.

Step 2: Find what each operation needs

Neither structure works alone. A hash map has no order, and a linked list has no fast lookup. Combine them: the map stores key → node, and the list keeps nodes ordered from most to least recently used.

Saying this reasoning out loud is the most important part of the answer. Interviewers want to see you derive the design from the requirements.

Step 3: Use sentinel nodes

Create dummy head and tail nodes so the list is never empty. This removes almost every edge case around inserting at the front or removing the last real node.

class Node:
    def __init__(self, k=0, v=0):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _add_front(self, n):
        n.next, n.prev = self.head.next, self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, k):
        if k not in self.map:
            return -1
        n = self.map[k]
        self._remove(n); self._add_front(n)
        return n.v

    def put(self, k, v):
        if k in self.map:
            self._remove(self.map[k])
        n = Node(k, v)
        self.map[k] = n
        self._add_front(n)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]

Step 4: Walk through an example

With capacity 2: put(1), put(2), get(1), put(3). After get(1), key 1 is most recent, so put(3) evicts key 2. Tracing this by hand catches the most common bug: evicting from the wrong end.

Step 5: Mention the shortcut, then explain why you didn't rely on it

Python's OrderedDict (with move_to_end and popitem(last=False)) and Java's LinkedHashMap can implement LRU in a few lines. It's worth mentioning, but most interviewers will ask you to build it yourself. Offering both shows you know the standard library and the underlying mechanics.

Likely follow-up questions

Common mistakes

Disclosure: I work on Linkjob AI. The Linkjob AI interview assistant can help you rehearse explaining designs like this, but tracing the pointer updates by hand a few times is still the best preparation.