A cache that forgets the least used
Reported in interviews at (where)
Build LFUCache, a store of whole-number keys and values that holds at most capacity keys and remembers how often each key has been used.
LFUCache(capacity) starts empty.
get(key) returns the value stored for key, or -1 if the key is not in the cache.
put(key, value) stores value for key, replacing the value the key had. If that adds a new key to a full cache, one key leaves first: the one used the fewest times, and among those with the same count, the one used longest ago.
A get of a key that is in the cache and every put add one use to that key; a key that is added starts with one use. A key that leaves the cache forgets its count. Aim for O(1) time per call.
- Input
["LFUCache","put","put","get","put","get","get","put","get","get","get"]
[[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 been used once and key 1 twice, so key 3 pushes key 2 out. Keys 1 and 3 then have two uses each; key 1 was used longer ago, so key 4 pushes it out.
- Input
["LFUCache","put","get","put","get","get"]
[[1],[5,50],[5],[6,60],[5],[6]]- Output
[null,null,50,null,-1,60]
With room for one key, a new key always replaces the old one, however often it was used.
Limits
1 <= capacity <= 30000 <= key <= 100000 <= value <= 100000at most 20000 calls after the constructor
Hints
Hint 1
Group the keys by how many times they have been used, and inside each group keep them in the order they were used.
Hint 2
Remember the smallest count in use: it only resets to 1 when a new key arrives, and it only grows by one when the last key of that count is used again.
Where this was reported
- Amazon, SDE-1 new grad interview, 2024 (Reddit)
- Cisco, Technical intern assessment, 2026 (Reddit)
- Amazon, SDE-1 interview, 2025 (LeetCode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.

