LFU Cache

Design LFUCache(capacity), a cache with a fixed positive capacity. get(key) returns the stored value or -1 for an absent key. put(key, value) inserts or…

Design LFUCache(capacity), a cache with a fixed positive capacity. get(key) returns the stored value or -1 for an absent key. put(key, value) inserts or updates a key. New keys start with frequency 1. Every successful get and existing-key put increases that key's frequency by one and makes it the most recent key at its new frequency. A missing get changes neither frequency nor recency. Before inserting a new key into a full cache, evict a key with the smallest frequency; break ties by least recent successful access or update. A reinserted key starts at frequency 1. Implement get and put in O(1) average time. The driver supplies aligned operations and arguments arrays, constructor first, and records null for construction/put or the integer result for get. Implement the class methods; do not print or return the transcript.

Positive capacity: 1..1000. Keys: strict integers 0..10000. Values: strict integers 0..100000. At most 100000 get/put calls after construction (1..100001 records total). Arrays must align; exactly one constructor appears first. get takes one key; put takes key and value. No separate target. Teaching playback accepts at most 12 records and capacity at most 4; coding retains all bounds above.

Example 1: input operations = ["LFUCache","put","put","get","put","get","get","put","get","get","get"], arguments = [[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]. Key 2 has frequency 1 and is evicted before key 1. Key 3 later reaches frequency 2 after key 1 last succeeded, so inserting key 4 evicts key 1 by the least-recent tie rule.

Example 2: input operations = ["LFUCache","put","put","put","put","put","get","get","get","get","get"], arguments = [[3],[5,7],[4,6],[3,5],[2,4],[1,3],[1],[2],[3],[4],[5]]; output [null,null,null,null,null,null,3,4,5,-1,-1]. New keys start at frequency 1. With capacity 3, inserting key 2 evicts key 5 and inserting key 1 evicts key 4. Reads of live keys 1, 2 and 3 return their values 3, 4 and 5; keys 4 and 5 return -1.

Category: Arrays & Hashing. Topic: arrays. Difficulty: Hard. Patterns: hashing, linked-list-traversal.