Skip to main content

24. LFU Cache

hardAsked at JetBrains

Design an O(1) least-frequently-used cache — JetBrains uses this to test layered data-structure design, the kind powering their PSI stub and reference caches.

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

Problem

Design a Least Frequently Used cache with get(key) and put(key, value) both running in O(1). On eviction, remove the key with the smallest use count; break ties by least-recently used.

Constraints

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

Examples

Example 1

Input
cap=2; put(1,1); put(2,2); get(1); put(3,3); get(2);
Output
1, -1

Example 2

Input
cap=2; put(1,1); put(2,2); get(1); put(3,3); get(3);
Output
1, 3

Approaches

1. Sort on eviction

Track (key, freq, lastUsed); on eviction, sort entries to find the least-frequent oldest entry. get/put degrade to O(n log n).

Time
O(n log n) per op
Space
O(n)
// linear scan or sort on each eviction — fails for the O(1) contract

Tradeoff:

2. Hash maps + per-frequency doubly-linked lists

Maintain key→node, freq→linked-list-of-nodes, and a running minFreq. get and put manipulate three structures, but each operation is O(1). Same layered eviction shape JetBrains stub/reference caches use to drop cold entries.

Time
O(1) per op
Space
O(n)
class LFUCache {
  constructor(cap) {
    this.cap = cap; this.size = 0; this.minFreq = 0;
    this.keyNode = new Map();   // key -> { key, val, freq, prev, next }
    this.freqList = new Map();  // freq -> { head, tail } sentinel pair
  }
  _list(freq) {
    if (!this.freqList.has(freq)) {
      const head = {}, tail = {};
      head.next = tail; tail.prev = head;
      this.freqList.set(freq, { head, tail });
    }
    return this.freqList.get(freq);
  }
  _detach(node) { node.prev.next = node.next; node.next.prev = node.prev; }
  _append(freq, node) {
    const { tail } = this._list(freq);
    node.prev = tail.prev; node.next = tail;
    tail.prev.next = node; tail.prev = node;
  }
  _bump(node) {
    this._detach(node);
    const oldList = this.freqList.get(node.freq);
    if (node.freq === this.minFreq && oldList.head.next === oldList.tail) this.minFreq++;
    node.freq++;
    this._append(node.freq, node);
  }
  get(key) {
    const node = this.keyNode.get(key);
    if (!node) return -1;
    this._bump(node);
    return node.val;
  }
  put(key, val) {
    if (this.cap === 0) return;
    if (this.keyNode.has(key)) { const n = this.keyNode.get(key); n.val = val; this._bump(n); return; }
    if (this.size === this.cap) {
      const { head, tail } = this._list(this.minFreq);
      const lru = head.next;
      this._detach(lru); this.keyNode.delete(lru.key); this.size--;
    }
    const node = { key, val, freq: 1, prev: null, next: null };
    this._append(1, node);
    this.keyNode.set(key, node);
    this.minFreq = 1; this.size++;
  }
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to layer the three data structures cleanly and call out which invariants each maintains — the same discipline behind their tiered PSI / stub / reference caches.

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 JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →