BFS and LFU Cache Variant

amazon Design a variant of an LFU cache that supports the following operations: put(key, value): Insert or update the key-value pair. get(key): Retrieve the value corresponding to the key, or return -1 if it doesn't exist. This cache should utilize a BFS mechanism to replace the classic LFU eviction strategy. For example, when the cache capacity reaches its limit, nodes with the lowest frequency are evicted in a BFS order within the same level. Constraints: The put and get operations must have O(1) complexity. The cache must be initialized with a given capacity. Example: cache = LFU_BFS_Cache(2) cache.put(1, 1) cache.put(2, 2) cache.get(1) # returns 1 cache.put(3, 3) # evicts key 2 cache.get(2) # returns -1 cache.get(3) # returns 3 Example Input put 1 1 put 2 2 get 1 put 3 3 get 2 get 3