460. LFU Cache
hardLike LRU, but the eviction key is least-frequently-used — and when frequencies tie, fall back to least-recently-used. Two hash maps plus one doubly-linked list per frequency bucket. A senior-level data-structure-composition stress test.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement the LFUCache class: LFUCache(int capacity) initializes the object with the capacity of the data structure. int get(int key) gets the value of the key if it exists, otherwise returns -1. void put(int key, int value) updates the value of the key if present, otherwise inserts the key. If the cache reaches its capacity it should invalidate and remove the least frequently used key before inserting. When there is a tie (multiple keys with the same frequency), the least recently used key would be invalidated. Each operation must run in O(1) average time complexity.
Constraints
1 <= capacity <= 10^40 <= key <= 10^50 <= value <= 10^9At most 2 * 10^5 calls will be made to get and put.
Examples
Example 1
["LFUCache","put","put","get","put","get","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]][null,null,null,1,null,-1,3,null,-1,3,4]Explanation: Capacity 2. After put(1,1) and put(2,2), get(1)=1 (freq 1→2). put(3,3) evicts key 2 (lowest freq). get(2)=-1; get(3)=3. put(4,4) evicts key 1 (now freq=2 tied; key 3 is most recently used, key 1 is lru). get(1)=-1; get(3)=3; get(4)=4.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Keep a hash map keyToNode and a second hash map freqToList where each value is a doubly-linked list of nodes sharing that frequency.
Hint 2
Maintain a running minFreq variable. On eviction, drop the tail of freqToList[minFreq] — that's the least-recently-used node at the lowest frequency.
Hint 3
On get/put-existing, you remove the node from its current frequency list, bump its frequency, and append to the new frequency list. If you just emptied freqToList[minFreq] and the node you touched was at minFreq, increment minFreq by 1.
Solution approach
Reveal approach
Hash map plus per-frequency doubly-linked lists, with a running minFreq. Three structures: keyToNode maps key → node (each node carries key, value, freq, prev, next). freqToList maps freq → doubly-linked list (with head/tail sentinels) of nodes sharing that frequency, ordered LRU. minFreq tracks the smallest active frequency. On get(key): if not in keyToNode, return -1. Otherwise touch(node): remove from freqToList[node.freq]; if that list is now empty and node.freq == minFreq, increment minFreq; node.freq += 1; append node to head of freqToList[node.freq]; return node.value. On put(key, value): if key already exists, update value and touch. Otherwise if size == capacity, evict tail of freqToList[minFreq] and delete its key from keyToNode. Then allocate a new node with freq = 1, append to head of freqToList[1], set minFreq = 1. Every operation does a constant number of unlink + relink ops, all O(1). Memory O(capacity).
Complexity
- Time
- O(1)
- Space
- O(capacity)
Related patterns
- linked-list
- doubly-linked-list
- hash-map
- design
Related problems
- 146. LRU Cache
- 432. All O`one Data Structure
- 707. Design Linked List
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Bloomberg
Practice these live with InterviewChamp.AI
Drill LFU Cache and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →