LFU Cache

Implement LFUCache(capacity), with nonnegative capacity. get(key) returns its integer value or -1 if missing; a successful get increases its frequency and makes it most recently used at its new frequency. put(key,value) returns None; inserting starts frequency 1, updating an existing key also increases its frequency. When full, evict the lowest-frequency key; tie-break by least recently used within that frequency. Missing gets do not change any recency or frequency. Capacity 0 stores nothing. Keys are integers and may be negative; aim for O(1) expected operations. Examples (JSON; null means Python None): Input: {"capacity": 2, "operations": [["put", [1, 10]], ["put", [2, 20]], ["get", [1]], ["put", [3, 30]], ["get", [2]], ["get", [3]]]} Output: [null, null, 10, null, -1, 30] Input: {"capacity": 2, "operations": [["put", [1, 1]], ["put", [2, 2]], ["put", [3, 3]], ["get", [1]], ["get", [2]]]} Output: [null, null, null, -1, 2]

class LFUCache:

    def __init__(self, capacity: int):
        """Implement this operation according to the statement."""
        pass

    def get(self, key: int) -> int:
        """Implement this operation according to the statement."""
        pass

    def put(self, key: int, value: int) -> None:
        """Implement this operation according to the statement."""
        pass