LRU Cache Design Question

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

1. get(key) - Return the value of the key if it exists in the cache; otherwise, return -1.
2. put(key, value) - Insert the value in the cache if the key is not present or update the value if the key is already present. If the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

Input:

The first line of input contains two space-separated values 'C' and 'Q', representing the capacity of the cache and the number of operations, respectively.

The next 'Q' lines contain operations: 
 - Starts with an integer indicating the type of operation.
 - Type 0: Followed by a single integer key.
 - Type 1: Followed by two space-separated integers key and value.

Output:

For each type 0 operation, print the value if the key exists in the cache; otherwise, print -1.

Example:

Sample Input:

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:

3
-1
5
-1
3
3

Explanation:

With capacity 3, operations occur as follows:
- put(1,1)
- put(2,2)
- put(3,3)
- put(4,5) - Evicts key 1 as it's the least recently used.
- get(3) returns 3
- get(1) returns -1
- get(4) returns 5
- put(2,3) updates key 2
- get(1) returns -1
- get(3) returns 3
- get(2) returns 3

Constraints:

• 1 ≤ C ≤ 10^4
• 1 ≤ Q ≤ 10^5
• 1 ≤ key, value ≤ 10^9
• Time Limit: 1 sec