460. LFU Cache

Practice LFU Cache for free on NudgeCode: Hard, Linked List pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Design a cache with a fixed capacity that evicts the least frequently used key when it is full.

Every key has a use count: it starts at 1 when the key is inserted and goes up by 1 on each get or put of that key.

• get(key) returns the value for key, or -1 if it is not cached.
• put(key, value) updates key if present. Otherwise it inserts key; if the cache is already full, it first removes the key with the lowest use count. On a tie, remove the one among them that was used longest ago.

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

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for the constructor and for calls that return nothing).

Example

["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]]
->  [null,null,null,1,null,-1,3,null,-1,3,4]

Constraints

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• Up to 2 * 10^5 calls in total