LFU cache

LFU cache

Problem

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);
}