LFU Cache
01 · Problem
Design a cache with a fixed capacity that evicts the least frequently used key when it is full. Implement the LFUCache class:
LFUCache(int capacity)creates the cache with the given positive capacity.int get(int key)returns the value stored forkey, or-1if the key is not present.void put(int key, int value)sets the value forkey, inserting it if absent. If inserting a new key would exceed the capacity, first evict the key with the lowest use count. If several keys share that lowest count, evict the one among them that was used least recently.
A key's use count starts at 1 when it is inserted and increases by 1 on every successful get and on every put that updates an existing key. Both get and put should run in O(1) average time.
The input lists the method names and their arguments; the output lists the return value of each call, with null for the constructor and for put.
02 · Examples
["LFUCache","put","put","get","put","put","get","get","get"], [[2],[1,10],[2,20],[2],[1,15],[3,30],[2],[1],[3]]
[null,null,null,20,null,null,-1,15,30]
After get(2) and put(1,15), keys 1 and 2 both have count 2. Key 2 was used earlier (at get(2)) than key 1 (at put(1,15)), so put(3,30) evicts key 2.
["LFUCache","put","get","put","get","get"], [[1],[5,5],[5],[6,6],[5],[6]]
[null,null,5,null,-1,6]
With capacity 1, inserting key 6 must evict key 5, so get(5) returns -1 and get(6) returns 6.
03 · Constraints
- 011 <= capacity <= 104
- 020 <= key <= 105
- 030 <= value <= 109
- 04At most 2 * 105 calls will be made to get and put in total.
04 · Optimal complexity
- Time
- O(1) per operation
- Space
- O(capacity)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.