Lesson 163
LFU Cache
O(1) Frequency Buckets
1:00How a Least-Frequently-Used cache evicts by access count, breaks ties by recency, and achieves O(1) get and put with a three-piece hash-map-plus-bucket design.
By the end, you can
- Explain what LFU evicts and how it differs from LRU.
- Apply the tie-break rule to identify the correct eviction victim when two keys share the minimum count.
- Describe the three data-structure components of the O(1) LFU design and the role of each.
- Trace a sequence of `get` and `put` operations on a small LFU cache, tracking counts, bucket membership, and minFreq.
- Explain why a min-heap approach costs O(log n) and why the bucket design avoids that.
- Define cache pollution and explain why pure LFU is vulnerable to it.
- Name the aging strategies (LFUDA, TinyLFU) that mitigate cache pollution.
Up next in Advanced Data Structures
