LRU Cache - Medium Python Design Interview Problem

Design a data structure that implements a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(capacity) - initializes the cache with a positive integer capacity.
get(key) - returns the value of key if it exists in the cache, otherwise returns -1. Accessing a key counts as a use.
put(key, value) - inserts or updates the key-value pair. If the cache has reached capacity, evict the least recently used key before inserting the new one.

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

Example

Input: ["LRUCache","put","put","get","put","get","get"]
       [[2],[1,1],[2,2],[1],[3,3],[2],[3]]
Output: [null,null,null,1,null,-1,3]
Explanation: After put(1,1) and put(2,2), get(1) returns 1 and makes key 1 most recent. put(3,3) evicts key 2 (LRU). get(2) returns -1.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls will be made to get and put.

Hints