Find the elements value if present in the cache.

Hard
0/120
Average time to solve is 35m
profile
Contributed by
5 upvotes
Asked in companies
alibabaTata1mg

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 3
1 4 1
2 2
2 4    
3 6
1 2 7
1 1 8
1 2 6
2 1
2 5
2 2
Sample Output 1:
-1 1
8 -1 6

Sample Output 1 Explanation:

Test case1:

Let’s say i’th operation takes place at t=i. Status after each operation is as follows.
1 4 1 - Element with 'U_ID' 4 and value 1 is inserted in the cache.
2 2 - No element with 'U_ID' 2 is present in the cache so -1 is returned.
2 4 - Element with 'U_ID' 4 is present in the cache so its value i.e 1 is returned.

Therefore the answer is -1 1.




Test case 2:

Let’s say i’th operation takes place at t=i. Status after each operation is as follows.
1 2 7 - Element with 'U_ID' 2 and value 7 is inserted in the cache.
1 1 8 - Element with 'U_ID' 1 and value 8 is inserted in the cache.
1 2 6 - Element with 'U_ID' 2 is already present in the cache so value is updated to 6.
2 1 - Element with 'U_ID' 1 is present in the cache so its value i.e 8 is returned. 
2 5 - No element with 'U_ID' 5 is present in cache so -1 is returned.
2 2 - Element with 'U_ID' 2 is present in cache so its value i.e 6 is returned.
Sample Input 2:
2
1 3 
1 1 1
1 3 91
2 1
4 6
1 1 7
1 3 1
1 2 6
2 2
1 2 1
2 2
Sample Output 2:
-1
6 1
Hint

Maintain a cache of size N.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N*M), where ‘N’ denotes the size of the cache and ‘M’ denotes the number of operations.

 

For each operation, we are iterating the cache of size ‘N’.

Space Complexity

O(N), where ‘N’ denotes the size of the cache.

 

We maintain a cache in the form of a list of size ‘N’.

Code Solution
(100% EXP penalty)
Find the elements value if present in the cache.
Full screen
Console