913. Least Used Cache
A vending-machine operator keeps a fixed-size memo of capacity item codes together with their current prices. Build the class LeastUsedCache.
get(key)returns the value stored forkey, or -1 if absent. A successful read adds one to the key's use count.put(key, value)storesvalue. For an existing key it overwrites the value and adds one to its use count. A new key starts with use count 1; if that makes the memo larger thancapacity, first evict the key with the smallest use count. Among keys with the same smallest count, evict the one whose latest use is oldest.
A failed get changes nothing. Both operations must run in O(1) average time.
Example 1
- Input:
- operations = ["LeastUsedCache","put","put","get","put","get","get","put","get","get"]arguments = [[2],[5,50],[9,90],[5],[7,70],[9],[7],[2,20],[5],[2]]
- Output:
- [null,null,null,50,null,-1,70,null,-1,20]
- Explanation:
Key 5 has been used twice and 9 once, so adding 7 evicts 9. Then 5 and 7 are both used twice; 5 was used longer ago, so adding 2 evicts 5, and later reads give -1 for 5 and 20 for 2.
Example 2
- Input:
- operations = ["LeastUsedCache","put","put","get","get"]arguments = [[1],[3,30],[4,40],[3],[4]]
- Output:
- [null,null,null,-1,40]
- Explanation:
With room for one key, the second put evicts key 3 immediately, so only key 4 can be read.
Constraints
1 ≤ capacity ≤ 1000
0 ≤ key, value ≤ 106
At most 10000 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)