LRU Cache

1. Get(int num): If the key exists, it will return the value of the key stored. Else, return -1. 2. Put(int key, int value): If the key already exists, update the value of the key. Else add the key-value pair to the cache. If the number of keys is more than the capacity for this operation, delete the least recently key used.

For the following input: 4 2 2 1 4 1 1 1 4 We will initialize an empty LRU cache for the first operation with a maximum capacity of 2. For the first operation, we need to add a key-value pair (1,4) to the cache. For the second operation, we need to return the value stored for key 1, i.e., 4 For the third operation, we need to return -1, as we don't have any key 4 in the cache. So, the final output will be: 4 -1

The first line of the input contains a single integer ‘T’ representing the no. of test cases. The first line of each test case contains two integers ‘N’ and ‘X’, denoting the no. of the operations. We need to initialize an empty LRU cache of the maximum capacity of ‘X’. The next ‘N’ lines of each test case contain either of the operations in the following format: - Get => two space-separated integers, 1 and ‘Y’ like '1 Y'. We need to return the value of the key ‘Y’ if it exists. Otherwise, Return -1. Put => three space-separated integers, 2, ‘A’ and ‘B’ like '2 A B'. If the key already exists, update the value of the key. Else add the key-value pair to the cache. If the number of keys is more than the capacity for this operation, delete the least recently key used.

For the first case: For the following input: 3 2 2 1 4 1 1 1 4 We will initialize an empty LRU cache for the first operation with a maximum capacity of 2. For the first operation, we need to add a key-value pair (1,4) to the cache. For the second operation, we need to return the value stored for key 1, i.e., 4 For the third operation, we need to return -1, as we don't have any key 4 in the cache. So, the final output will be: 4 -1 For the second case: For the following input: 5 1 2 1 4 2 2 6 1 1 1 2 We will initialize an empty LRU cache for the first operation with a maximum capacity of 1. For the first operation, we need to add a key-value pair (1,4) to the cache. For the second operation, we need to add a key-value pair (2,6) to the cache and remove (1,4) from the cache. For the third operation, we need to return -1, as we don't have any key 1 in the cache. For the fourth operation, we need to return the value stored for key 2, i.e., 6 So, the final output will be: -1 6

Hashmap + Linked list

We have to keep track of the keys, so we can use a doubly linked list and an unordered hashmap to achieve this.

If we use an array, we can perform an update operation in O(1), but adding and removing keys take O(N).

If we use a linked list, we can add and remove keys in O(1), but the update operations take O(N).

So, a combination of a doubly linked list and an unordered hash map can achieve both operations in O(1).

We can create a double-linked list with the help of the given key, value, and two-pointers keeping track of the head and tail. We create an unordered hashmap and put the pointer to the node with the key in the hash map.

For a Put operation:-

If the key is present in the map
1. Remove the node from the doubly linked list and the map.
If the length of the doubly linked list is equal to the capacity of the cache
1. Remove the last node from the doubly linked list and remove the corresponding entry from the hash map.
Add a new node at the start of the doubly linked list.
Update/Add the address of the node in the hashmap.

For a Get operation:-

If the key is present in the map
1. Get the node's address from the hashmap and return the node's value from the doubly linked list.
Else
1. Return -1.

Algorithm:

LRUCache(capacity)

Function arguments - The maximum capacity of the cache.

Initialize an empty doubly linked list of ‘Node’, to contain the key-value pair, with a head and a tail pointer.
Initialize the unordered hashmap ‘map’, to store the address of the nodes of the doubly linked list.

get(key)

Function arguments - The key to getting the value associated with it.

If the hashmap has an entry corresponding to the key
- curNode=map[key]
- result=curNode->value
- map.erase(key)
- deleteNode(curNode)
- addNode(curNode)
- map[key]=head->next
- Return result.
Else return -1.

put(key,value)

Function arguments - The key and value we want to store in the cache.

If the hashmap has an entry corresponding to the key
- *curNode=map[key]
- map.erase(key)
- deleteNode(curNode)
If the size of the map equals the capacity of the cache
- map.erase(tail->prev->key)
- deleteNode(tail->prev)
Add(new Node(key,value))
map[key]=head->next

addNode(*curNode)

curNode->next=head->next
curNode->prev=head
curNode->next->prev=curNode
head->next=curNode

deleteNode(*curNode)

prevNode=curNode->prev
nextNode=curNode->next
prevNode->next=nextNode
nextNode->prev=prevNode

Time Complexity

O( N ), Where ‘N’ is the number of operations performed.

We are performing all the operations in O(1) and the total number of operations is N.

Hence the time complexity is O( N ).

Space Complexity

O( X ), Where ‘X’ is the maximum number of nodes in the linked list.

We are using a doubly linked list to store the key-value pairs and a hashmap to store the address of the nodes of the doubly linked list.

Hence space complexity is O( X ).

Problem statement

Sample Input 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :