LRU Cache
Design a cache that holds at most capacity key-value pairs and, when it is full, throws out the entry that was used least recently. A "use" is either reading the key with get or writing it with put.
Implement the class LRUCache:
new LRUCache(capacity)creates an empty cache that can holdcapacityentries.get(key)returns the value stored forkey, or-1if the key is not in the cache. A successfulgetmakes the key the most recently used.put(key, value)stores the value. If the key already exists, its value is replaced and it becomes the most recently used. Otherwise the new entry is added, and if that would exceedcapacity, the least recently used entry is evicted first.
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
1 <= capacity <= 30000 <= key <= 10^4and0 <= value <= 10^5- At most
2 * 10^5calls in total.
Examples
Example 1
Input: ["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]Capacity 2. get(1) makes key 1 the most recent, so put(3) evicts key 2. Then put(4) evicts key 1, the oldest of {1, 3}.
Example 2
Input: ["LRUCache","put","put","get","put","put","get"]
[[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]
Output: [null,null,null,2,null,null,-1]Writing an existing key updates it and counts as a use, so it never grows past one entry. put(4) then evicts key 2.
Example 3
Input: ["LRUCache","put","get","put","get","get"]
[[1],[1,10],[1],[2,20],[1],[2]]
Output: [null,null,10,null,-1,20]With capacity 1 every new key evicts the previous one.
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 LRUCache {
/** @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 recently used key.
* @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.