LFU Cache Design Problem

Design and implement a Least Frequently Used (LFU) Cache with the following functionalities:

1. put(U__ID, value): Insert the value in the cache if the key ('U__ID') is not already present, or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting the new item. 2. get(U__ID): Return the value of the key ('U__ID'), if present in the cache; otherwise, return -1. 

Note:

1) The frequency of use of an element is determined by the number of operations performed with its 'U__ID' after it is inserted into the cache. 2) If multiple elements have the least frequency, remove the element which was least recently used. 

Task:

You are given 'M' operations to perform in the cache. Implement all the functions of the LFU cache.

Type 1: for put(key, value) operation. Type 2: for get(key) operation. 

Example:

We perform the following operations on an empty cache with a capacity of 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, the value of 'U_ID' 2 is returned, i.e., 1. When operation 2 1 is performed, the value of 'U_ID' 1 is to be returned but it is not present in the cache, so -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 usage count of each element. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1 time operation of type 2). 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 space-separated integers ‘N’ and ‘M’, representing the size of the cache and the number of operations, respectively. The next ‘M’ lines contain operations that have to be performed on the cache. 

Output Format:

For each test case, print a vector/list containing the results of all the operations of type 2, in the order they were requested. 

Note:

1. All 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³
• 1 <= VAL <= 10⁶
• Time Limit: 1 sec