LFU Cache

hard · frequency buckets

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]

Starter code

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
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

3 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. RecruiterCharacter joke · No posting date

    We loved your energy. We went with the candidate whose code compiled.

  2. TryGetValueCharacter joke · No posting date

    My solution passed all the tests. All zero of them. I forgot to run them.

  3. TryGetValueCharacter joke · No posting date

    I solved this in O(1). Then I remembered I actually have to write the code. O(n) regrets.