← All challenges

LFU cache

Medium

Implement a Least Frequently Used cache with O(1) amortized operations.

LFU cache

Problem

Caches must decide what to evict when they fill up, and recency is not the only signal that matters. LFU (Least Frequently Used) assumes the opposite of LRU: the entries accessed most often are the ones worth keeping, even if they haven't been touched recently. Real systems blend the two — Redis offers an LFU eviction mode, and frequency-aware policies keep hot objects resident in CDN and database caches. The challenge this exercise explores is tracking a per-key frequency and finding the least-frequent key in O(1) when the cache fills.

Design a Least Frequently Used (LFU) cache with O(1) amortized get and put operations. The cache tracks how often each key is accessed. When the cache is full and a new key is inserted, the key with the lowest access frequency is evicted. If there is a tie, the least recently used among the tied keys is evicted.

Input

  • capacity: number — Maximum number of key-value pairs the cache can hold. Must be greater than 0.

Output

  • LFUCache — An LFUCache instance with get(key: number): number (returns the value or -1 if absent) and put(key: number, value: number): void methods.

Examples

Example 1:

const cache = new LFUCache(2); cache.put(1, 10); cache.put(2, 20); cache.get(1); // freq(1)=2 cache.put(3, 30); // evicts key 2 (freq=1) cache.get(2); // returns -1 cache.get(3); // returns 30

Output: -1

Key 1 is accessed twice, key 2 once. When key 3 is inserted, key 2 (lowest frequency) is evicted.

Example 2:

const cache = new LFUCache(3); cache.put(1, 1); cache.put(2, 2); cache.put(3, 3); cache.get(1); // freq(1)=2 cache.get(1); // freq(1)=3 cache.put(4, 4); // evicts key 2 (freq=1) cache.get(1); // returns 1 cache.get(2); // returns -1

Output: -1

Key 1 is accessed three times. Keys 2 and 3 have frequency 1; key 2 is evicted first (LRU among ties).

Constraints

  • Capacity is at least 1.
  • All keys and values are integers.
  • get and put must each run in O(1) amortized time.
  • On eviction tie, the least recently used key among the lowest-frequency keys is removed.

Complexity

  • Time: O(1) per operation amortized
  • Space: O(capacity)

Starter

class LFUCache {
  private capacity: number;
  private keyToVal: Map<number, number> = new Map();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  // TODO: return the value for key, or -1 when the key is absent.
  // Each successful get counts as an access and must bump the key's
  // frequency.
  get(key: number): number {
    // TODO: implement
    throw new Error('not implemented');
  }

  // TODO: insert or update key -> value. When the cache is full, evict
  // the key with the lowest access frequency; on a tie, evict the least
  // recently used among the tied keys.
  put(key: number, value: number): void {
    // TODO: implement
  }
}

export function solve(capacity: number): LFUCache {
  return new LFUCache(capacity);
}

Hints

Answer