Implement an LFU cache with O(1) operations

Problem: LFU Cache

Design and implement a Least Frequently Used (LFU) cache. The cache should support the following operations with O(1) average time complexity:

• get(key): Return the value of the key if it exists, otherwise return -1. Increment the frequency of the accessed key.
• put(key, value): Update the value if the key exists or insert the key if it does not. If the cache reaches capacity, remove the item with the lowest frequency. If there is a tie in frequency, remove the item that was least recently used.

Interface

class LFUCache:
    def __init__(self, capacity: int):
        # Initialize cache with capacity
        pass

    def get(self, key: int) -> int:
        # Returns value if key exists, else -1
        pass

    def put(self, key: int, value: int) -> None:
        # Inserts or updates key
        pass

Constraints

• 0 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9

Examples

Example 1:

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

Edge Cases

• Capacity is 0.
• Accessing keys that do not exist.
• Repeatedly updating an existing key's value.