Implement an LFU cache

Problem: LFU Cache

Design and implement a Least Frequently Used (LFU) cache with a fixed capacity.

The cache supports the following operations:

• get(key) -> value
  • Return the value of key if it exists in the cache.
  • Otherwise return -1 .
  • If the key exists, its usage frequency increases by 1.
• put(key, value) -> void
  • Insert or update the value of key .
  • If the cache reaches capacity, it must evict one key before inserting.

Eviction Policy

1. Evict the key with the lowest frequency (LFU).
2. If multiple keys have the same (lowest) frequency, evict the least recently used (LRU) among them.

Requirements / Constraints

• Capacity is a non-negative integer.
• Aim for O(1) average time per operation.
• If capacity == 0 , put does nothing and get always returns -1 .

Example

If capacity = 2:

• put(1, 1)
• put(2, 2)
• get(1) returns 1 (freq(1)=2)
• put(3, 3) evicts key 2 (freq(2)=1 is lowest)
• get(2) returns -1
• get(3) returns 3