Make sure to change the code a little bit void put(int key_, int value) { if(m.find(key_) != m.end()) { node* existingnode = m[key_]; m.erase(key_); deletenode(existingnode); } if(m.size() == cap) { m.erase(tail->prev->key); deletenode(tail->prev); } Suppose , you're commenting the m.erase line , in that case make sure that the if statement below , where we're checking if the size of map is equal to cap , is changed as follows : ELSE IF (m.size() == cap) { m.erase(tail->prev->key); deletenode(tail->prev); } See , that I've changed the if to else if. WHY ? See , since we're not deleting the key-val pair from the map , the map might be full , and if the earlier code is written , the control flow would check if the map is full and thus would delete the LEAST RECENTLY USED NODE , causing us trouble. Thus , the ELSE IF.
@@takeUforward No No, it is not an extra step, it is absolutely correct. If you remove it the map.size()==capacity condition will hit and this messes up the answer as a node will be deleted unintentionally (According to the java code shown). I have checked this.
Striver Sir, Knowledge Gate's lectures are no more free, the playlist on TH-cam has private videos, I request to please tell the alternative for learning OS DBMS CN for SDE interview. Should I go for GFG's CS Fundamentals? Thank You.
@@freshcontent3729 Looks like you didn't understood the core concept. In queue, how will you get the address of data required in O(1). get() function will become a mess as first you will need to search data, delete it, shift all remaining data*, reinsert data O(N). put() method won't be easy as well, we want something like last in access to be O(1) while as we will have queue, it will be O(N) -> as we are using queue(FIFO). Due to these intracacies we are not using queue. Obviously you can use queue if asked by interviewer for fun :)
Khatarnaak bhaishab, Maja aa gaya, Dono video dekh kr LRU cache ke. The first algorithm was explained & in this code walkthrough is explained extremely well ❤️🩹
when we have to make the node as recent used node we have to search that particular node from linked list and have to delete it and again have to add it......so if we will not add that particular node in map we have to traverse whole linked list for that.
@@purellajajisaipavankumar651 we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
Your often talk about engineering students or iit, nit, nsit, iiit students plz talk about and make Roadmap for bsc msc computer science non engineering students
Can somebody please clear my doubt? The deletenode call inside get method is only breaking the link for resnode, and we are assigning the same node after head in addnode call, so why are we updating the corresponding address in the map? I think there is no neee to write m[key_] = head->next;
that's what I was thinking. We are not actually deleting nodes. We are just severing links between the node to be deleted from its adjacent nodes. However in add node we are actually creating new node with the same key and new value. A new node will have new address , so needs to be updated in the map. Also, when putting a node in the cache (key of which already exists in map) , we could just have changed the links to move it next to head. However when putting a node with new key , we are required to create a new node. In that case we would have to define 2 different functions:- 1. for putting already present keys (just change the links, don't create new node) 2. for putting new keys (new node is required to be made) So, to avoid making seperate functions for them , striver just did that using a single function for both cases where he always deletes the old node(if exists in map) and create a new node and add it after head.
Use list in C++ stl as it will reduce code and make it more easier to understand and will also lead to cleaner code class LRUCache { list l; unordered_map m;//to check in O(1) and int size; public:
LRUCache(int capacity) { size=capacity; } int get(int key) { if(m.find(key)==m.end()) return -1; l.splice(l.begin(),l,m[key]); return m[key]->second; } void put(int key, int value) { if(m.find(key)!=m.end()) { //splice moves the node poninting by iterator at 3 to iterator before first argument in list l which is 2nd element l.splice(l.begin(),l,m[key]); m[key]->second=value; return; } if(l.size()==size) { auto d_key=l.back().first; l.pop_back(); m.erase(d_key); } l.push_front({key,value}); m[key]=l.begin(); } };
Do we have implementation of hashmap or unordered map in C++? I tried searching other content on your channel but not able to find one. Can any one please provide the link for implentation of hashmap or unordered map in C++?
head->next = tail; tail->prev = head; Why is this written inside LRUCache(){} ? It shows error when written right after head and tail are both initialized. Why? Please explain someone🙏
Striver, you are amazing. I cannot really wrap my mind around the fact that at such young age(so young that he is calling the nodes as "guy" signifies the fact that his vocab is very limited) he has gained so much skills.
Bro put method implementation is wrong here, it should be else if(cap == mp. size()), as when someone updates a key that already exists there in the map and the size is full then in that case we don't need to remove the least recently used node as we are to inserting any new node we are just updating existing node there
@@pranavsharma7479 it happened with me...i know unordered map has avg complexity of 1 and map has logn but still they must have made test cases so that worstcase of unordered map was applicable. Anyways, my code was giving tle on last few TCs with unordered map but ran successfully with map
Bhaiya can you help me to solve this problem or any suggestion (how to make a plugin for upload a csv file in wordpress and display each line in dashboard ?)
@@freshcontent3729 I think the main advantage of using DLL was the ease with which he was able to reorder the recently used item with O(1) time. I dont think you will be able to do that in O(1) with queues. Not completely sure though.
Bhai this solution in leetcode shows the following:- Runtime: 436 ms, faster than 12.57% of C++ online submissions for LRU Cache. Memory Usage: 178.6 MB, less than 5.02% of C++ online submissions for LRU Cache. Is there a better way to solve this question or is this sufficient enough?
I don't think there's any need of changing the address of key in get method coz we are assigning the same node to head->next. correct me if i am wrong.
Sorry to say but it is a wrong and very inefficient implementation. Reasons highlighted: 1) No relation between hashmap and linked list. What is the point of keeping Linked list? 2) In case of successful get operation, entry from hashmap and linklist is deleted and added. Honestly, successful get operation should not change hashmap. 3) Put operation should come into place when get operation is unsuccessful. Because if cache is miss then data should be readback from datastore/backend/disk/device and then populate the hashmap using put operation. 4) Find operation of hashmap should be close to O(1), which will not be the case here if more than one get operation is successful for a given key because hashmap is modified. 5) Periodic timer thread should be there to check if cache/hashmap is near to full then free up the entries in the background, otherwise if the cache is full then last cache hit/get operation will always be slow. Thanks!
If you are coming from watching the previous video explanation, do comment
bhaiya one question, did you delete ur video " stack using 2 queues?" if you did then why so ?
@@freshcontent3729 playlist ke h toh.. check kro, galat upload hua tha, th replace kie.
@@takeUforward check kiya it showes privated in playlist
th-cam.com/video/jDZQKzEtbYQ/w-d-xo.html
Isime dono hai..
Coming from the previous video bhaiya 💥💥💥💥
We can free memory by delete or free operation on the LRU node which is to be deleted when put is performed when cache size is exceeded.
Yes, otherwise there is no need to erase the map element....because the node remains the same.
Couldn't get a better explanation than this. Thanks bhaiya.
You are doing a great job helping us.
Expecting more such explanatory videos
what will be the space compleixty of stirivers code ?
Can you make a series for dp????
You as a teacher is really awesome, can connect with you.
Follow Aditya Verma's DP playlist. He is considered as God of DP !
@@AbhishekVerma-yw1ps any playlist for backtracking
UNDERSTOOD......Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Is it necessary to erase key from map which is already present? I think that will automatically be overwritten when we assign new value to the key
Yes no need, i did an extra step there
Same doubt 😂
Make sure to change the code a little bit
void put(int key_, int value) {
if(m.find(key_) != m.end()) {
node* existingnode = m[key_];
m.erase(key_);
deletenode(existingnode);
}
if(m.size() == cap) {
m.erase(tail->prev->key);
deletenode(tail->prev);
}
Suppose , you're commenting the m.erase line , in that case make sure that the if statement below , where we're checking if the size of map is equal to cap , is changed as follows :
ELSE IF (m.size() == cap) {
m.erase(tail->prev->key);
deletenode(tail->prev);
}
See , that I've changed the if to else if.
WHY ?
See , since we're not deleting the key-val pair from the map , the map might be full , and if the earlier code is written , the control flow would check if the map is full and thus would delete the LEAST RECENTLY USED NODE , causing us trouble.
Thus , the ELSE IF.
@@takeUforward No No, it is not an extra step, it is absolutely correct. If you remove it the map.size()==capacity condition will hit and this messes up the answer as a node will be deleted unintentionally (According to the java code shown). I have checked this.
Aditya bhai, isse acha explanation and code kahi aur nahi mila, Thanks!!!
Couldn't get a better explanation than this.
what will be the space compleixty of stirivers code ?
Hats off for that simple Java code!!
Thank you so much! Your explanations are always top notch!
Great teaching, you makes everything clear, without diving into code.
one suggestion : you should free up space of node which is deleted in dll.
in java , we need not do that , jvm's garbage collector will take care of it. in c++ yes we should dealloc
Striver Sir, Knowledge Gate's lectures are no more free, the playlist on TH-cam has private videos, I request to please tell the alternative for learning OS DBMS CN for SDE interview. Should I go for GFG's CS Fundamentals?
Thank You.
I have made a video on this on the other channel..
DUDEEE!
It got accepted, and the explanation is sooo simple too.
I didn't think I'll wait for this question this long. Gr8 explanation 🔥🔥
we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
@@freshcontent3729 Queue's Delete operation would not be in O(1)
@@freshcontent3729 Looks like you didn't understood the core concept. In queue, how will you get the address of data required in O(1).
get() function will become a mess as first you will need to search data, delete it, shift all remaining data*, reinsert data O(N). put() method won't be easy as well, we want something like last in access to be O(1) while as we will have queue, it will be O(N) -> as we are using queue(FIFO).
Due to these intracacies we are not using queue. Obviously you can use queue if asked by interviewer for fun :)
@@freshcontent3729 moving node will be of O(1) tc where as in queue it will be O(N)
Awesome explanation!!
Thank you for your efforts 💝
Literally GBU for such exceptional rich content!
So What if this video is old , Love Your Content Bhaiya , Jaruri thori na sirf dp series mai commment kru Jo Jo acha lage Usme comment krunga
best tutorial on this question!!!!
Can we take priority queue of linked list to solve this ?
Why not use list STL instead of implementing doubly linked list by yourself?
Interviews!
You have a course on GFG ? Can you provide details or the link?
Khatarnaak bhaishab, Maja aa gaya, Dono video dekh kr LRU cache ke. The first algorithm was explained & in this code walkthrough is explained extremely well ❤️🩹
Great explanation! instead of m.find(key)!=m,end( ) .. we can use m[key]!=NULL;
that didn't work...on leetcode
In your SDE sheet, why is this llisted under Stacks and Queues even though stack or
queue is not used here..?
same doubt
Beautiful explanation. Thanks a lot!!!!!!!!!
java code at 07:40
What is the point of keeping key and value, both in the node???
Thank you so much striver!
very well explained thank you
7:42 for java explanation
Why are we storing key in the linkedlist node ? only storing value will be enough right as we have key in hashmap. Is there any significance of it ?
we are accessing the element(if present) from the LinkedList
when we have to make the node as recent used node we have to search that particular node from linked list and have to delete it and again have to add it......so if we will not add that particular node in map we have to traverse whole linked list for that.
@@purellajajisaipavankumar651 we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
@@freshcontent3729 Accessing and deleting and inserting is easy in dll compared to queue or a linked lisr
Your often talk about engineering students or iit, nit, nsit, iiit students plz talk about and make Roadmap for bsc msc computer science non engineering students
7:39 java solution
Thank you so much!!!😊
striver bhai kabhi ruknna mat keep foreward amazing explanation bhai😘
Can somebody please clear my doubt?
The deletenode call inside get method is only breaking the link for resnode, and we are assigning the same node after head in addnode call, so why are we updating the corresponding address in the map?
I think there is no neee to write
m[key_] = head->next;
right no need to write m[key_] = head->next as well as mp.erase(key) in get method
that's what I was thinking. We are not actually deleting nodes. We are just severing links between the node to be deleted from its adjacent nodes. However in add node we are actually creating new node with the same key and new value. A new node will have new address , so needs to be updated in the map.
Also, when putting a node in the cache (key of which already exists in map) , we could just have changed the links to move it next to head. However when putting a node with new key , we are required to create a new node. In that case we would have to define 2 different functions:-
1. for putting already present keys (just change the links, don't create new node)
2. for putting new keys (new node is required to be made)
So, to avoid making seperate functions for them , striver just did that using a single function for both cases where he always deletes the old node(if exists in map) and create a new node and add it after head.
Use list in C++ stl as it will reduce code and make it more easier to understand and will also lead to cleaner code
class LRUCache
{
list l;
unordered_map m;//to check in O(1) and
int size;
public:
LRUCache(int capacity)
{
size=capacity;
}
int get(int key)
{
if(m.find(key)==m.end())
return -1;
l.splice(l.begin(),l,m[key]);
return m[key]->second;
}
void put(int key, int value)
{
if(m.find(key)!=m.end())
{
//splice moves the node poninting by iterator at 3 to iterator before first argument in list l which is 2nd element
l.splice(l.begin(),l,m[key]);
m[key]->second=value;
return;
}
if(l.size()==size)
{
auto d_key=l.back().first;
l.pop_back();
m.erase(d_key);
}
l.push_front({key,value});
m[key]=l.begin();
}
};
hey thanks for suggestion ,it would have been more helpful if it was more of a detailed explanation
bro nice implementation , but splice function has linear time complexity
Amazing Explanation, thank you
what will be the space compleixty of stirivers code ?
Thank you so much
Do we have implementation of hashmap or unordered map in C++?
I tried searching other content on your channel but not able to find one.
Can any one please provide the link for implentation of hashmap or unordered map in C++?
Thanks for great explanation!!
why are we deleting when we need to move a node to the front?
Not only LRU Cache, I revised linked list and doubly linked list from this video
what will be the space compleixty of stirivers code ?
@@freshcontent3729 O(2N) where n is number of keys throughout the question.
Great explanation
much needed video bhaiya thank you very much :)
Thankyou sir🙏🙇♂❤
Amazing explanation 👍🏻
head->next = tail;
tail->prev = head;
Why is this written inside LRUCache(){} ?
It shows error when written right after head and tail are both initialized. Why?
Please explain someone🙏
Awesome videos man. Loved it.
Understood
Gives TLE on leetcode even after using map instead of unordered map
In 0:51 LRUCache is a constructor for the class right?
Yes
😍 raj bhaiya raat 3 baje comments me doubts solve kar rahe hai 🔥🙏 can't thank you enough for the effort.
Paid courses me itna support nahi milta ❤️
@@ritankarsarkar9394 haha, koi doubt puche th bata dena chye agar aata ho, mera hardly 5 sec jaega.
Big fan sir 🙇
JUST AMAZING
hey striver bhai key_ ye kyu use kia h har jagah we can use simple key as well .
I thing my code is better than strivers's code in terms of code-readability :
class Node {
public:
Node *next;
Node *prev;
int key;
int val;
Node(int key, int val)
{
this->key = key;
this->val = val;
prev = next = NULL;
}
};
class LRUCache {
public:
int capacity;
unordered_maph;
Node *head, *tail;
LRUCache(int capacity) {
this->capacity = capacity;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (h.find(key) != h.end())
{
int value = h[key]->val;
Node *temp = h[key];
h.erase(key);
removeNode(temp);
insertNode(key, value);
return value;
}
return -1;
}
void removeNode(Node *temp)
{
Node *curr = temp->next;
Node *prev = temp->prev;
prev->next = curr;
curr->prev = prev;
}
void insertNode(int key, int value)
{
Node *curr = new Node(key, value);
h[key] = curr;
curr->next = head->next;
head->next = curr;
curr->prev = head;
curr->next->prev = curr;
}
void put(int key, int value) {
if (h.find(key) != h.end())
{
Node *temp = h[key];
h.erase(key);
removeNode(temp);
}
if (h.size() == capacity)
{
Node *prev = tail->prev;
h.erase(prev->key);
removeNode(prev);
}
insertNode(key, value);
}
};
Thanku... Brother❤❤❤... New subscriber
Java 07:41
Great Explanation bro :)
Great explanation🔥🔥revisrd dll😁
what will be the space compleixty of stirivers code ?
Please discuss java implementation for next question.
We have discussed it here too..
Coming from the previous vedio bhaiya
I was just wondering how the add in get was working , this is working addnode(new node(key_,res));
Great teaching always 🙌
why doubly linkedlist why not just linkedlist?
understood.
Striver, you are amazing.
I cannot really wrap my mind around the fact that at such young age(so young that he is calling the nodes as "guy" signifies the fact that his vocab is very limited) he has gained so much skills.
I could not see the correlation between calling a node as "guy" and having limited vocab though😅😅.
understood!!
Awesome!!
🥳
great great great!!!!!!!!!!!!
❤❤
Bro put method implementation is wrong here, it should be else if(cap == mp. size()), as when someone updates a key that already exists there in the map and the size is full then in that case we don't need to remove the least recently used node as we are to inserting any new node we are just updating existing node there
The C++ sol is giving TLE IN leetcode
I am getting TLE , wrote the same code , what to do?
Use a normal map instead of unordered map ur soln will be accepted
@@Vivek-hf7mx Thanks brother it's working
@@manikantsharma6108 it is still not working..
map < int, node * > m;
Unordered_map will give TLE in leetcode, use map
wht ? why i dont think so
@@pranavsharma7479 it happened with me...i know unordered map has avg complexity of 1 and map has logn but still they must have made test cases so that worstcase of unordered map was applicable. Anyways, my code was giving tle on last few TCs with unordered map but ran successfully with map
I don't think i will ever be able to come with a solution like this. I will most likely remain dumb.
yes yes yes
Done
Amazing bhaiya 🔥🔥🔥🔥🔥
we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
Nice
I am getting TLE while submitting the same code
Thank you bhaiya for explaining...but leetcode pr mere TLE de raha h...apka code bhi copy paste krke dekh liya ...helpMe( please, 🙏 );
It is giving TLE on leetcode :( for two test cases.
Use a normal map instead of unordered map ur soln will be accepted
understood❤❤
There will be memory leak not deleting the node just changing the links
OP!!!!
🔥🔥
Bhaiya can you help me to solve this problem or any suggestion (how to make a plugin for upload a csv file in wordpress and display each line in dashboard ?)
Ye
it showing TLE when submitting on leetcode (same code as above in c++) why? can anyone help please
Use a normal map instead of unordered map ur soln will be accepted
Sooooo good
we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
@@freshcontent3729 I think the main advantage of using DLL was the ease with which he was able to reorder the recently used item with O(1) time. I dont think you will be able to do that in O(1) with queues. Not completely sure though.
Given C++ code is giving time limit exceeded error on Leetcode.Can someone please provide working code?
Use a normal map instead of unordered map ur soln will be accepted
Please make a roadmap for BCA Students...
Yes
@@AdityaPrakashSinha .
chumma code deya hai bro
Bhai this solution in leetcode shows the following:-
Runtime: 436 ms, faster than 12.57% of C++ online submissions for LRU Cache.
Memory Usage: 178.6 MB, less than 5.02% of C++ online submissions for LRU Cache.
Is there a better way to solve this question or is this sufficient enough?
Leetcode runtime err is a myth, its not correct always..keeps fluctuating..
Focus on asymptotic complexity
Ok thank you bhai👍👍
we can do this question using queue too right ?? what is the advantage of using Doubly linked list like striver did ? Please tell.
@@freshcontent3729 delete in o(1)
@@takeUforward thanks, so in interview which apporach should I tell ? both or this one ?
I don't think there's any need of changing the address of key in get method coz we are assigning the same node to head->next. correct me if i am wrong.
yes there's no need of changing
Who also gets oyo ad😂
Sorry to say but it is a wrong and very inefficient implementation. Reasons highlighted:
1) No relation between hashmap and linked list. What is the point of keeping Linked list?
2) In case of successful get operation, entry from hashmap and linklist is deleted and added. Honestly, successful get operation should not change hashmap.
3) Put operation should come into place when get operation is unsuccessful. Because if cache is miss then data should be readback from datastore/backend/disk/device and then populate the hashmap using put operation.
4) Find operation of hashmap should be close to O(1), which will not be the case here if more than one get operation is successful for a given key because hashmap is modified.
5) Periodic timer thread should be there to check if cache/hashmap is near to full then free up the entries in the background, otherwise if the cache is full then last cache hit/get operation will always be slow.
Thanks!
First 🥇