I was literally waiting for this video in continuation with the LRU cache. Awesome work, really appreciate the fact that you upload all these videos for free 💯
You're an awesome teacher man ❤️ I previously saw your LRU video then tried my best in LFU to come up with O(N) solution passing 23/25 tests. Now, O(1) solution looks so easy to implement after watching this.
So, unlike LRU cache, we need to also keep track of the frequency of each node inside each node, right? So we could access the right map when a particular node is accessed.
As soon as I saw your problem statement explanation where you drew the freq. table, it clicked me to use an ordered_map of dlls! Then, I implemented by myself... thank you so much!
After banging my head around the various codes available on the net, I am finally able to understand the concept. Although the addition of map containing freq as key and LRU cache as value is the only change, but I must say it was very difficult to understand.. Thanks for your effort
where are u maintaining the lfu element? bcoz if the 2nd freq list gets emptied to 3rd and after that, the 1st list gets emptied, then your freq value would be 2 but the 2nd list is empty
Yes, this would have been the case if we had a DELETE operation, but in the problem we only have add and get, so the condition you mentioned will never occur as an element is only removed if there is new one who wants to take its place. So, in your case the first list will only be emptied when the last element moves from list 1 to list 2, so the empty list 2 will get filled.
@@vinayakgandhi5690 yes you are correct,for example a,b are in 2nd now moved to third now freq = 3 a new element is added as c now frq=1 now it cannot be deleted ,in order to be deleted there should be new element who captures again 1st freq list
Isn't the time complexity of this procedure is *O(lg(n))* as to reach a list with *freq 'f'* in *freqlist* map is *lg(n)* . And also we need to store current frequency of a key in *keynode* map or we can use *unordered_map* for *keynode*
How to point the next frequency if let's say we evict all the nodes of the current lowest frequency. Do we want to sort the frequency from the map and get the min one ??
List* temp=ml[minfreq]; keynode.erase(temp->tail->prev->k); freqlist[minfreq]->removenode(temp->tail->prev); can anyone explain temp->tail how come temp access tail node ?
Hey striver, that's great explanation indeed. But I had a doubt. Can't we just use a unordered_map as a data structure over here. Because every time a new node is going to come at a certain position, it is going to land at the end of the queue and whenever there is a tie, the node which is at the front of queue, will get removed. Because unlike in LRU cache problem, if we are using an element again, its frequency got incremented over here. Though this approach might not work in O(1) as we have to remove the Node from queue every time. Just wanna know if this is correct approach or not.
From queue you can access only the front element right. What if the element which you wanted to access is located in middle of the queue?? That's why DLL come here handy. Queue interface limits you only to front element.
Video bina dekhe kyu bolte ho bro .. Bht difference hota h whiteboard and pad me, people easily understand in once, in pad, you cannot convey it that easily.. Ek bar video dekho, nai smjh aaye tab batana!!
@@takeUforward Na Na galat way mein naa lo bhaiya, I appreciate your hard work, aur maine kaafi videos dekhi hay ye first dekh raha hu aisa nhi hay bhaiya😅😅😅😅 Abhi graph series chalra aap wala❤️❤️
thanks bro for the awesome video, but one suggestion, please don't use your voice too harshly, it clearly shows how much effort you are putting out to speak single word, it can affect you in long term (voice issues) and it's not also soothing to listener ears as well TBH. Rather use mic, so your throat does not have to act like a loud speaker.
JavaScript Implementation // Least Frequently Used Memory Replacement algorithm // Has two methods // get(key) => Returns the value if found else -1 for a cache miss // In case of a cache hit, increment the frequency of the item // put(key, value) => Inserts the element to the cache if there is still room or Updates it if it already exists // If the cache is full, displace the Least Frequently Used Item in the cache // IMPLEMENTATION class Node{ constructor(key, value) { this.key = key; this.value = value; this.next = null; this.previous = null; this.frequency = 1; } } class DoublyLinkedList { constructor() { this.head = new Node(null, null); this.tail = new Node(null, null); this.head.next = this.tail; this.tail.previous = this.head; } removeNode(node){ let next = node.next; let previous = node.previous; previous.next = next; next.previous = previous; } insertHead(node){ node.previous = this.head; node.next = this.head.next; this.head.next.previous = node; this.head.next = node; } removeTail(){ let tail = this.tail.previous; this.removeNode(tail); // This is returned so as to use it to delete its value from the cache(nodeHash) return tail.key; } // Check if Dll is empty isEmpty(){ return this.head.next.value === null; } } class LFUCache { constructor(capacity) { this.capacity = capacity; // Key = Frequency, Value = Dll of items with the same frequency this.frequencyMap = new Map(); // Key = key, Value = Node(key, value) this.nodeHash = new Map(); this.currentSize = 0; this.leastFrequency = 1; } get(key){ // For a cache hit, return the value // Delete it from previous frequency doubly linked list frequency // If that Dll was with the leastFrequency and is now empty after deletion, increment the leastFrequency // Increment the frequency of that item // Insert the node to the Dll with the new frequency // For a cache miss return -1 let node = this.nodeHash.get(key); if(!node)return -1; // Delete it from Dll this.frequencyMap.get(node.frequency).removeNode(node); if(this.leastFrequency === node.frequency && this.frequencyMap.get(node.frequency).isEmpty()){ this.leastFrequency++; } node.frequency++; if(!this.frequencyMap.has(node.frequency)){ this.frequencyMap.set(node.frequency, new DoublyLinkedList()); } this.frequencyMap.get(node.frequency).insertHead(node); return node.value; } put(key, value){ // If the key exists, update the value of the node and increment the node frequency // If the new frequency does not exist in the frequency map, create it // Insert the node to the right Dll // Increment the leastFrequency if the previous Dll is now empty and it was the least frequency // Insert the item to the cache, if it previously did not exist // Check the size of the cache // If it is full, displace the LFU item from the cache(LRU in case of multiple items with leastFrequency) if(this.capacity === 0)return; let newNode = new Node(key, value); let node = this.nodeHash.get(key); if(node){ node.value = value; this.frequencyMap.get(node.frequency).removeNode(node); if(this.leastFrequency === node.frequency && this.frequencyMap.get(node.frequency).isEmpty()){ this.leastFrequency++; } node.frequency++; if(!this.frequencyMap.get(node.frequency)){ this.frequencyMap.set(node.frequency, new DoublyLinkedList()); } this.frequencyMap.get(node.frequency).insertHead(node); }else{ if(this.currentSize === this.capacity){ let removedKey = this.frequencyMap.get(this.leastFrequency).removeTail(); this.nodeHash.delete(removedKey); }else{ this.currentSize++; } if(!this.frequencyMap.has(1)){ this.frequencyMap.set(1, new DoublyLinkedList()); } this.frequencyMap.get(1).insertHead(newNode); this.nodeHash.set(key, newNode); this.leastFrequency = 1; } } }
Always remember we are storing linkedList in frequency map where each frequency has a list and Nodes having same frequency nodes , use this code with reduced variables and integration of LRU cache as much as possible, class LFUCache { int capacity; HashMap map; HashMap frequencymap; int minfreq; public LFUCache(int capacity) { map=new HashMap(); frequencymap=new HashMap(); this.capacity=capacity; minfreq=0; } public int get(int key) { if(map.containsKey(key)){ Node curr=map.get(key); updateNode(curr); return curr.value; }else{ return -1; }
}
public void put(int key, int value) { if(map.containsKey(key)){ Node curr=map.get(key); curr.value=value; updateNode(curr); }else{ if(map.size()==capacity){ DLL minList=frequencymap.get(minfreq); map.remove(minList.tail.prev.key); minList.deleteNode(minList.tail.prev); } minfreq=1; Node newone=new Node(key,value); DLL curList=frequencymap.getOrDefault(1,new DLL()); curList.addNode(newone); frequencymap.put(1,curList); map.put(key,newone); } } public void updateNode(Node curr){ int currFreq=curr.frequency; DLL curList=frequencymap.get(currFreq); curList.deleteNode(curr); if(minfreq==currFreq && curList.listsize==0){ minfreq++; } curr.frequency=currFreq+1; DLL newListorexisting=frequencymap.getOrDefault(curr.frequency,new DLL()); newListorexisting.addNode(curr); frequencymap.put(curr.frequency,newListorexisting); } class Node{ int key; int value; Node next; Node prev; int frequency; public Node(int _key,int _value){ this.key=_key; this.value=_value; this.frequency=1; } public Node(int _key,int _value,Node _next,Node _prev){ this.key=_key; this.value=_value; this.frequency=1; this.next=_next; this.prev=_prev; } } class DLL{ Node head=new Node(0,0); Node tail=new Node(0,0); int listsize; public DLL(){ head.next=tail; tail.prev=head; listsize=0; } public void addNode(Node curr){ Node temp=head.next; head.next=curr; curr.prev=head; curr.next=temp; temp.prev=curr; listsize++; } public void deleteNode(Node curr){ Node pehle=curr.prev; Node aage=curr.next; pehle.next=pehle.next.next; aage.prev=aage.prev.prev; listsize--; } } }
This is how i implemented with 3 hashmap and a list class LFUCache { //using 3 hashmaps, //1 normal hashmap for key and value //1 hashmap for key and count //1 hashmap for count and keys having the same count HashMapmap; HashMapcount; HashMapfreq; int min_freq=0; int cap=0; public LFUCache(int capacity) { this.cap=capacity; map=new HashMap(); count=new HashMap(); freq=new HashMap(); freq.put(1,new LinkedHashSet());
}
public int get(int key) { if(!map.containsKey(key)) return -1; int cnt=count.get(key); count.put(key,cnt+1);//we need to update the count of the key since it has been accessed freq.get(cnt).remove(key);//removing the element that is present in this count //for example freq,elements 2,3,4,5 had the frequency 1 //we need to increase the frequency of current key say 3 as it was accessed so its frequency(of accessability) must be increased //but first we need to remove it from frequency 1 list if(min_freq==cnt && freq.get(cnt).size()==0) min_freq++; //suppose 3 was the only element with freq 1,now that it has been accessed again its frequency(of accessibility) has increased to 2,no the list of elements having frequency 1 is empty,so we need to increase the min frequency if(!freq.containsKey(cnt+1)) freq.put(cnt+1,new LinkedHashSet()); freq.get(cnt+1).add(key); //adding the key to the new frequency set; return map.get(key);
}
public void put(int key, int value) { if(cap=cap){ //the map has reached its cap size //now we must delete an elemnt which has the min freq and is leas rrecently accesd //suppose the min freq is 1 //freq //here 3 is least recently accessed //so 3 must be delete,although 1,4,7 also have the same access frequency,but they are most recently accessed than 3 int element= freq.get(min_freq).iterator().next(); freq.get(min_freq).remove(element); map.remove(element); //we must also remove it from the map so that if it is tried to access it should return -1 } map.put(key,value); count.put(key,1); min_freq=1;//now the min will be 1 as this is a new element added whose frequency is of accessability is 1 freq.get(min_freq).add(key);
Question on Public demand :)
Instagram: Striver_79
@@RandomGuy-id7cl Id created on 4th july and same comment of my 40+ videos, kaam dhanda nai h ?
I am following your sheet 👍
Thank you❤️❤️
Bhaiya code implementation link is wrong,correct link is :
th-cam.com/video/mzqHlAW7jeE/w-d-xo.html
This is the best damned LRU/LFU video in the world. Crystal clear, quick, no fat/fluff/nonsense, straight to the point. Excellent!
Definitely 👍
Thanks!
I was literally waiting for this video in continuation with the LRU cache. Awesome work, really appreciate the fact that you upload all these videos for free 💯
brother have you completed your dsa journey ?? can i ask where are you working today and did dsa helped u ??
Striver, this is the best possible explanation in the entire world.
You're an awesome teacher man ❤️
I previously saw your LRU video then tried my best in LFU to come up with O(N) solution passing 23/25 tests. Now, O(1) solution looks so easy to implement after watching this.
Very clever implementation! How he handled all the LRU Cache method in freq map..... mind blown.
Please like this video even if you don't like the video because it took more than 5 hours for him to prepare this video for us. 🙏
brother have you completed your dsa journey ?? can i ask where are you working today and did dsa helped u ??
Cant thankyou enough for this ! I was struggling to understand this particular concept now its clear
So, unlike LRU cache, we need to also keep track of the frequency of each node inside each node, right? So we could access the right map when a particular node is accessed.
1 year back LRU cache was under HARD, now its medium
Bro you gained a subscriber. well done.. this ddnt make sense until I met this channel. Thank you
As soon as I saw your problem statement explanation where you drew the freq. table, it clicked me to use an ordered_map of dlls! Then, I implemented by myself... thank you so much!
After banging my head around the various codes available on the net, I am finally able to understand the concept. Although the addition of map containing freq as key and LRU cache as value is the only change, but I must say it was very difficult to understand.. Thanks for your effort
Thanks. As always you explained it very clearly. Helping others learn for free is really great gesture.
Love the energy with which you are explaining
Please complete the series!! string, DP and trees are most important!!
Understood....Thank You So Much for this wonderful video....🙏🙏🙏
This video is very good. I understood your explanation in one watch
Such an amazing explanation Striver. Hats off. Thankyou !
Explaination toh awesome hai hi ,but the promo at 2:28 is fantabulous
How do you search which frequency the LRU item belong to in O(1) time
did you get answer already ?
In the node itself you can store the frequency. So when you are accessing using get u can get frequency
where are u maintaining the lfu element? bcoz if the 2nd freq list gets emptied to 3rd and after that, the 1st list gets emptied, then your freq value would be 2 but the 2nd list is empty
Yes, this would have been the case if we had a DELETE operation, but in the problem we only have add and get, so the condition you mentioned will never occur as an element is only removed if there is new one who wants to take its place. So, in your case the first list will only be emptied when the last element moves from list 1 to list 2, so the empty list 2 will get filled.
@@vinayakgandhi5690 yes you are correct,for example a,b are in 2nd now moved to third now freq = 3 a new element is added as c now frq=1 now it cannot be deleted ,in order to be deleted there should be new element who captures again 1st freq list
woooaahhh i liked that small intro videoooo
Bhai tera koi tod nahi.❤❤❤❤
Isn't the time complexity of this procedure is *O(lg(n))* as to reach a list with *freq 'f'* in *freqlist* map is *lg(n)* . And also we need to store current frequency of a key in *keynode* map or we can use *unordered_map* for *keynode*
Really appreciate your hard work in explaining
How to point the next frequency if let's say we evict all the nodes of the current lowest frequency.
Do we want to sort the frequency from the map and get the min one ??
yeah I'm guessing we have to store the available frequencies in another doubly linked list where we will be able to delete in O(1) time
Whiteboard solutions are love
I will say the Most Frequently Used phrase here "thank you!"
This algorithm does not address how you would jump to the next min frequency once the list of keys in the current least frequency gets used up.
Code Implementation Video: www.youtube.com/watch?v=0PSB9... Update this.. this should bring to c++ video, but it references to the same vid
Oops, okay doing
@@takeUforward still not done
@@takeUforward Still not done.
Screw any interviewer who asks this question just to fail you
Love U Striver bhai ❤️
Thanks man!! u r a life saver!!
When you replaced 2,25 you did not tell how 2 was in the list of which frequency, can you update the lecture?
Awesome explanation 🤟
when we are inserting 5,50 there is already space available in freq 1 list, then also we will remove the 3,30?
Where can I find the code implementation video? The link in the description redirects to the same video unfortunately
Really good problem 😲🤠
thanks for the video. your link to the code implementation is pointing to this video itself. Please check
kaash maine ye pehle dekha hota, mera amazon ka final interview for sde1 me aaya tha
💀💀
List* temp=ml[minfreq];
keynode.erase(temp->tail->prev->k);
freqlist[minfreq]->removenode(temp->tail->prev);
can anyone explain temp->tail how come temp access tail node ?
Awesome sir 💯💯
yes it does exist!! yes it does exist!!
Great Explanation.
Hey striver, that's great explanation indeed. But I had a doubt.
Can't we just use a unordered_map as a data structure over here.
Because every time a new node is going to come at a certain position, it is going to land at the end of the queue and whenever there is a tie, the node which is at the front of queue, will get removed.
Because unlike in LRU cache problem, if we are using an element again, its frequency got incremented over here.
Though this approach might not work in O(1) as we have to remove the Node from queue every time.
Just wanna know if this is correct approach or not.
From queue you can access only the front element right. What if the element which you wanted to access is located in middle of the queue?? That's why DLL come here handy. Queue interface limits you only to front element.
@@VY-zt3ph Ya that's why it will become O(n) because we have to remove the element every time
@@NikhilGupta-zo5jh yes.
I think pad wala zyada better hota compare to board 😅😅😅
Video bina dekhe kyu bolte ho bro .. Bht difference hota h whiteboard and pad me, people easily understand in once, in pad, you cannot convey it that easily..
Ek bar video dekho, nai smjh aaye tab batana!!
@@takeUforward Na Na galat way mein naa lo bhaiya, I appreciate your hard work, aur maine kaafi videos dekhi hay ye first dekh raha hu aisa nhi hay bhaiya😅😅😅😅
Abhi graph series chalra aap wala❤️❤️
@@takeUforward yes sir board >>> pad... thank u for ur efforts
Striver please add videos of Heaps too if possible.
Thanks for this video.
What will be the time complexity?
thanku so much🤩
Good Imlementation
bhaiya, video name me implement ki spelling glt ho gyi hai..
thanks bro for the awesome video, but one suggestion, please don't use your voice too harshly, it clearly shows how much effort you are putting out to speak single word, it can affect you in long term (voice issues) and it's not also soothing to listener ears as well TBH. Rather use mic, so your throat does not have to act like a loud speaker.
Awesome brother
Thanks a lot brother
JavaScript Implementation
// Least Frequently Used Memory Replacement algorithm
// Has two methods
// get(key) => Returns the value if found else -1 for a cache miss
// In case of a cache hit, increment the frequency of the item
// put(key, value) => Inserts the element to the cache if there is still room or Updates it if it already exists
// If the cache is full, displace the Least Frequently Used Item in the cache
// IMPLEMENTATION
class Node{
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
this.previous = null;
this.frequency = 1;
}
}
class DoublyLinkedList {
constructor() {
this.head = new Node(null, null);
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.previous = this.head;
}
removeNode(node){
let next = node.next;
let previous = node.previous;
previous.next = next;
next.previous = previous;
}
insertHead(node){
node.previous = this.head;
node.next = this.head.next;
this.head.next.previous = node;
this.head.next = node;
}
removeTail(){
let tail = this.tail.previous;
this.removeNode(tail);
// This is returned so as to use it to delete its value from the cache(nodeHash)
return tail.key;
}
// Check if Dll is empty
isEmpty(){
return this.head.next.value === null;
}
}
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
// Key = Frequency, Value = Dll of items with the same frequency
this.frequencyMap = new Map();
// Key = key, Value = Node(key, value)
this.nodeHash = new Map();
this.currentSize = 0;
this.leastFrequency = 1;
}
get(key){
// For a cache hit, return the value
// Delete it from previous frequency doubly linked list frequency
// If that Dll was with the leastFrequency and is now empty after deletion, increment the leastFrequency
// Increment the frequency of that item
// Insert the node to the Dll with the new frequency
// For a cache miss return -1
let node = this.nodeHash.get(key);
if(!node)return -1;
// Delete it from Dll
this.frequencyMap.get(node.frequency).removeNode(node);
if(this.leastFrequency === node.frequency && this.frequencyMap.get(node.frequency).isEmpty()){
this.leastFrequency++;
}
node.frequency++;
if(!this.frequencyMap.has(node.frequency)){
this.frequencyMap.set(node.frequency, new DoublyLinkedList());
}
this.frequencyMap.get(node.frequency).insertHead(node);
return node.value;
}
put(key, value){
// If the key exists, update the value of the node and increment the node frequency
// If the new frequency does not exist in the frequency map, create it
// Insert the node to the right Dll
// Increment the leastFrequency if the previous Dll is now empty and it was the least frequency
// Insert the item to the cache, if it previously did not exist
// Check the size of the cache
// If it is full, displace the LFU item from the cache(LRU in case of multiple items with leastFrequency)
if(this.capacity === 0)return;
let newNode = new Node(key, value);
let node = this.nodeHash.get(key);
if(node){
node.value = value;
this.frequencyMap.get(node.frequency).removeNode(node);
if(this.leastFrequency === node.frequency && this.frequencyMap.get(node.frequency).isEmpty()){
this.leastFrequency++;
}
node.frequency++;
if(!this.frequencyMap.get(node.frequency)){
this.frequencyMap.set(node.frequency, new DoublyLinkedList());
}
this.frequencyMap.get(node.frequency).insertHead(node);
}else{
if(this.currentSize === this.capacity){
let removedKey = this.frequencyMap.get(this.leastFrequency).removeTail();
this.nodeHash.delete(removedKey);
}else{
this.currentSize++;
}
if(!this.frequencyMap.has(1)){
this.frequencyMap.set(1, new DoublyLinkedList());
}
this.frequencyMap.get(1).insertHead(newNode);
this.nodeHash.set(key, newNode);
this.leastFrequency = 1;
}
}
}
explanation is well and good but the time of write code that is very hard
why we are storing address, iska to kahin use bhi nhi ho rha
To direct access the value n then delete the node..
Always remember we are storing linkedList in frequency map where each frequency has a list and Nodes having same frequency nodes ,
use this code with reduced variables and integration of LRU cache as much as possible,
class LFUCache {
int capacity;
HashMap map;
HashMap frequencymap;
int minfreq;
public LFUCache(int capacity) {
map=new HashMap();
frequencymap=new HashMap();
this.capacity=capacity;
minfreq=0;
}
public int get(int key) {
if(map.containsKey(key)){
Node curr=map.get(key);
updateNode(curr);
return curr.value;
}else{
return -1;
}
}
public void put(int key, int value) {
if(map.containsKey(key)){
Node curr=map.get(key);
curr.value=value;
updateNode(curr);
}else{
if(map.size()==capacity){
DLL minList=frequencymap.get(minfreq);
map.remove(minList.tail.prev.key);
minList.deleteNode(minList.tail.prev);
}
minfreq=1;
Node newone=new Node(key,value);
DLL curList=frequencymap.getOrDefault(1,new DLL());
curList.addNode(newone);
frequencymap.put(1,curList);
map.put(key,newone);
}
}
public void updateNode(Node curr){
int currFreq=curr.frequency;
DLL curList=frequencymap.get(currFreq);
curList.deleteNode(curr);
if(minfreq==currFreq && curList.listsize==0){
minfreq++;
}
curr.frequency=currFreq+1;
DLL newListorexisting=frequencymap.getOrDefault(curr.frequency,new DLL());
newListorexisting.addNode(curr);
frequencymap.put(curr.frequency,newListorexisting);
}
class Node{
int key;
int value;
Node next;
Node prev;
int frequency;
public Node(int _key,int _value){
this.key=_key;
this.value=_value;
this.frequency=1;
}
public Node(int _key,int _value,Node _next,Node _prev){
this.key=_key;
this.value=_value;
this.frequency=1;
this.next=_next;
this.prev=_prev;
}
}
class DLL{
Node head=new Node(0,0);
Node tail=new Node(0,0);
int listsize;
public DLL(){
head.next=tail;
tail.prev=head;
listsize=0;
}
public void addNode(Node curr){
Node temp=head.next;
head.next=curr;
curr.prev=head;
curr.next=temp;
temp.prev=curr;
listsize++;
}
public void deleteNode(Node curr){
Node pehle=curr.prev;
Node aage=curr.next;
pehle.next=pehle.next.next;
aage.prev=aage.prev.prev;
listsize--;
}
}
}
You are good.
Great man! >
Superb
Bhaiya aapne Implement ki Spelling me ' p ' lagana bhul gaye Title me 😅
7:50
Understood!
Title Typo - "IMLEMENT"
code explanation with code video upload please
if LFU cache asked in interviews ?????
understood
God
understood!!
Understood
Awsome
Yo bro
Use the word element :P
end bro
❤❤
best
Title has been mispronounced as Imlement instead of Implement.
Haha
@@takeUforward 😂
First view🎉🎉
Ist
camera lens is not clear
This is how i implemented with 3 hashmap and a list
class LFUCache {
//using 3 hashmaps,
//1 normal hashmap for key and value
//1 hashmap for key and count
//1 hashmap for count and keys having the same count
HashMapmap;
HashMapcount;
HashMapfreq;
int min_freq=0;
int cap=0;
public LFUCache(int capacity) {
this.cap=capacity;
map=new HashMap();
count=new HashMap();
freq=new HashMap();
freq.put(1,new LinkedHashSet());
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
int cnt=count.get(key);
count.put(key,cnt+1);//we need to update the count of the key since it has been accessed
freq.get(cnt).remove(key);//removing the element that is present in this count
//for example freq,elements 2,3,4,5 had the frequency 1
//we need to increase the frequency of current key say 3 as it was accessed so its frequency(of accessability) must be increased
//but first we need to remove it from frequency 1 list
if(min_freq==cnt && freq.get(cnt).size()==0)
min_freq++;
//suppose 3 was the only element with freq 1,now that it has been accessed again its frequency(of accessibility) has increased to 2,no the list of elements having frequency 1 is empty,so we need to increase the min frequency
if(!freq.containsKey(cnt+1))
freq.put(cnt+1,new LinkedHashSet());
freq.get(cnt+1).add(key);
//adding the key to the new frequency set;
return map.get(key);
}
public void put(int key, int value) {
if(cap=cap){
//the map has reached its cap size
//now we must delete an elemnt which has the min freq and is leas rrecently accesd
//suppose the min freq is 1
//freq
//here 3 is least recently accessed
//so 3 must be delete,although 1,4,7 also have the same access frequency,but they are most recently accessed than 3
int element= freq.get(min_freq).iterator().next();
freq.get(min_freq).remove(element);
map.remove(element);
//we must also remove it from the map so that if it is tried to access it should return -1
}
map.put(key,value);
count.put(key,1);
min_freq=1;//now the min will be 1 as this is a new element added whose frequency is of accessability is 1
freq.get(min_freq).add(key);
}
}
Understood
understood
❤❤