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:

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

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

• public 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$ ...