LFU Cache
Evicts the least frequently used entry, breaking ties by recency.
LRU Cache: LFU: the oldest entry survives because it is the most used
get 1: a hit, value 10. Its count goes from 1 to 2, which moves it up past every entry with a lower count and to the front of the entries that share its new count.
Cost
- Get
- O(1)
- Put
- O(1)
- Space
- O(capacity)
Before this
Taught by the same lesson
LRU Cache covers these too, in the same run.