Implement LFU Cache

Implement an LFU (Least Frequently Used) cache with the following operations: get and put. When the cache reaches its capacity, it should evict the least frequently used items. If there is a tie, then it should evict the least recently used among the least frequently used items. Function Definitions: class LFUCache: def __init__(self, capacity: int): Initialize the LFU cache object with a positive integer representing the capacity of the cache. def get(self, key: int) -> int: Return the value of the key if it exists in the cache; otherwise, return -1. def put(self, key: int, value: int): If the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. Example: Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4] Example Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]