LFU Cache
Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations with O(1) time complexity.

30:00

LFU Cache
hard
Topics
Companies

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations with O(1) time complexity.

Example 1:
Input: {"operations":["LFUCache","put","put","get","put","get","get","put","get","get","get"],"args":[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]}
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Constraints:

  • 1≤capacity≤1041 \leq \text{capacity} \leq 10^4

  • 0≤key,value≤1090 \leq \text{key}, \text{value} \leq 10^9

  • At most 2×1052 \times 10^5 calls will be made to get and put.

Input
arr ={"operations":["LFUCache","put","put","get","put","get","get","put","get","get","get"],"args":[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]}

Initialize LFU Cache with capacity 2

LFUCache
Cache (0/2)

Empty cache

Frequency Buckets (minFreq=0)

No frequency buckets

Capacity: 2
Size: 0
Min Freq: 0
Variables
No variables to display
DepthFunction Call
Stack empty
0/13