Heap / Priority Queue
LC #460Hard
LFU Cache
Heap / Priority Queue
Problem
Design and implement a data structure for a Least Frequently Used (LFU) cache.
designhash-maplinked-list
Constraints
- ›1 ≤ capacity ≤ 10⁴
- ›0 ≤ key ≤ 10⁵
- ›0 ≤ value ≤ 10⁹
- ›get and put must be O(1) average. At most 2 * 10⁵ calls made.
Example
Input
LFUCache(2) → put(1,1) → put(2,2) → get(1) → put(3,3) → get(2)Output
get(1)=1, get(2)=-1Why
After put(3,3), key 2 was evicted because it was used 1 time, whereas key 1 was used 2 times.