NeetCode #340LC-460HardLinked ListNC 250
← Back to All Problems#340 · #460 · LFU Cache(LFU 缓存)
📌 Problem Statement & Constraints
Design a Least Frequently Used (LFU) cache with a fixed capacity.
get(key) and put(key, value) must run in O(1). On eviction, remove the least frequently used key; ties are broken by least recent use. Constraints: 0 <= capacity <= 10^4; at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- Three structures: a map from key to value, a map from key to frequency, and a map from frequency to an ordered set of keys at that frequency.
- The ordered set (an
OrderedDict) at each frequency stores keys in usage order, so the first key is the least recently used at that frequency. - Track
min_freqso eviction is O(1) rather than requiring a scan over frequencies. - On any access, move the key from frequency
ftof + 1and updatemin_freqif the old frequency bucket became empty.
💻 Benchmark Python3 Implementation
class LFUCache:
def __init__(self, capacity: int):
from collections import OrderedDict, defaultdict
self.cap = capacity
self.vals = {} # key -> value
self.freqs = {} # key -> frequency
self.buckets = defaultdict(OrderedDict) # freq -> keys in usage order
self.min_freq = 0
def _touch(self, key: int) -> None:
f = self.freqs[key]
del self.buckets[f][key] # leave the old frequency bucket
if not self.buckets[f]:
del self.buckets[f]
if self.min_freq == f:
self.min_freq = f + 1 # the minimum only ever rises by 1
self.freqs[key] = f + 1
self.buckets[f + 1][key] = None
def get(self, key: int) -> int:
if key not in self.vals:
return -1
self._touch(key)
return self.vals[key]
def put(self, key: int, value: int) -> None:
if self.cap <= 0:
return # a zero-capacity cache stores nothing
if key in self.vals:
self.vals[key] = value
self._touch(key)
return
if len(self.vals) >= self.cap:
# evict the LRU key within the least frequent bucket
lfu, _ = self.buckets[self.min_freq].popitem(last=False)
del self.vals[lfu]
del self.freqs[lfu]
self.vals[key] = value
self.freqs[key] = 1
self.buckets[1][key] = None
self.min_freq = 1 # a newly inserted key has frequency 1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) per operation: each step is a constant number of dictionary and OrderedDict operations.
💾 Space Complexity
O(capacity) for the three maps.
⚠️ Interview Pitfalls & Follow-ups
- Using a heap keyed by frequency: ties must be broken by recency, which a heap cannot do in O(1); the per-frequency ordered bucket handles it directly.
- Not updating
min_freqwhen a bucket empties: eviction would then target an empty bucket. Themin_freqonly needs to rise by 1, never more. - Forgetting to reset
min_freq = 1on a new insertion: a fresh key always has frequency 1, so the minimum is at most 1. - Handling
capacity == 0: everyputmust be a no-op and everygetmust return -1; without the guard, the eviction code would index an empty bucket. - Confusing LRU and LFU tie-breaking: LFU evicts the least frequent, and only uses recency as a tie-breaker.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.