Problem: LRU Cache

Statement

Design a data structure that follows the constraints of a least recently used (LRU) cache.

Implement the LRUCache class with the following operations:

• LRUCache(int capacity): Initializes the LRU cache with a positive size capacity.

• int get(int key): Returns the value associated with key if it exists in the cache. Otherwise, returns $-1$.

• void put(int key, int value): Updates the value of key if it already exists in the cache. Otherwise, inserts the key\-value pair into the cache. If this insertion causes the number of keys to exceed capacity, the least recently used key must be evicted.

Note: Both get and put must operate in $O(1)$ average time complexity.

Constraints:

• $1 \leq$ capacity $\leq 3000$

• $0 \leq$ key ...