Skip to main content

15. LFU Cache

hardAsked at Redis

Implement a Least-Frequently-Used cache with O(1) get and put; Redis loves it because LFU eviction (allkeys-lfu) is one of its native maxmemory policies.

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

Problem

Implement LFUCache with capacity C. Both get and put must run in O(1). On capacity overflow evict the least-frequently-used key; break ties by LRU among that frequency tier.

Constraints

  • 0 <= capacity <= 10^4
  • Up to 2 * 10^5 calls

Examples

Example 1

Input
capacity=2; put(1,1); put(2,2); get(1)=1; put(3,3) evicts 2; get(2)=-1
Output
see explanation

Approaches

1. Sort by frequency on eviction

Maintain a Map of {key: [value, freq]} and scan on each put.

Time
O(n) per put
Space
O(n)
// Scan map for (minFreq, oldestAtMinFreq) on every eviction.

Tradeoff:

2. Three maps: key->node, freq->list, plus minFreq

Store each key in a doubly linked list bucketed by frequency. On get bump the node to the next-higher freq list. Maintain minFreq for O(1) eviction. Mirrors Redis's LFU counter with logarithmic-decay sampling.

Time
O(1) per op
Space
O(capacity)
class LFUCache {
  constructor(cap) {
    this.cap = cap;
    this.size = 0;
    this.minFreq = 0;
    this.keyNode = new Map();
    this.freqList = new Map(); // freq -> LinkedList of nodes
  }
  get(k) { /* if missing return -1; else bump freq and return value */ }
  put(k, v) { /* if exists update value + bump; else evict if full, insert with freq=1, minFreq=1 */ }
}

Tradeoff:

Redis-specific tips

Redis interviewers grade for the three-map design AND for naming the LFU counter decay trick — real Redis uses an 8-bit counter that probabilistically increments and decays over time to avoid frequency-stuck keys.

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

Practice these live with InterviewChamp.AI →