"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.
Start by confirming the contract with your interviewer:
get(key) returns the value if present, otherwise -1 (or None), and marks the key as recently used.put(key, value) inserts or updates, marks the key as recently used, and evicts the least recently used key if capacity is exceeded.Ask whether capacity can be zero and whether keys and values are integers. These small questions take ten seconds and prevent bugs later.
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.
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]
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.
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.
get.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.