Intermediate LevelSystem Design & Architecture
Compare Cache Eviction Policies: Least Recently Used (LRU) vs Least Frequently Used (LFU) vs ARC.
❓ Interview Prompt: Compare Cache Eviction Policies: LRU (Least Recently Used), LFU (Least Frequently Used), and Adaptive Replacement Cache (ARC).
Evaluating cache memory eviction algorithms:
•
LRU (Least Recently Used): Evicts the key that has not been accessed for the longest duration. Implemented via HashMap + Doubly LinkedList in $O(1)$ time.
•
LFU (Least Frequently Used): Evicts the key with the lowest total hit frequency count. Useful for long-term hot key caching.
•
ARC (Adaptive Replacement Cache): Dynamically tunes balance between LRU and LFU based on recent workload patterns.
Code Implementation Example
typescript
// Doubly LinkedList Node for LRU Cache
class LRUNode {
constructor(public key: string, public val: any, public prev: LRUNode | null = null, public next: LRUNode | null = null) {}
}
// LRU Cache maintains HashMap for O(1) lookups and Doubly LinkedList for O(1) eviction💡LRU Cache data structure node definition.
🎯 Interview Key Takeaway
Use LRU for general-purpose cache eviction, and LFU when historical frequency indicates long-term item utility.
#System Design#LRU#LFU#Cache Eviction#Intermediate
Back to all System Design & Architecture Questions→