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

Question

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:

Sample Output 1:

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.

Accepted Answer

The question is about designing and implementing a data structure for LRU cache to support get and put operations.

LRU cache is a cache replacement policy that removes the least recently used item when the cache reaches its capacity.
The cache is initialized with a capacity and supports get(key) and put(key, value) operations.
For each get operation, return the value of the key if it exists in the cache, otherwise return -1.
For each put operation, insert the value in the cache if the key is not already present or update the value of the given key if it is already present.
When the cache reaches its capacity, invalidate the least recently used item before inserting the new item.
The access to an item or key is defined as a get or a put operation on the key.
The least recently used key is the one with the oldest access time.
The input consists of the capacity of the cache and the number of operations to be performed.
Each operation is of type 0 (get) or type 1 (put) and is followed by the necessary parameters.
For each get operation, print the value of the key if it exists, otherwise print -1.