LFU Cache
Hard · Design · Hash Table · Linked List · Design
Problem
Design a cache that evicts the least frequently used key when it is full. Implement the class LFUCache:
- LFUCache(capacity) creates an empty cache with room for capacity keys.
- get(key) returns the key's value, or -1 if the key is absent.
- put(key, value) updates the value of an existing key, or inserts a new key. If inserting a new key when the cache is already at capacity, first evict the key with the smallest use count. If several keys share that smallest count, evict the one among them that was used least recently.
Every key has a use counter. It starts at 1 when the key is inserted and goes up by 1 on each get or put that touches the key. An evicted key loses its counter. get and put should both run in O(1) average time.
Tests call the class through a sequence: ops[0] is the class name with vals[0] its constructor arguments, and each later ops[i] is a method called with vals[i]. The expected output lists each call's return value (None for the constructor and put).
Examples
Input: ops = ["LFUCache","put","put","get","put","get","get","get"], vals = [[2],[1,10],[2,20],[1],[3,30],[2],[3],[1]] Output: [null,null,null,10,null,-1,30,10]
After get(1), key 1 has been used twice and key 2 once, so inserting key 3 evicts key 2.
Input: ops = ["LFUCache","put","put","put","get","get"], vals = [[2],[1,1],[2,2],[3,3],[1],[2]] Output: [null,null,null,null,-1,2]
Keys 1 and 2 are tied at one use, so the older one, key 1, is evicted to make room for key 3.
Input: ops = ["LFUCache","put","put","put","put","get","get","get"], vals = [[2],[1,1],[2,2],[1,10],[3,3],[1],[2],[3]] Output: [null,null,null,null,null,10,-1,3]
Updating key 1 is a use, so it has two uses and key 2 is evicted when key 3 arrives.
Constraints
- 1 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 · 10^5 calls are made to get and put
Approaches
- Scan every key for the victim — time O(1) for get, O(capacity) for a put that evicts, space O(capacity)
Follow-up
LFU keeps old favorites forever: a key used a million times last week outlives everything new. Real caches age the counts (halve them periodically), or use designs like TinyLFU, which estimate frequency with a small counting sketch and admit a new key only if it is likely to be used more than the victim.
Related problems
Start free on Cariara · Coding problems · System design studio
