LRU vs LFU Implementation
LRU (Least Recently Used) evicts the item unused the longest, while LFU (Least Frequently Used) removes the item with the lowest access frequency in an in-memory cache system.
When to Use
Use LRU when access patterns change quickly, such as user session caches or feed data. Use LFU for workloads with stable “hot” data like trending videos or product catalogs that are repeatedly accessed.
Example
If your cache of size 3 sees A, B, C, A, A, D — LRU evicts the least recent (B), while LFU keeps A due to higher frequency.
Explore more with Grokking System Design Fundamentals, Grokking the Coding Interview, or Mock Interviews with ex-FAANG engineers to master these concepts through hands-on learning.
Why Is It Important
Efficient eviction policies reduce cache misses and improve system latency.
The right algorithm ensures optimal cache hit rate and memory efficiency.
Interview Tips
Explain LRU uses a HashMap + Doubly Linked List for O(1) operations. LFU adds frequency tracking via min-heaps or linked frequency lists, which adds complexity but better reflects long-term popularity.
Trade-offs
LRU is simple and fast but may evict valuable items under cyclic workloads. LFU offers higher hit rates for stable patterns but adds overhead for maintaining counts and rebalancing structures.
Pitfalls
Avoid naive LFU implementations that don’t decay old frequencies, leading to cache pollution. Similarly, incorrect LRU pointer management can degrade O(1) guarantees.
Pro Tip: To go deeper, explore Grokking the System Design Interview or Grokking Database Fundamentals for Tech Interviews.
GET YOUR FREE
Coding Questions Catalog
$197
$78
$78
