Least Frequently Used (LFU) Cache

Problem Statement

Design and implement a Least Frequently Used (LFU) cache class LFUCache.

Requirements

• LFUCache(int capacity): Initializes the object with the capacity of the data structure.
• int get(int key): Gets the value of the key if the key exists in the cache, otherwise returns -1. Accessing a key increases its frequency count.
• void put(int key, int value): Updates the value of the key if it exists, or inserts it if it is not already present. When the cache reaches capacity and an insertion is required, evict the key with the lowest frequency. If multiple keys have the same lowest frequency, evict the least recently used (LRU) one among them.

Constraints

• 0 <= capacity <= 10^5
• 0 <= key <= 10^9
• 0 <= value <= 10^9
• get and put must run in O(1) average time complexity.

Examples

# Example usage:
lfu = LFUCache(2)
lfu.put(1, 1)
lfu.put(2, 2)
lfu.get(1)      # returns 1, cache is {1: 1, 2: 2}, freq 1: {2}, freq 2: {1}
lfu.put(3, 3)   # evicts key 2, cache is {1: 1, 3: 3}
lfu.get(2)      # returns -1
lfu.get(3)      # returns 3, cache is {1: 1, 3: 3}, freq 1: {}, freq 2: {1, 3}