Skip to main content

25. LFU Cache

hardAsked at GitLab

Implement a cache with O(1) get and put that evicts the least frequently used entry, breaking ties by least recently used.

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

Problem

Design an LFU cache with capacity C that supports get(key) and put(key, value) in O(1). When the cache is full, evict the least frequently used item; on a frequency tie, evict the least recently used among them.

Constraints

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

Examples

Example 1

Input
cap=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

Example 2

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

Approaches

1. Heap by (freq, time)

Keep a min-heap keyed by (freq, last-access tick). Get/put are O(log n) — fails the contract but is conceptually simpler.

Time
O(log n)
Space
O(n)
/* Min-heap with stale entries; lazy delete on pop. Conceptually clear but slower than O(1). */

Tradeoff:

2. Freq buckets of ordered maps

Map key -> {value, freq}; map freq -> insertion-ordered Map of keys at that freq. Track minFreq. On access, move the key to bucket freq+1 and bump minFreq if its old bucket empties. Eviction pulls the first key from the minFreq bucket.

Time
O(1)
Space
O(C)
class LFUCache {
  constructor(capacity){
    this.cap = capacity;
    this.entries = new Map();
    this.buckets = new Map();
    this.minFreq = 0;
  }
  _touch(key){
    const e = this.entries.get(key);
    this.buckets.get(e.freq).delete(key);
    if (this.buckets.get(e.freq).size === 0){
      this.buckets.delete(e.freq);
      if (this.minFreq === e.freq) this.minFreq++;
    }
    e.freq++;
    if (!this.buckets.has(e.freq)) this.buckets.set(e.freq, new Map());
    this.buckets.get(e.freq).set(key, true);
  }
  get(key){
    if (!this.entries.has(key)) return -1;
    this._touch(key);
    return this.entries.get(key).value;
  }
  put(key, value){
    if (this.cap === 0) return;
    if (this.entries.has(key)){
      this.entries.get(key).value = value;
      this._touch(key);
      return;
    }
    if (this.entries.size >= this.cap){
      const bucket = this.buckets.get(this.minFreq);
      const evictKey = bucket.keys().next().value;
      bucket.delete(evictKey);
      if (bucket.size === 0) this.buckets.delete(this.minFreq);
      this.entries.delete(evictKey);
    }
    this.entries.set(key, { value, freq: 1 });
    if (!this.buckets.has(1)) this.buckets.set(1, new Map());
    this.buckets.get(1).set(key, true);
    this.minFreq = 1;
  }
}

Tradeoff:

GitLab-specific tips

GitLab maps LFU onto runner-pool warm caches — they want to see that you can keep frequency ordering and LRU tie-breaking both O(1) when scheduling artifact reuse across a million jobs.

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

Practice these live with InterviewChamp.AI →