LFU Cache
On this page
Problem statement
Design a cache with a fixed capacity that supports
get(key)andput(key, value)in O(1) average time.getreturns the value or −1.putinserts or updates a key. When the cache is full and a new key arrives, evict the key that has been used the fewest times; if several keys tie, evict the one whose last use is oldest. Bothgetandputon an existing key count as a use; a newly inserted key has a use count of 1.
LFU is the harder sibling of LRU Cache, and it is usually asked right after it. LRU needs one ordering (recency); LFU needs two (count, then recency), and the trick is keeping both in O(1) without a heap. Original problem: LeetCode 460.
Example

LFUCache(2)
put(1, A); put(2, B)
get(1) -> A # counts: 1:2, 2:1
put(3, C) # evicts 2 (count 1)
get(2) -> -1
get(3) -> C # counts: 1:2, 3:2
put(4, D) # tie at count 2: key 1 was used longer ago -> evict 1
get(1) -> -1
get(3) -> C
get(4) -> D
Constraints (assumed)
- 0 ≤ capacity ≤ 10⁴; up to 2 × 10⁵ calls.
- Keys and values are integers (letters above for readability).
What this question tests
- Breaking a two-level ordering (count, then recency) into structures that each give O(1) updates.
- Realising that counts only ever go up by one, so you never need a heap to find the new minimum.
- Keeping three structures consistent on every path: hit, update, insert, evict.
Questions to ask first
- How are ties broken? (Here: least recently used among the lowest count.)
- Does
puton an existing key count as a use? (Here: yes.) - What count does a new key start with, and does the count survive eviction? (Here: 1; an evicted key starts again at 1.)
- Can capacity be 0? (Here: yes; every
putis ignored.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.