912. Recently Used Cache
A busy noodle stall keeps a small order board that remembers the price of at most capacity dishes, each identified by an integer dish code. Build the class RecentCache.
RecentCache(capacity)creates an empty board.get(key)returns the stored value ofkey, or -1 if it is not on the board. A successful read makeskeythe most recently used entry.put(key, value)stores or overwrites the value ofkeyand makes it the most recently used. If the board then holds more thancapacitykeys, remove the single least recently used key.
Reading and writing both count as a use. Every call must run in O(1) average time.
Example 1
- Input:
- operations = ["RecentCache","put","put","put","get","put","get","get"]arguments = [[3],[41,500],[17,250],[63,900],[41],[8,120],[17],[63]]
- Output:
- [null,null,null,null,500,null,-1,900]
- Explanation:
After three puts the board is full. Reading 41 makes it the most recent, so adding 8 removes 17, the least recently used entry; hence
get(17)is -1 while 63 is still stored with 900.
Example 2
- Input:
- operations = ["RecentCache","put","put","get","get"]arguments = [[2],[5,10],[5,99],[5],[6]]
- Output:
- [null,null,null,99,-1]
- Explanation:
Putting an existing key only replaces its value, so 5 reads back 99; key 6 was never stored and gives -1.
Constraints
1 ≤ capacity ≤ 3000
0 ≤ key, value ≤ 106
At most 20000 calls to get and put
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) per call
- Space
- O(capacity)