LRU Cache

Build a key-value cache with a fixed number of slots. When it is full and a new key arrives, it throws out the key that has gone unused for the longest time (the least recently used key).

Write the class LRUCache:

• LRUCache(capacity) creates an empty cache that holds at most capacity keys.
• get(key) returns the value stored for key, or -1 if key is not in the cache.
• put(key, value) stores value under key, replacing the old value if key is already there. If this adds a new key and the cache now holds more than capacity keys, remove the least recently used key.

A key counts as used when get finds it and when put stores it, whether that put adds it or updates it. A get that returns -1 uses nothing.

Both get and put must take O(1) time on average.

Each example lists the calls in order, then each call's arguments, then each call's result (null for the constructor and for put).

Example 1

Input:
["LRUCache", "put", "put", "get", "put", "get", "get", "get"]
[[2], [5, 50], [8, 80], [5], [3, 30], [8], [5], [3]]
Output: [null, null, null, 50, null, -1, 50, 30]

After get(5), key 8 is the one unused for longest, so put(3, 30) removes it and keeps 5.

Example 2

Input:
["LRUCache", "put", "put", "put", "put", "get", "get"]
[[2], [1, 10], [2, 20], [1, 15], [3, 30], [2], [1]]
Output: [null, null, null, null, null, -1, 15]

put(1, 15) updates key 1 and also counts as using it, so put(3, 30) removes key 2.

Example 3

Input:
["LRUCache", "get", "put", "get", "put", "get", "get"]
[[1], [7], [7, 0], [7], [9, 4], [7], [9]]
Output: [null, -1, null, 0, null, -1, 4]

A value of 0 is a real value, not a miss. With room for one key, adding 9 pushes 7 out.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10⁴
• 0 <= value <= 10⁵
• At most 2 * 10⁵ calls in total are made to get and put.