Skip to main content

25. LFU Cache

hardAsked at Intuit

Design an LFU (least-frequently-used) cache with O(1) get and put. Intuit asks this only at senior levels; it tests whether you can compose three data structures — hash for keys, hash for frequency buckets, doubly-linked lists per bucket — without breaking the O(1) contract.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit Staff onsite — LFU cited as the 90-minute deep coding round.
  • LeetCode Discuss (2025-09)— Intuit senior loop — interviewer demanded O(1) for both operations, not amortized.

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, or inserts the key if not. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (two or more keys with the same frequency), the least recently used key would be invalidated. Both get and put must run in O(1) time complexity.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • At most 2 * 10^5 calls will be made to get and put.

Examples

Example 1

Input
LFUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); get(3); put(4,4); get(1); get(3); get(4);
Output
[1,-1,3,-1,3,4]

Explanation: put(3,3) evicts key 2 (freq 1, oldest). put(4,4) evicts key 1 (freq 2 now, but lower than key 3 at 3).

Approaches

1. Sorted by frequency

Maintain a sorted structure by (freq, recency). get and put update positions in O(log n).

Time
O(log n)
Space
O(capacity)
// Conceptual — use a balanced BST keyed by (freq, time) plus a hash key→node. Skip full code; this fails the O(1) requirement.

Tradeoff: Logarithmic — fails the explicit O(1) constraint.

2. Three-structure composition (optimal)

key→node hash, freq→DLL hash (each DLL holds nodes at that frequency, ordered by recency), and a minFreq pointer. On get/put, move the node from its current freq DLL to freq+1's DLL and update minFreq if needed. On evict, pop the tail of minFreq's DLL.

Time
O(1)
Space
O(capacity)
class Node { constructor(k, v) { this.k = k; this.v = v; this.freq = 1; this.prev = null; this.next = null; } }
class DLL {
  constructor() { this.head = new Node(); this.tail = new Node(); this.head.next = this.tail; this.tail.prev = this.head; this.size = 0; }
  addFront(n) { n.next = this.head.next; n.prev = this.head; this.head.next.prev = n; this.head.next = n; this.size++; }
  remove(n) { n.prev.next = n.next; n.next.prev = n.prev; this.size--; }
  popBack() { if (this.size === 0) return null; const n = this.tail.prev; this.remove(n); return n; }
}
class LFUCache {
  constructor(capacity) { this.cap = capacity; this.keyToNode = new Map(); this.freqToList = new Map(); this.minFreq = 0; }
  _touch(n) {
    const f = n.freq;
    this.freqToList.get(f).remove(n);
    if (this.freqToList.get(f).size === 0) {
      this.freqToList.delete(f);
      if (this.minFreq === f) this.minFreq++;
    }
    n.freq++;
    if (!this.freqToList.has(n.freq)) this.freqToList.set(n.freq, new DLL());
    this.freqToList.get(n.freq).addFront(n);
  }
  get(key) {
    if (!this.keyToNode.has(key)) return -1;
    const n = this.keyToNode.get(key);
    this._touch(n);
    return n.v;
  }
  put(key, value) {
    if (this.cap === 0) return;
    if (this.keyToNode.has(key)) {
      const n = this.keyToNode.get(key);
      n.v = value;
      this._touch(n);
      return;
    }
    if (this.keyToNode.size >= this.cap) {
      const list = this.freqToList.get(this.minFreq);
      const evicted = list.popBack();
      this.keyToNode.delete(evicted.k);
      if (list.size === 0) this.freqToList.delete(this.minFreq);
    }
    const n = new Node(key, value);
    this.keyToNode.set(key, n);
    if (!this.freqToList.has(1)) this.freqToList.set(1, new DLL());
    this.freqToList.get(1).addFront(n);
    this.minFreq = 1;
  }
}

Tradeoff: True O(1) per operation. The minFreq pointer is the linchpin — without it, finding the LFU bucket would be O(unique-freq-count).

Intuit-specific tips

Intuit only asks LFU at staff+ level; expect 60-90 minutes. They grade for the three-structure invariant statement upfront and whether you derive minFreq's behavior under each operation (insert resets minFreq to 1; eviction may bump it up; promotion may bump it up). Bonus signal: mention Caffeine's W-TinyLFU as the production successor and explain the admission-policy improvement over raw LFU.

Common mistakes

  • Forgetting to update minFreq when the only-bucket-at-minFreq empties on promotion.
  • Adding the new node to freq=0's list instead of freq=1's — new nodes have a single use (the insertion).
  • Using a single sorted structure and getting O(log n) — the problem explicitly requires O(1).

Follow-up questions

An interviewer at Intuit may pivot to one of these next:

  • Add a TTL to each entry; evict on freq OR expiry.
  • Implement W-TinyLFU with a small admission filter in front of the LFU.
  • Make the cache thread-safe with minimal lock contention.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

How does minFreq get updated correctly?

Three rules: (1) On insert, minFreq = 1. (2) On promote, if the source bucket empties and source freq == minFreq, increment minFreq. (3) On evict, recompute is unnecessary because we always evict from minFreq's bucket; if that empties post-evict, the next put will reset minFreq = 1.

Why doubly-linked list and not a queue?

We need O(1) removal of an arbitrary node (when a key's freq increases). A FIFO queue only supports O(1) at the ends. DLL gives O(1) at any node we hold a pointer to.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →