Find the elements value if present in the cache.

Posted: 5 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

There is a cache that can hold up to ‘N’ elements. Initially, it is empty. There are two types of operations:-

Operation 1: [ 1 ‘U_ID’ ‘VAL’ ] - where 1 represents an insert/update operation is being performed in the cache.

If the element with a particular ‘U_ID’ already exists in cache:
 - Update its mapped value with ‘VAL’. 

If it does not exist and the cache is not full then 
 - Simply insert this element. 

If it does not exist and the cache is already full then 
 - We remove an element and insert this element into the cache. The element to be removed is selected as the least frequently used element.
Note:
  1) The frequency of use of an element is calculated by a number of operations with its ‘U_ID’ performed after it is inserted in the cache.

  2) If multiple elements have the least frequency then we remove the element which was least recently used. 

Operation 2: [ 2 'UID' ] - where 2 represents, mapped value of this 'UID'

If present in cache otherwise return -1.

You have been given ‘M’ operations which you need to perform in the cache. Your task is to return a vector/list that contains the answer of all the operations of type 2 and in the order in which they were asked.

Example:
We perform the following operations on an empty cache which has capacity 2:

When operation 1 2 3 is performed, the element with 'U_ID' 2 and value 3 is inserted in the cache.

When operation 1 2 1 is performed, the element with 'U_ID' 2’s value is updated to 1.  

When operation 2 2 is performed then value of 'U_ID' 2 is returned i.e. 1.

When operation 2 1 is performed then the value of 'U_ID' 1 is to be returned but it is not present in cache therefore -1 is returned.

When operation 1 1 5 is performed, the element with 'U_ID' 1 and value 5 is inserted in the cache. 

When operation 1 6 4 is performed, the cache is full so we need to delete an element.First, we check the number of times each element is used. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1-time operation of type 1). Element with 'U_ID' 1 is used 1 time (1-time operation of type 1). So element with 'U_ID' 1 is deleted. The element with 'U_ID' 6 and value 4 is inserted in the cache. 
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two single space-se[arated integers ‘N’ and ‘M’ representing the size of cache and number of operations respectively.

Next ‘M’ lines contain operations that have to be performed on the cache. Each operation is either of type 1 or 2.
Output Format:
For each test case, return a vector/list that contains answers of all the operations of type 2 and in the order which they were asked.
Note:
1. All the operations are valid. 
2. You do not need to print anything; it has already been taken care of. Just implement the function. 
Constraints:
1 <= T <= 10
1 <= N <= 1000
1 <= M <= 1000
1 <= U_ID <= 10^3
1 <= VAL<= 10^6

Time Limit: 1sec
Approach 1

We can maintain a list of cache initialized with -1 which represents all the cells in the cache are empty. Declare a list that stores value at ith position, frequency of times it was used, and last operation it was used. 

Declare a list ‘ANS’ that stores answer for all queries of type 2. We perform each operation as follows:-

 

  • If the operation is of type 1 then iterate cache and check if the element with that 'U_ID' is present. If present, just update its value with the value given in the query, increase the frequency of times used by 1, and the last operation it was used to ‘i’. If it is not present and there is at least one position empty i.e with value -1 update that position with the following 'U_ID' and value mentioned in the query, initialize frequency of times used to 1 and last operation when it was used to i. If no position is empty find the position which is used the least number of times, if there are multiple positions find the position which was least recently used and delete that element from the cache and insert the element in the above operation.
  • If the operation is of type 2 iterate through the cache and check if an element with a particular 'U_ID' mentioned in operation is present in cache:-
    • If present, push its updated value from the cache in ‘ANS’.
    • Otherwise, push -1 in the list ‘ANS’.
  • After performing all the operations return ‘ANS’.
Try Problem