LFU Cache
Build a cache that throws out the key you have used the fewest times. Every get that finds its key is one use, and so is every put: a new key starts at one use, and a put on a key that is already stored replaces its value and adds one use. When the cache is full and a new key arrives, evict the key with the fewest uses; if several are tied, evict the one whose last use is oldest. get returns the value, or -1 for a key that is not stored. A cache of capacity 0 stores nothing. Aim for O(1) work per call. The script driver below feeds your class a list of calls and collects what each get returns, so you only fill in the class. Limits: 0 <= capacity <= 50000, at most 200000 put and get calls, 0 <= key <= 1000000, 0 <= value <= 1000000000. Example: LFUCache(2) put(5, 50), put(6, 60) get(6) -> 60, get(6) -> 60 (key 6 has 3 uses, key 5 has 1) put(7, 70) (full: key 5 has the fewest uses and goes) get(5) -> -1, get(7) -> 70
You're building a cache that, once full, drops the key you've used the fewest times, and among ties the one you used longest ago. Interviewers love it because every call has to stay O(1), so you can't just scan for the loser. The classic traps are the tie-break and keeping the lowest count right when a key moves up or gets evicted. Expect a capacity up to 50,000 and up to 200,000 calls.
Examples
You write
LFUCache: get(key: int), put(key: int, value: int)
Example 1
- Input
- LFUCache(2), put(5,50), put(6,60), get(6) => 60, get(6) => 60, put(7,70), get(5) => -1, get(7) => 70, put(8,80), get(7) => -1, get(6) => 60, get(8) => 80
- returns
- [60, 60, -1, 70, -1, 60, 80]
Example 2
- Input
- LFUCache(0), put(1,10), get(1) => -1, put(2,20), get(2) => -1, LFUCache(1), put(3,30), get(3) => 30, put(4,40), get(3) => -1, get(4) => 40
- returns
- [-1, -1, 30, -1, 40]
Save this for your laptop
The editor and Run need a bigger screen. The link opens LFU Cache ready to code. It is free, and the editor needs no account.
The pattern behind it
Design
I reach for it when
- The statement describes a class with methods, not one function.
- Each method needs to be fast, and the structure decides how fast.
Say this before you type. Say each method, the cost you want from it, and the structure that earns that cost.
All 28 Design problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.