LFU Cache
Design a cache that holds at most capacity key-value pairs and, when it is full, evicts the entry that was used the fewest times. If several entries are tied for the fewest uses, evict the one that was used least recently among them.
Implement the class LFUCache:
new LFUCache(capacity)creates an empty cache.get(key)returns the value stored forkey, or-1if it is absent. A successfulgetcounts as one use.put(key, value)stores the value. If the key exists, its value is replaced and that counts as one use. If it is new and the cache is full, evict first as described above. A new key starts with a use count of 1.
When an entry is evicted its count is forgotten: if the key comes back later it starts again at 1. A cache with capacity 0 stores nothing. Both get and put must run in O(1) average time.
Each test is a sequence of calls. The first call creates the object. Calls that return nothing are shown as null in the expected output, and their return value isn't checked.
Constraints
0 <= capacity <= 10^40 <= key <= 10^5and0 <= value <= 10^9- At most
2 * 10^5calls in total.
Examples
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]Capacity 2. Key 1 has 2 uses and key 2 has 1, so put(3) evicts key 2. Keys 1 and 3 both have 2 uses when put(4) arrives; key 1 was used longer ago, so it goes.
Example 2
Input: ["LFUCache","put","put","get","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[2],[3,3],[1],[2],[3]]
Output: [null,null,null,1,2,null,-1,2,3]Keys 1 and 2 are tied at 2 uses. The tie goes to the least recently used one, key 1, so key 1 is evicted.
Example 3
Input: ["LFUCache","put","get","put","get"]
[[0],[0,0],[0],[1,1],[1]]
Output: [null,null,-1,null,-1]A cache of capacity 0 stores nothing.
Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.
JavaScript you'll use: Classes for data structures Map and Set
class LFUCache {
/** @param {number} capacity the most entries the cache may hold */
constructor(capacity) {
}
/**
* @param {number} key
* @return {number} the stored value, or -1 if the key is not in the cache
*/
get(key) {
}
/**
* Inserts or updates the key. If that pushes the cache over capacity, evict the least frequently used key
* (the least recently used one among ties).
* @param {number} key
* @param {number} value
* @return {void}
*/
put(key, value) {
}
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.