LRU Cache | Brute Force | Optimal | Detailed | Leetcode 146
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- This is the 2nd Video on our Design Data Structure Playlist.
In this video we will try to solve a very good and famous and interesting Problem "LRU Cache" (Leetcode 146)
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : LRU Cache
Company Tags : Adobe, Microsoft, Amazon, Citygroup, Twitch and many more shown in video
My solutions on Github : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
Plz keep uploading such videos
It really helps 🙏
true 🔥
I hope I would have got this channel before. You are really awesome bro!!!
It means a lot to me. Thank you so much 😇🙏
Brilliant explanation as always
Instead of adding to the front you can also add to the back only problem is dll.end() return the iterator just after last element we need to subtract the iterator by 1
example:
auto itr=dll.end();
itr--;
map[key].first=itr;
i think erase time complexity of unorderded map is O(N) in worst case which can be avoided by assigning dll.end() and just need to add one check
if(map.find(key)!=map.end() && map[key].first!=dll.end() );
and should use unordered_map instead of ordered map
Indeed . Feels great you mentioned this one ❤️❤️❤️
Mind Blowing
awesome explanation , bhai appke smjhane ka kya hi jawaab hai , mtlb shbd km pd jayenge!!!
Means a lot 😇🙏
bhaiya , i don't know , but the way you build intution in a problem is something which make you unique....pls make videos on recursion and DP.. we will always support you
Thank you so much
Sure thing
Absolutely mindblowing , how u constructed the problem by taking it step by step , line by line , BEST of all
Thank you so much Pritish ❣
LEGENDARY explanation
I had watched other channels as well, this is by far the best explanation
This is one of the finest explanations I have encountered for this problem. Not even famous other youtubers made it this easy
finally ye question ab jake meko clear ho gya is video se... thank you so much bhaiya 🥺🥺🥺
Thank you so much 😇🙏
thanks for the explanation. i have done this question before. revisiting it for revision
Awesome 😇
first I was watching striver's video then i saw u also have uploaded on it , automatically finger went there and clicked on your video.🤗
Thank you so much for trusting my channel and explanation 😇🙏❤️
lol same
same 2 same
Guys, let’s do LRU Cache first.
This will help us to solve LFU Cache
Next video will be on LFU Cache
Thank you all for watching ❤❤❤
Aaay Sir 🔥
yeh pre-requisite hai for LFU cache?
@@AbhijeetKumarAJ No bro pre-requisite is LRU
@@niteshk0487 I AM ASKING is LRU pre-requisite for LFU
Yea this qn should be solved before LFU
It will make it easy for all of us to understand LFU Cache
You skillfully simplify complex ideas, making learning enjoyable. love from this side....
❤️❤️🙏🙏
bro keep uploading
because your way of understanding is very good and communication also,
very helpful for me ,
Perfect explanation. Thanks for the brute force
Thankyou sir , best explanation
really awesome explanation
Thank you ❤️😇
Dude this was 🔥.
Now, waiting for LFU cache
Thankss. Your channel will definitely grow. You have a way with explaining.
Thanks a lot Danish ❤️❤️❤️
Great explanation! Thank you so much..💫💫
You are so welcome 😊
You deserve 100k subs.
Means a lot ❤️
Soon this guy will reach 100k I am pretty sure
I think this is the only video which helped me understand the approach clearly. thank you so much
You are doing great
plz keep doing this .
Amazing explanation.Way to go brother.
Unbelievable explanation. Hats off!!
Thank you so much ❣
Relieved that taj ka POTD ka already video hai is channel ka 🥳🥳🥳🥳
Thanks, bhai. Below are both the Java solution:
Brute Force:
class LRUCache {
List cache;
int n;
public LRUCache(int capacity) {
n = capacity;
cache = new ArrayList();
}
public int get(int key) {
for(int i = 0 ; i < cache.size(); i++){
if(cache.get(i).key == key){
int val = cache.get(i).value;
Pair temp = new Pair(key, val);
cache.remove(i);
cache.add(temp);
return val;
}
}
return -1;
}
public void put(int key, int value) {
for(int i = 0 ; i < cache.size(); i++){
if(cache.get(i).key == key){
cache.remove(i);
cache.add(new Pair(key, value));
return;
}
}
if(cache.size() == n){
cache.remove(0);
cache.add(new Pair(key, value));
}
else {
cache.add(new Pair(key, value));
}
}
}
class Pair {
int key;
int value;
Pair(int _key, int _value){
this.key = _key;
this.value = _value;
}
}
Optimal:
class LRUCache {
Node head = new Node(0, 0), tail = new Node(0, 0);
Map < Integer, Node > map = new HashMap();
int capacity;
public LRUCache(int _capacity) {
capacity = _capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
insert(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
remove(map.get(key));
}
if (map.size() == capacity) {
remove(tail.prev);
}
insert(new Node(key, value));
}
private void remove(Node node) {
map.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void insert(Node node) {
map.put(node.key, node);
Node headNext = head.next;
head.next = node;
node.prev = head;
headNext.prev = node;
node.next = headNext;
}
class Node {
Node prev, next;
int key, value;
Node(int _key, int _value) {
key = _key;
value = _value;
}
}
}
You are a Life saviour.
Wow. tysm
thank you bhai and Nagma
bhai u r exceptional , tysm😍
Thank you so much 🙏❤️😇
Awesome👏👏👏👏....................I was using a Deque😦
Bhai bhai bhai
Kya samjhaya hai 💯
Thanks a lot 😇🙏
woaaahhhh explanation!! superb
Thank you so much ❣
Thanks for the video sir, loving your content.
Thanks Sneha.
Welcome to my channel
Awesome explanation, loved it !!
Thank you so much ❣
Thanks a lot sir
amazing explanation.keep it up
Thank you so much Harikesh ❤️❤️❤️
Amazing. Thanks a lot
Need java code if possible
U r damn good in explaining things bro 🙏 please could you guide us further on how to improve dsa it would be great help 🍀
Thanks a lot Harsh ❤️❤️
I will soon make a video on guide also.
Hope that will help
@@codestorywithMIK it will definitely help me a lot bro thanks looking forward to watch it 🤞
The Best Explanation Possible
Thank you so much Sachin ❤️🙏
Great content❤
Java Solution using DLL and map to store Key and address
created addNode and delNode function
class LRUCache {
class Node{
int key;
int val;
Node prev;
Node next;
Node(int key, int val){
this.key = key;
this.val = val;
}
}
Node head = new Node(-1, -1);
Node tail = new Node(-1, -1);
int cap;
HashMap m = new HashMap();
public LRUCache(int capacity) {
cap = capacity;
head.next = tail;
tail.prev = head;
}
// function to add a new node
private void addNode(Node newnode){
Node temp = head.next;
newnode.next = temp;
newnode.prev = head;
head.next = newnode;
temp.prev = newnode;
}
// function to delete a node
private void deleteNode(Node delnode){
Node prevv = delnode.prev;
Node nextt = delnode.next;
// join previous and next to remove node
prevv.next = nextt;
nextt.prev = prevv;
}
public int get(int key) {
// if present in map
if(m.containsKey(key)){
Node resnode = m.get(key);
// stores value
int ans = resnode.val;
// makes it most frequently used
// remove from map
m.remove(key);
// remove from node
deleteNode(resnode);
// add to node
addNode(resnode);
// add to map
m.put(key,head.next);
return ans;
}
// is not present in map and LL
return -1;
}
public void put(int key, int value) {
// if it already contains key so we can later readd
if (m.containsKey(key)){
Node curr = m.get(key);
m.remove(key);
deleteNode(curr);
}
// if it is of filled size
if (m.size() == cap){
m.remove(tail.prev.key);
deleteNode(tail.prev);
}
// simply add it at head
addNode(new Node(key, value));
// put key and new address in map
m.put(key, head.next);
}
}
Thanks brother!!
Hey please continue the graph concept series.. thankyou
++
nice ❣
Thank you so much Sachin.
Thank you 🙏
so the optimal solution time complexity is O(1)? and space complexity is O(n) as we are storing data in doubly linked list?
Absolutely correct Abhijeet ❤️
goat..tecahing
wonderful
Amazing brother ❤
Thank you so much 😇❤️
great explanation! thanks!
Glad it was helpful! 😇
one of the best explanation for this question but sir one doubt will interviewer would ask us about the internal implementation of this doubly linked list ?
Thanks a lot Sidharth.
Actually it totally depends if you are a fresher they ask for implementation.
But for questions like these, they dont ask internal implementation because this question itself is lengthy
Went through the comments and disappointed to see that not even a single soul came up with the queue solution. Anyways, here is my implementation for the same:
class LRUCache {
int size;
queue q;
map mp, cnt;
public:
LRUCache(int capacity) {
size = capacity;
mp.clear();
}
int get(int key) {
if (cnt.find(key) == cnt.end())
return -1;
q.push(key);
cnt[key]++;
if(mp.find(key) != mp.end())
return mp[key];
return -1;
}
void put(int key, int value) {
q.push(key);
cnt[key]++;
mp[key] = value;
while (cnt.size() > size) {
int cur = q.front();
q.pop();
if (cnt[cur]-- == 1)
cnt.erase(cur);
}
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
Thank you so much for sharing ❤️❤️
Awesome bhaiya op
6k Soon Bhhaiya Love You
Hope so 🥹
Thank you so much Harsh ❤️🙏🙏
It’s 6k now - th-cam.com/users/shortsXxYKzdIp1rI?feature=share
Thank you for your well wishes Harsh 😇🙏❤️
@@codestorywithMIK Welcome Now It will be 10K as your way of teaching is excellent
@codestorywithMIK dequeue se push and pop o(1) mai hota hai so y we had used DLL rather than dequeue
Wow daily challenge already avalaible
Yes 😇🙏👍🏻
Thank you so much for seeing my video 🙏
🔥
awesome explanation
Thanks a lot Girish ❤️
Small correction push_back in dll is O(1)
what 's the explanation bro great !
Thank you so much Shivam ❤️❤️
Please make video on comparator function in C++.
Sure soon.
bhaiya.., i think it's time to take one step forward and go for GFG's POTD also.. what's your thought ?? ,, GFG coders don't get are Quality Explanation on entire TH-cam ,, no one explains questions like you,,
Totally agree.
Just need to crunch more time to cover gfg potd. Will soon start this also
@@codestorywithMIK Yaa.. i know you already working hard and had a very busy schedule and still uploading video's consistently... your dedication is so much appreciable 🙏🙏
@rahulmaurya6451 Means a lot 🙏🙏🙏
bhya tell me onre thing , thoda awckward question h but dekh lena
ek vector m n elements hai to uski run time complexity O(n) hai, but agar hm vector of pair store kr rhe hn to uski complexity O(n^2) honi chahiye naa, because single index store two values in that data structure.
dll create krke fir btana next if possible kyuki stl wala thoda confusion h
Sir,Issi ke sath LFU ka bhi dekh lete toh kaam ho jata
LFU video uploaded in this playlist 🙏😇❤️
won't the list.pop_back() becomes equivalent to traversing the whole list and deleting the last element, which makes the time complexity of this operation as O(n), so it doesn't make difference if we insert the newest element at first, or at last, because either the insertion , or deletion will be still o(n) ??
Excellent explanation understood it very well 👍
Thanks a lot Sharib ❤️
kindly add timelines in videos bhaiya.
I have a confusion, why we need to remove [2,2] in the beginning, as per algo we need to remove [1,1] which is added before [2,2]..
Can you explain it clearly??
Because [1,1] was just recently used. Hence it’s fresh.
[2,2] was not recently used that’s why it’s not fresh.
NOTE : Qn does not say to remove those which added before, qn is saying to remove those which was LEAST recently used .
See 3:33 of this video.
Hope that will help 😇🙏❤️
bhai thoda chotti video banaya karo,warna thummbnail se hi bhagna padta hai
Bhaya kvi aisa hua h ki aapko kisi daily problem m doubt ho or aap discussion section m gye ho. 😅
Indeed Yes Sourav.
But sometimes i hate the solutions provided there because most people don’t explain in detail. So i just try to simplify and produce my own simplified explanation ❤️
Shouldn't you be using unordered_map instead of map? Because time complexity of find() in map is O(logn) whereas in unordered_map is O(1).
🙇♂🙏
in first approach get method is not quadratic, it is linear.
BHAIYA ONE DOUBT IF THIS QUESTION WILL BE ASKED IN A INTERVIEW AND THE INTERVIEWER DIDNT ALLOW US TO USE STL LIST THEN WHAT WILL WE DO
I DONT THINK I CAN MAKE MY OWN DOUBLY LINKED LIST CLASSS AND TGEN EVERYTIME CHANGE LINKS FOR EVERY OPERATION?
Hi Kunal,
It actually depends. There can be many scenarios :
1) If you are a fresher then they will expect you to know about Data Structure and would want you to implement dll
2) Since this qn is intself a lengthy, and implementing dll separate might take a lot of time because of which interviewer might not be interested in the dll implementation
3) Interviewer might only ask how will you implement dll and then let you continue with stl .
4) When I had cracked Microsoft, there was a qn which was short and it required min heap. Since the qn was short, i was asked to implement min heap on my own.
@@codestorywithMIK Got it bhaiya thanks for the reply 🤩
why are we specifically pushing the recent ones in the front of the list? Can't we push them at the back instead if we want to?
Bhaya dll.pop_back() constant complexity h ? Ya o(n)
Thanks for asking this Qn.
It’s O(1) i.e. CONSTANT
You can read more here : cplusplus.com/reference/list/list/pop_back/
Bhaya ye function constant time m kaise kaam kr lete h jaise ki vector.size () h ,Bina traverse krre kaise ?
@@adhikari669 kyuki iski internal implementation class se hui hai, to bas apn uska method call kar rhe getsize() type to vo O(1) me return karta
@@twi4458Ha ye to m smjha ki class m ek member function h iss naam ka to call kro or answer return krega pr ye Bina traverse kree size kaise pta kr leta h , ye puchna tha..
Come soon
Can we use queue or dequeue ( stl c++) ??
class LRUCache {
public:
class node {
public:
int key;
int val;
node *next;
node *prev;
node(int k, int v)
{
key = k;
val = v;
}
};
node *head = new node(0,0);
node *tail = new node(0,0);
int cap =0;
unordered_map mp;
LRUCache(int capacity) {
cap = capacity;
head->next = tail;
tail->prev = head;
}
void deleteNode(node *root)
{
mp.erase(root->key);
node *nextNode = root->next;
node *prevNode = root->prev;
prevNode->next = nextNode;
nextNode->prev = prevNode;
}
void addNode(node *root)
{
mp[root->key] = root;
node *temp = head->next;
head->next = root;
root->next = temp;
temp->prev = root;
root->prev = head;
}
int get(int key) {
if(mp.find(key) != mp.end())
{
node *curr = mp[key];
int ans = curr->val;
deleteNode(curr);
addNode(curr);
return ans;
}
return -1;
}
void put(int key, int value) {
node *temp = new node(key, value);
if(mp.find(key) != mp.end())
{
node *curr = mp[key];
deleteNode(curr);
mp.erase(key);
}
if(mp.size() == cap)
{
mp.erase(tail->prev->key);
deleteNode(tail->prev);
}
addNode(temp);
mp[key] = temp;
}
};
@Devender Verma 😂😂😂👍🏻
Bhaya apni leetcodeprofile share kroo 🙏
Hey Sourav,
Find all here github.com/MAZHARMIK
Why can't we use only map here ?
why don't we use deque for this problem ?
Cant i use hashmap + queue here?
1584. Min Cost to Connect All Points, Make Video on it.
Sure Animesh. Soon
cache[key] undeclare hai na??
why did't you use unordered_map?
unordered_map in C++ doesn’t allow keeping pair inside it.
@@codestorywithMIK i used unorderd_map and it passed all test cases.
unordered_map does't allow pair as key but it allow as value
@akki8534 Yes yes.
You are right ❤️
mera kyo accept nhi ho rha??
ye test case galat hai
["LFUCache","put","put","get","get","get","put","put","get","get","get","get"]
[[3],[2,2],[1,1],[2],[1],[2],[3,3],[4,4],[3],[2],[1],[4]]
Correct ans: [null,null,null,2,1,2,null,null,3,2,-1,4]
Wrong ans by leetcode: [null,null,null,2,1,2,null,null,-1,2,1,4]
Please share your code
Good explanation but I found and coded up
A better and easy solution using the same DLL and map but i am using a inbuilt STL splice mathod
which makes life very easy for transfering of node in linked list to begin
code for the same :-
class LRUCache {
public:
// optimal approach +. use an map and doubly linkedlist use STL
// use an STL splice function to esy transfer of node in DLL
unordered_map mp; // {key , value == iterator of list}
list dll; //{key,value}
int cap;
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
int value = -1;
// first check if is present in map or not
if( mp.find(key) == mp.end() )
return -1;
else //key exists
{
auto it = mp.find(key) ;
value = it->second->second; //this we need to return
// lets place it at front
dll.splice(dll.begin(),dll,it->second);
}
return value;
}
void put(int key, int value) {
//
// first check if is present in map or not
if( mp.find(key) != mp.end() ) //update its value and move to front
{
auto it = mp.find(key);
//value updation
it->second->second = value ;
// move to front
dll.splice(dll.begin(),dll,it->second);
return ;
}
if(cap==mp.size()) //map size == list size use any one but mp.size is better tc
{
//need to delete from back
//lets store the key to delete we have to delete from map also
int key_to_delete = dll.back().first;
dll.pop_back();
mp.erase(key_to_delete);
}
// insert at begin in list and insert in map
dll.emplace_front(key,value); //emplace front or push_front but emplace front have better TC
mp[key] = dll.begin();
}
};```