LRU Cache

Design a least recently used (LRU) cache with a fixed capacity:

• LRUCache(capacity) creates an empty cache.
• get(key) returns the key's value, or -1 if it's missing. A successful get counts as a use.
• put(key, value) inserts or updates the key (also a use). If that pushes the size above capacity, evict the key that was used least recently.

Both operations must run in O(1) average time.

Example 1

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

get(1) makes key 1 recent, so put(3) evicts 2. Then put(4) evicts 1.

Example 2

Input:
["LRUCache","put","put","get"]
[[1],[7,1],[7,2],[7]]
Output:
[null,null,null,2]

Updating an existing key doesn't evict anything.

Constraints

• 1 ≤ capacity ≤ 5000
• 0 ≤ key ≤ 10⁴, 0 ≤ value ≤ 10⁵
• At most 4 · 10⁴ calls to get and put