NeetCode #338LC-146MediumLinked ListNC 150NC 250
← Back to All Problems#338 · #146 · LRU Cache(LRU 缓存)
📌 Problem Statement & Constraints
Design a Least Recently Used (LRU) cache with a fixed capacity. Implement
get(key) returning the value or -1, and put(key, value). Both must run in O(1) average time. When the capacity is exceeded, evict the least recently used key. Constraints: 1 <= capacity <= 3000; at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- Two structures are needed: a hash map for O(1) lookup and a doubly linked list for O(1) recency updates.
- The list orders keys from most recently used (head) to least recently used (tail).
getandputboth move the touched key to the head; when full,putremoves the tail.- Python's
OrderedDictimplements exactly this, withmove_to_endandpopitem(last=False).
💻 Benchmark Python3 Implementation
class LRUCache:
def __init__(self, capacity: int):
from collections import OrderedDict
self.cap = capacity
self.d = OrderedDict() # front = most recently used
def get(self, key: int) -> int:
if key not in self.d:
return -1
self.d.move_to_end(key) # mark as recently used
return self.d[key]
def put(self, key: int, value: int) -> None:
if key in self.d:
self.d.move_to_end(key) # refresh recency
self.d[key] = value
if len(self.d) > self.cap:
self.d.popitem(last=False) # evict the least recently used
# From-scratch doubly linked list, if OrderedDict is disallowed
class LRUCache2:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head = {"prev": None, "next": None} # sentinels
self.tail = {"prev": self.head, "next": None}
self.head["next"] = self.tail
def _remove(self, node):
node["prev"]["next"] = node["next"]
node["next"]["prev"] = node["prev"]
def _add_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.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node["val"]
def put(self, key: int, value: int) -> None:
if key in self.map:
self._remove(self.map[key])
node = {"key": key, "val": value, "prev": None, "next": None}
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail["prev"]
self._remove(lru)
del self.map[lru["key"]]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) per operation for both variants: hash lookup plus a constant number of pointer updates.
💾 Space Complexity
O(capacity).
⚠️ Interview Pitfalls & Follow-ups
- Using a plain dict: Python dicts preserve insertion order but provide no O(1) way to remove the least recently used entry by recency.
- Forgetting to refresh recency on
putof an existing key: the key would be evicted too early. - Evicting before inserting: the size check must happen after the insertion.
- Using
popitem()withoutlast=False: that removes the most recently used item, the opposite of what is needed. - Using a singly linked list: removing an arbitrary node (needed for
get) requires the previous pointer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.