Implement LFU Cache

Design and implement an LFU (Least Frequently Used) cache with capacity capacity. Support the following operations with O(1) average time complexity: get(key): If key exists, return its value and increment its usage frequency freq by 1. If key does not exist, return -1. put(key, value): If capacity == 0, do nothing. If key exists, update its value and increment its freq by 1. If key does not exist: If the cache is full, evict one entry: Evict the entry with the lowest frequency (LFU). If multiple entries have the same frequency, evict the least recently used among them. Insert the new entry with initial frequency 1. Implement this data structure/class. Example capacity = 2 put(1, 1) put(2, 2) get(1) -> 1 put(3, 3) # evicts key=2 get(2) -> -1 get(3) -> 3 put(4, 4) # evicts key=1 get(1) -> -1 get(3) -> 3 get(4) -> 4 Constraints 0 <= capacity <= 10^4 0 <= key, value <= 10^5 Number of get/put calls <= 2*10^5 Example Input 2 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 put 4 4 get 1 get 3 get 4 Output 1 -1 3 -1 3 4