By Fatskills Exam Guides Team — the exam nerds behind 28,500+ quizzes and 2.1M practice questions across 500+ global exams.
"This problem appears in 1 out of every 3 onsite interviews—nail it, and you prove you can design real-world systems with optimal trade-offs between speed and memory."
Before tackling LRU Cache, ensure you understand: 1. Hash Maps (Dictionaries) – O(1) average-time lookups/insertions/deletions. 2. Doubly Linked Lists – O(1) insertions/deletions at both ends. 3. Time-Space Trade-offs – Balancing fast access with memory constraints.
cache = {key: Node}, head/tail pointers
head.next = tail, tail.prev = head
remove(node), add_to_front(node)
if len(cache) > capacity: remove(tail.prev)
get
put
if key in cache
Follow these steps every time you solve an LRU Cache problem:
get(key)
-1
Confirm put(key, value) evicts LRU item if capacity is exceeded.
put(key, value)
Choose Data Structures
key → Node
Doubly Linked List: Maintain usage order (most recent at head, LRU at tail).
Design Node Structure
Each node has key, value, prev, next.
key
value
prev
next
Initialize Dummy Head/Tail
Simplifies edge cases (e.g., empty list).
Implement Helper Methods
_remove(node)
_add_to_front(node): Insert node after head.
_add_to_front(node)
Implement get(key)
Else: Return -1.
Implement put(key, value)
Else:
Test Edge Cases
Problem: Design an LRU cache with get and put in O(1) time.
dict
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() # Dummy head self.tail = Node() # Dummy tail self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node 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) else: if len(self.cache) >= self.capacity: lru_node = self.tail.prev self._remove(lru_node) del self.cache[lru_node.key] new_node = Node(key, value) self.cache[key] = new_node self._add_to_front(new_node)
Problem: Extend LRU Cache to support get(key, timestamp) where items expire after ttl seconds.
get(key, timestamp)
ttl
expiry_time
timestamp > expiry_time
expiry_time = timestamp + ttl
class Node: def __init__(self, key=0, value=0, expiry_time=0): self.key = key self.value = value self.expiry_time = expiry_time self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int, ttl: int): self.capacity = capacity self.ttl = ttl self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node 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, timestamp: int) -> int: if key not in self.cache: return -1 node = self.cache[key] if timestamp > node.expiry_time: self._remove(node) del self.cache[key] return -1 self._remove(node) self._add_to_front(node) return node.value def put(self, key: int, value: int, timestamp: int) -> None: if key in self.cache: node = self.cache[key] node.value = value node.expiry_time = timestamp + self.ttl self._remove(node) self._add_to_front(node) else: if len(self.cache) >= self.capacity: lru_node = self.tail.prev self._remove(lru_node) del self.cache[lru_node.key] new_node = Node(key, value, timestamp + self.ttl) self.cache[key] = new_node self._add_to_front(new_node)
Problem: Design an LRU cache that also tracks access frequency (e.g., for analytics).
frequency
class Node: def __init__(self, key=0, value=0): self.key = key self.value = value self.frequency = 1 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): prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node 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] node.frequency += 1 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 node.frequency += 1 self._remove(node) self._add_to_front(node) else: if len(self.cache) >= self.capacity: lru_node = self.tail.prev self._remove(lru_node) del self.cache[lru_node.key] new_node = Node(key, value) self.cache[key] = new_node self._add_to_front(new_node)
len(cache) >= capacity
key → value
capacity=0
"Alright, let’s lock this in. LRU Cache is all about O(1) operations—so you must combine a hash map with a doubly linked list. Here’s the playbook:
Test edge cases: empty cache, single item, duplicates, full capacity. If they ask for a twist—like expiry or frequency—extend the node structure, but keep the core O(1) operations.
You’ve got this. Now go crush that interview!
This framework is interview-ready—use it verbatim. Good luck! ?
Join 4M+ learners. Unlock unlimited quizzes, wrong-answer tracking, flashcards + reminders, study guides, and 1-on-1 challenges.