LFU Cache
Problem Statement
Build a class LFUCache: a key–value store with a fixed size limit. When it is full and a new key arrives, it throws out the key that has been used the fewest times (the least frequently used, "LFU"). If several keys share that smallest use count, it throws out the one among them that was used longest ago.
LFUCache(int capacity)creates an empty cache that can hold at mostcapacitykeys.int get(int key)returns the value ofkey, or-1if it is not stored. A successful get adds 1 to the key's use count.void put(int key, int value)storesvalueunderkey. If the key exists, its value is replaced and its use count goes up by 1. Otherwise, if the cache is full, the victim described above is removed first; then the new key is added with a use count of 1.
Both get and put must run in O(1) average time.
The capacity, then a sequence of get(key) and put(key, value) calls.
For each get, the stored value or -1. put returns nothing.
After get(1), key 1 has count 2 and key 2 has count 1, so put(3, 3) evicts key 2. After get(3), keys 1 and 3 both have count 2 — a tie. Key 1 was used longer ago, so put(4, 4) evicts key 1.
- • 1 ≤ capacity ≤ 10^4 (older versions allowed 0 — handle it safely anyway)
- • 0 ≤ key ≤ 10^5
- • 0 ≤ value ≤ 10^9
- • At most 2 · 10^5 calls to get and put
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Store (key, value, freq, lastUsed); scan for the key and for the victim
Map finds keys; a std::set sorted by (freq, time) gives the victim at begin()
freq → list of keys (front = most recent), key → (value, freq, iterator), track minFreq
Keep a vector of items, each with key, value, freq and lastUsed (a global timer that goes up on every use). get and put scan for the key. To evict, scan for the item with the smallest freq, and on a tie the smallest lastUsed.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.