LFU Cache

Moderate
0/80
profile
Contributed by
34 upvotes
Asked in companies
SalesforceOLX GroupDisney + Hotstar

Problem statement

Design and implement a Least Frequently Used(LFU) Cache, to implement the following functions:

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’),  present in the cache, if it’s present otherwise return -1.
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.

You have been given ‘M’ operations which you need to perform in the cache. Your task is to 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 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 the 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.
Output Format: 
For each test case, print a vector/list that contains answers of all the operations of type 2 and in the order in 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. The 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

Try using the brute force approach.

Approaches (3)
Brute Force

In this approach, we will create 2 lists ‘cache’ and ‘nodes’, one for the keys current present in the cache and another list for the information about the key such as frequency, recency and value. Then for each query, we find the key in ‘cache’ and update the value if needed.

 

We will create a class Node(value, index, freq), where value is the value of the node, index int recency of the node, i.e., how recently it is used, and freq is the frequency of the Node.

 

Algorithm:

  • In the constructor(capacity) function:
    • Set capacity as ‘capacity,
    • Initialize an array ‘cache’ of ‘capacity’ size
    • Initialize an array of Nodes(0, 0, 0) of ‘capacity’ size called ‘nodes’
    • Set currSize as 0
    • Set position as 0
  • In the get(key) function:
    • Increase position by 1
    • Set value as -1
    • Iterate i from 0 to ‘capacity - 1’
      • If key is equal to cache[i]
        • Set value as nodes[i].value
        • Set nodes[i].index as position
        • Increase nodes[i].freq by 1
    • Return value
  • In the put(key, value) function
    • Increase position by 1
    • If capacity is 0 return
    • Iterate i from 0 to ‘capacity - 1’
      • If key is equal to cache[i]
        • Set nodes[i].value as value 
        • Set nodes[i].index as position
        • Increase nodes[i].freq by 1
        • Return from the function
    • If currSize is less than capacity
      • Set cache[currSize] as key
      • Set nodes[currSize]’s value, index and freq as value, position, 1 respectively
      • Increase currSize by 1
    • Otherwise,
      • Find the node in the nodes array with minimum ‘freq’ and if the frequency is equal get the one with the minimum position. Set it as pos.
      • Set cache[pos] as key
      • Set nodes[pos]’s value, index and freq as value, position, 1 respectively
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’.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
LFU Cache
Full screen
Console