LFU Cache

Design a Least Frequently Used (LFU) cache with a fixed capacity:

LFUCache(capacity) — create the cache.
get(key) — return the value for key, or -1 if absent; a successful get increases the key's use frequency.
put(key, value) — insert or update key (also increasing its frequency). If the cache is over capacity, evict the least frequently used key; if several tie on frequency, evict the least recently used among them.

Both get and put must run in O(1) average time.

Hints

· Stuck? Reveal one nudge at a time.

Evict by lowest use frequency, breaking ties by least recently used.

Group keys into one ordered bucket per frequency, and track the minimum frequency present.

Every access bumps a key up one bucket; eviction takes the LRU of the minimum-frequency bucket.

Common doubts

To evict the least-frequently-used key in O(1), you need instant access to all keys at the minimum frequency; a bucket per frequency provides exactly that.

Among the lowest-frequency keys, the tie-break is least-recently-used, so the bucket must be ordered by recency to evict the right one.

It increases by 1 only when a bump empties the current minimum bucket, and it resets to 1 whenever a brand-new key (frequency 1) is inserted.

Interview follow-ups

· What an interviewer asks next.

LRU tracks only recency (one ordered list); LFU tracks frequency first, then recency, needing a bucket per frequency plus a minFreq pointer.

Real LFU variants decay frequencies over time (e.g. Window-TinyLFU) to avoid stale keys dominating the cache forever.

Fun facts

LFU with the minFreq trick is a favorite hard design question precisely because the O(1) tie-break-by-recency is subtle.
Production caches often blend LRU and LFU (e.g. Caffeine's TinyLFU) to get the best of both.

Asked at

AmazonGoogleMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: capacity=2; put(1,1),put(2,2),get(1),put(3,3),get(2),get(3)
Output: 1, -1, 3
get(1) makes key 1 frequency 2; put(3,3) evicts key 2 (freq 1), so get(2)=-1 and get(3)=3.

Example 2

Input: capacity=0; put(0,0),get(0)
Output: -1
A zero-capacity cache stores nothing, so get returns -1.

Constraints

- 0 <= capacity <= 10^4 - 0 <= key <= 10^5 - 0 <= value <= 10^9 - At most 2 * 10^5 calls to get and put

LFU adds a twist to LRU: evict by lowest use frequency, breaking ties by least recently used. The trick is to group keys into frequency buckets — one ordered list per frequency — and track the minimum frequency present. A key's every access moves it up one bucket; eviction removes the least-recently-used key from the minimum-frequency bucket.

Prerequisites

Before you start

· Concepts used directly in the solution.

Frequency buckets. One ordered collection of keys per use-count, so all keys of a given frequency are together.

LRU order within a bucket. Within a frequency, keys are ordered by recency to break ties on eviction.

minFreq tracking. The smallest frequency currently present, so eviction is O(1).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The policy

“Does get increase frequency?”

Yes — a successful get counts as a use and bumps the frequency.

“How are frequency ties broken?”

By recency — evict the least recently used among the lowest-frequency keys.

The ideal opening — say it like this

I keep a value+frequency map, and one LRU-ordered bucket of keys per frequency.

Every get or put bumps a key from its frequency bucket to the next one, and I track the minimum frequency present.

On eviction I remove the least recently used key from the minimum-frequency bucket.

Understand the problem

Worked example — capacity = 2: put(1,1), put(2,2), get(1), put(3,3), get(2)

put(1,1) -> freq{1: [1]}                 (null)
put(2,2) -> freq{1: [1,2]}               (null)
get(1)   -> 1; bump -> freq{1:[2], 2:[1]}, minf now 1
put(3,3) -> over capacity: evict LFU=key 2 (freq 1); add 3
            freq{1:[3], 2:[1]}           (null)
get(2)   -> -1  (2 was evicted)

Key observations

1Aha

Bucket keys by frequency

Keeping one ordered list per frequency lets you find all lowest-frequency candidates instantly and pick among them by recency.

2Aha

Track minFreq for O(1) eviction

minFreq points at the bucket to evict from. It rises by one only when a bump empties the current minimum bucket, and resets to 1 on any new insertion.

3Aha

Every access bumps by exactly one

A get or an update moves the key from frequency f to f + 1, preserving the invariant that each bucket holds precisely the keys of that frequency.

Summary

Key takeaway

Keep a value+frequency map and one LRU-ordered bucket of keys per frequency, plus minFreq. Bump a key to the next bucket on every access; evict the least-recently-used key from the minFreq bucket, and reset minFreq = 1 on a new insertion. O(1) per operation.

get(key):  if absent -1; bump(key); return value
put(k,v):  if present update + bump
           else if size == cap: evict LRU of freq[minFreq]
                add (k, v) at freq 1; minFreq = 1
bump: move key from freq f bucket to freq f+1 bucket; if freq[minFreq] emptied: minFreq += 1