Last Updated: 16 Dec, 2020

(Unused) LRU Cache Implementation

Moderate

Asked in company

Solve now

Problem statement

Design a data structure that follows the concept of LRU i.e. Least Recently Used Cache.

LRU Cache Class implementation :

You are given a capacity ‘C’ for LRUCache(int capacity) which basically initializes the LRU cache with positive size capacity.

Then you are given a ‘KEY’ for which the function int get(int key) returns the value of the key if the key exists, otherwise, return -1.

You are given two integers ‘KEY’ and ‘VALUE’ for which the function void put(int key, int value) updates the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Input format:

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains the ‘Q’ i.e. number of queries.

The first integer of each query defines the type of queries that can contain values ‘0’,’1’, or ‘2’.
If the value is ‘0’, it denotes that constructor ‘LRUCache’ is called.
If the value is ‘1’, it denotes that function ‘get’ is called.
If the value is ‘2’, it denotes that function ‘put’ is called.

Now,
If the query is ‘0’, then it follows by one integer, for the capacity size.
If the query is ‘1’, then it follows by one integer, for the key.
If the query is ‘0’, then it follows by two integers, for the key and value pair.

Each query is in a different line.

Output format:

For each test case, print the output array/list.

Note:

You do not need to print anything; it has already been taken care of.

Constraints :

1 <= T <= 50
1 <= N <= 10^4
0 <= QType[i] <= 2
1 <= QValues[i] <= 10^5

Where ‘T’ is the number of test cases.
'N' is the given capacity size of the LRU Cache.
‘QType’ is the given type of query.
‘QValues’ is the given query values.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

Let's try assuming that you never had to remove entries from the LRU cache because we had enough space, what would you use to support and get and put functions? A simple HashMap would be sufficient in that case.

Now, look at the second part which is where the eviction comes in, here we need a data structure which at any given instance can give us the least recently used objects in order.

Let’s see if we can maintain a linked list to do it.
We try to keep the list ordered by the order in which they are used.
So whenever a get operation happens, we would need to move that object from a certain position into the list to the front of the list. Which means a delete followed by the insert at the beginning.
Insert at the beginning of the list is trivial. How do we achieve the erase of the object from a random position in the least time possible? How about we maintain another HashMapthat stores the pointer to the corresponding linked list node.
Now when we know the node, we would need to know its previous and next node in the list to enable the deletion of the node from the list. We can get the next in the list from the next pointer? What about the previous node?
To encounter that, we make the list doubly-linked list.

Let’s see how the functions would work :

LRUCache(): It is nothing but a constructor that takes an integer ‘N’ and constructs LRUCache of capacity ‘N’.
get(key) :
Look for the value corresponding to the key in the HashMap.
If the key is not found, we don’t need to change accessList. So, return -1.
If a key is found, then we need to move the node corresponding to the key to the front of the list in the accessList.
set(key, value)
If the key is a new entry (it does not exist in the HashMap) and the cache is full(size = capacity), then we would need to remove the least recently used key.
We know that this key is the key corresponding to the last node in the accessList which is accessible in O(1).
Post this, there are 2 cases.
One is if the key is a new entry and is not present in the HashMap. In this case, a new node is created for the key and inserted at the head of the accessList. A new (key, value) entry is created into the HashMap.
Else if the key is already present in the map, in which case the value. needs to be updated. We update the value in the HashMapand then we update the accessList for the key exactly the way we did in the case of ‘get’ operation.

Solve now