JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

SQP10 Implementation LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure. int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1. void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:
Input:["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation:

// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3
                    

Constraints:
- 1 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 * 10^5 calls will be made to get and put.

Notes

Note: Zoom for Better Understanding

Approch

Basically we Degine the Data Structure that follow the Properties of the LFU Lest Frequenty used in this problem we have a tuple of the finction

get()

put()

get function return the value of the particular key, if the key is not present into the ds retuirn -1 get(key)

put function used for the we gives the key and value and we put into the cache data structure put(key,val)

if the capacity of the data structure is filled then removed LFU guy

remove the least frequent used guy and then we will Insert the our New pair

The Main Task is Degine the algorithm with Space Complexcity O(1) but function work in the Constant Time.

Check the Exapmple in the Notes.

How Algorithm Works

• get(key):
    ○ If key is not present in cache, return -1
    ○ Get the node from the cache
    ○ Update the node frequency
    ○ Remove the node from the DLL of node's previous frequency
    ○ Add the node to the DLL with the node's updated frequency
    ○ Update min frequency value
                
• put(key, value):
    ○ If key is present in cache
        - Similar logic to that of get function
        - Only difference being that we need to update the value here
    ○ If key not present in cache
        - If the cache has already reached it's capacity, delete the tail 
           node from the DLL with least frequency
        - Create the new node with the (key, value) pair passed as arguments
        - Add the node to the frequency table with frequency key = 1
        - Add the node to the cache
        - Update min frequency to be 1
                  

                  

Code Zone!

Before Loking the Code...
Try by Your Self ...