Linked Lists A list and a map together
311. LRU Cache
Design a cache that holds at most capacity keys, each with a value. When the cache is full and a new key
comes in, the cache makes room by evicting the key that was used least recently. Write a class LRUCache
with a constructor and two methods:
LRUCache(capacity)creates an empty cache that can holdcapacitykeys.get(key)returns the value stored forkey, or-1ifkeyis not in the cache.put(key, value)storesvalueforkey. Ifkeyis already in the cache, its old value is replaced. Otherwisekeyis added, and if the cache already holdscapacitykeys, the least recently used key is evicted first.
A key is used each time put stores it and each time get finds it. The least recently used key is the
one whose last use is furthest in the past. get and put must each run in O(1) time on average.
Your class is tested by replaying a list of calls on a new LRUCache(capacity). ops[i] names the
i-th call, "get" or "put", and keys[i] is the key it is called with. The puts take their values from
values in order, so the first put stores values[0], the second stores values[1], and so on. The answer
is the list of every value that get returns, in the order of the calls.
In C# and Go the methods are Get and Put. Go creates the cache with Constructor(capacity), and Rust
with LRUCache::new(capacity). The names in ops are the same in every language.
Example 1
Input: capacity = 3
ops = ["put",
"put",
"put",
"get",
"put",
"get",
"get",
"put",
"get",
"get"]
keys = [5, 8, 2, 5, 9, 8, 2, 7, 5, 9]
values = [50, 80, 20, 90, 70]
[50,-1,20,-1,90]Explanation: After three puts the cache is full. get(5) uses key 5, so key 8 is now the least recently used, and
put(9, 90) evicts it. get(2) then uses key 2, which leaves key 5 the least recent, so put(7, 70)
evicts key 5.
Example 2
Input: capacity = 2
ops = ["put",
"put",
"put",
"put",
"get",
"get",
"get"]
keys = [1, 2, 1, 3, 1, 2, 3]
values = [100, 200, 111, 300]
[111,-1,300]Explanation: The third put stores 111 for key 1, which is already in the cache. That replaces the old value and makes
key 1 the most recent, so put(3, 300) evicts key 2.
Example 3
Input: capacity = 1
ops = ["get",
"put",
"get",
"put",
"get",
"get"]
keys = [0, 0, 0, 1000000000, 0, 1000000000]
values = [0, 1000000000]
[-1,0,-1,1000000000]Explanation: The first get finds an empty cache. Key 0 then stores the value 0, which is a real value, not a miss.
With room for one key, put(1000000000, 1000000000) evicts key 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ capacity ≤ 1051 ≤ ops.length ≤ 2 × 105- Each
ops[i]is"get"or"put". keys.lengthequalsops.length.values.lengthequals the number of"put"calls inops.0 ≤ keys[i] ≤ 1090 ≤ values[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.