LFU Cache
Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.
Practice this as a mock interviewFree to start, no account neededProblem
Design a fixed-capacity key-value cache that evicts the **least frequently used** key when full.
Every key in the cache has a use counter. Inserting a new key sets its counter to 1. A successful get, or a put that updates an existing key, adds 1 to that key's counter. When a new key must be inserted into a full cache, first evict the key with the **smallest counter**. If several keys share the smallest counter, evict the one whose most recent use is **oldest** (least recently used among them). An evicted key's counter is forgotten; if it is inserted again, it starts over at 1.
Implement:
- LFUCache(capacity) creates the cache.
- get(key) returns the key's value (and counts as a use) or -1 if absent.
- put(key, value) updates an existing key's value (counts as a use), or inserts the key, evicting first if the cache is full.
Both operations must run in **O(1)** average time.
Examples
Constraints
- 1 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 * 10^5 calls to `get` and `put`.
What the interviewer grades
A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.