Last Updated: 5 Mar, 2021
Find the elements value if present in the cache.
Hard
Asked in companies
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
Approaches
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’.
Declare a set that stores the frequency of times it was used and the last operation it was used and its ‘U_ID’. We will also maintain a set of ‘U_ID’ and their value.
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:-
- If the element is present in the cache we update its value then we also update the frequency of times it was used and the last operation when it was used.
- If the element is not present in the cache and we have an empty position in cache insert it in the set consisting of ‘U_ID’ and in the set consisting of the frequency of times it was used, last operation, and ‘U_ID’.
- If the element is not present in cache and cache is full delete element which is at the beginning of set storing frequency and last operation and ‘U_ID’ because it will be the element with least frequency and was least recently used among least frequently used elements and now insert the element in operation in the cache.
- If the operation is of type 2 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’.