LRU Cache Design Problem Statement

Design and implement a data structure for a Least Recently Used (LRU) cache that supports the following operations:

• get(key) - Retrieve the value associated with the specified key if it exists in the cache; otherwise, return -1.
• put(key, value) - Insert or update the value associated with the specified key. If the cache has reached its capacity, evict the least recently used item before inserting the new item.

Input:

The first line of input contains two space-separated integers 'C' and 'Q', representing the capacity of the cache and the number of operations to perform, respectively.
Each of the next 'Q' lines contains an operation. If the operation starts with 0, it implies a 'get' operation, followed by the key. If it starts with 1, it implies a 'put' operation, followed by the key and value.

Output:

For each 'get' operation (i.e., when the operation starts with 0), print the value associated with the key if it exists; otherwise, print -1.

Example:

Sample Input 1:

3 11
1 1 1
1 2 2
1 3 3
1 4 5
0 3
0 1
0 4
1 2 3
0 1
0 3
0 2

Sample Output 1:

3
-1
5
-1
3
3

Constraints:

• 1 <= C <= 10^4
• 1 <= Q <= 10^5
• 1 <= key, value <= 10^9
• Time Limit: 1 second

Note:

No printing is needed from your implementation; just implement the function as described.