What is the difference between LRU and LFU cache eviction?
LRU evicts the item not used for the longest time. LFU evicts the item used the fewest times. LRU favours recency and is the common default; LFU favours long-term popularity but is slower to adapt.
Explain it simply
A cache is small, so when it is full something must go. The eviction policy decides what.
LRU (least recently used): think of your phone's recent apps list. The app you have not opened for the longest time is dropped first. It assumes recent use predicts future use.
LFU (least frequently used): keep a count of uses per item and drop the lowest count. Think of a library removing books that were borrowed the fewest times overall.
Trade-offs:
- LRU is simple and adapts quickly when popularity shifts, but one big scan of rarely used items can flush out genuinely hot ones.
- LFU protects consistently popular items, but an item that was popular last month keeps a high count and lingers, and a brand-new hot item starts at count 1 and may be evicted too soon. Counts usually decay to fix this.
FIFO and random eviction also exist and are cheap.
Example
Cache capacity 2. Accesses: A, B, A, C.
After A, B : cache = {A, B}
Access A : A used again, B is now least recent
Access C : cache full
LRU evicts B (oldest use) -> {A, C}
LFU evicts B (count 1 vs A's 2) -> {A, C}They agree here. Add D next: LRU evicts A or C by recency, LFU evicts C (count 1) and keeps A.
What to say in the interview
"LRU removes the least recently used entry, LFU the least frequently used. LRU is the usual default because it is simple and adapts quickly; LFU suits stable popularity patterns but needs count decay. I would pick based on the access pattern."