Skip to content
Onsite
20 / 20

LFU Cache

HardP3Coding

Design a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

  • LFUCache(capacity) creates a cache holding at most capacity keys.
  • get(key) returns the value of key, or -1 if it is absent.
  • put(key, value) inserts or updates the value. If inserting a new key would exceed the capacity, first evict one key: the one with the lowest use count; if several tie, the least recently used among them.

A key's use count is the number of get and put calls that touched it since it was inserted (a fresh insert has count 1). Evicting removes the count; a key inserted again starts at 1. With capacity 0 the cache stores nothing.

Both operations must run in O(1) average time.

Example 1

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]
Why
Key 1 has count 2, key 2 has count 1, so inserting 3 evicts key 2.

Constraints

  • 0 <= capacity <= 10^4
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • At most 2 * 10^5 calls.

Hints

Run checks the 2 visible tests, Submit all 8.