25. LFU Cache

hardAsked at Nubank

Design a Least-Frequently-Used cache with O(1) get and put, breaking ties by recency; Nubank uses it to gauge whether senior candidates can layer two hash maps with frequency buckets for hot-credit-line caching.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Design an LFU cache with a fixed capacity. get(key) returns the value or -1 and bumps that key's frequency. put(key, value) inserts/updates and evicts the least-frequently-used key on overflow; if multiple keys tie on frequency, evict the least-recently-used among them. Both operations must run in O(1) average time.

Constraints

0 <= capacity <= 10^4
0 <= key, value <= 10^9
Up to 2 * 10^5 calls

Examples

Example 1

Input

['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]]

Output

[null,null,null,1,null,-1,3,null,-1,3,4]

Example 2

Input

capacity=0; put(0,0); get(0)

Output

-1

Approaches

1. Heap by (freq, time)

Store entries in a min-heap keyed by (freq, lastUsed). get/put rebuild ordering with log n cost.

Time: O(log n)
Space: O(n)

// Heap of {key, freq, ts}; on get bump freq+ts and sift; on put evict heap top. O(log n) — too slow under the O(1) bar.

Tradeoff:

2. Two maps + frequency-bucketed DLL

keyToNode maps key -> node holding {key, val, freq}. freqToList maps freq -> a doubly-linked list of nodes at that frequency in LRU order. Track minFreq. On access, move node from its list to freq+1's list; on overflow, drop the tail of freqToList[minFreq].

Time: O(1)
Space: O(capacity)

// Pseudocode
// class Node { key, val, freq, prev, next }
// class DLL { head, tail; addFront(n); remove(n); popLast(); empty() }
// keyToNode: Map<key, Node>
// freqToList: Map<freq, DLL>
// minFreq: number
//
// get(k):
//   if !keyToNode.has(k) return -1
//   n = keyToNode.get(k)
//   bump(n)
//   return n.val
//
// put(k, v):
//   if capacity === 0 return
//   if keyToNode.has(k): n = keyToNode.get(k); n.val = v; bump(n); return
//   if keyToNode.size === capacity:
//     evict = freqToList.get(minFreq).popLast()
//     keyToNode.delete(evict.key)
//   n = new Node(k, v, 1)
//   keyToNode.set(k, n)
//   freqToList.get(1) || freqToList.set(1, new DLL())
//   freqToList.get(1).addFront(n)
//   minFreq = 1
//
// bump(n):
//   freqToList.get(n.freq).remove(n)
//   if freqToList.get(n.freq).empty() and minFreq === n.freq: minFreq++
//   n.freq++
//   freqToList.get(n.freq) || freqToList.set(n.freq, new DLL())
//   freqToList.get(n.freq).addFront(n)

Tradeoff:

Nubank-specific tips

Nubank looks for whether you can articulate the minFreq invariant and how it updates on the eviction path — that's the senior-vs-mid signal on this one.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill LFU Cache and other Nubank interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →