LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement the LFUCache class:

• LFUCache(int capacity) Initializes the cache with the given positive capacity.
• int get(int key) Returns the value of the key if present in the cache, otherwise returns -1.
• void put(int key, int value) Updates the value of the key if it exists, or inserts the key-value pair. When the cache is at capacity, invalidate and remove the least frequently used key before inserting. If multiple keys share the lowest frequency, evict the least recently used among them. To determine frequency: the use count of a key is the number of get and put calls made to it since insertion. The use count is reset to 0 when the key is removed from the cache. Inserting a key via put counts as its first use (frequency 1). The functions get and put must each run in O(1) average time complexity. Note. With capacity = 0, the cache stores nothing; every get returns -1 and every put is a no-op.