LRU Cache | (C++, Java, Python) |30 day Challenge | Day 24 | LeetCode
Вставка
- Опубліковано 19 вер 2024
- Complete Playlist LeetCode Solutions: • LeetCode Solutions | L...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
LeetCode 30 day Challenge | Problem 24 | LRU Cache | 24 April,
Facebook Coding Interview question,
google coding interview question,
leetcode,
lru cache python,
lru cache java,
lru cache c++,
#Facebook #CodingInterview #LeetCode #30DayChallenge #Google #LRU #Amazon
Share your interview experience. If it was asked to you in any programming interview?
that god it was wrongly put into capacity function else i was just getting frustrated ;-
Best solution to this problem till now. This was asked in Goldman Sachs last technical interview round I couldnt answer it properly
Your explanations are very clear and very easy to follow. You have impressive programming knowledge. Thanks for posting your videos.
Glad it was helpful!
@@KnowledgeCenter They are very helpful. I'm considering joining your channel, what additional benefits are there to joining. Can I submit specific questions to you? I program in Python. Thanks.
Wait for some time. I'll add a small video with all the details shortly. Better to join after that. And yes, adding specific Questions would be one of the benefits.
@@KnowledgeCenter That would be great -- thank you so much!
Best video explanation of LRU Cache, short and clear!!!
Thanks. Glad you think so.
Fantastic. You go to great depths to put across the underlying concepts of the video. A positive learning experience came out of this lockdown. Thank you for this !!
Glad it was helpful!
Best explaination 👏🏻
Glad it was helpful!
thanks man!
Welcome.
Thanks for the video! Referring to the C++ solution, it is accepted in Leetcode, however, the worst case time complexity of unordered_map's erase function is linear. So wouldn't that make the worst case of this algorithm O(n)?
One question I have for C++ implementation, for maintaining the order of [key, value] pair why you didn't use the Ordered Map ( map ) ? Please clear this doubt.
you don't require ordering here as long as you are storing the address of the page from list. Also using map will take O(logn) time for access and we have to do it in O(1), hence unordered_map is the most suitable here
Nice video , can u make a series of important questions asked by companies
Thanks for suggesting. I had started a playlist for Google and Facebook. But I felt there are good overlaps. So, rather than having separate playlists, I should have Common playlist of good and/or popular questions.
The LeetCode playlist in the channel was created with that intent. Will keep adding regularly to it.
I also felt most of the good questions asked in interviews are available on LeetCode. So, I plan to enrich LeetCode playlist itself.
Any suggestions on this, or it looks fine??
@@KnowledgeCenter Yes that will be good! Please keep uploading solutions to leetcode problems. This keeps us going.
@@poojaagarwal1480 Sure. And make sure to try the problems first yourself and after that only refer videos like the ones on this channel or other channels, just to look for other approaches, or compare if there are better approaches available, or you are stuck for some time.
Good Luck... Happy Learning...
@@KnowledgeCenter Yes Thank you
Nice video sir!!!
Thank you!
In Java
To find out the initially inserted element is that the only way or is there an alternate way?
You can implement it using LinkedList and Hash Map instead of LinkedHashMap.
For LinkedHashMap you get the standard Map interface. So, you get the keyset() or entryset() then iterate. The thing that differentiates it from normal HashMap is internal implementation of preserving the order of insertion. The interface remains same.
public class LinkedHashMap
extends HashMap
implements Map
So, LinkedHashMap provides standard Map Interface.
Could you plz make a video for the LFU, leetcode 460?
Sure. Will create it immediately after May challenge ends. Already 3 leetcode questions Queued based on other Coders' requests. Thanks for suggesting.
waiting for the video from the morning
Hope you enjoyed it!
Hi,
if .keySet().iterator().next() is pointing to the first key of the LinkedHashMap, how do I point to the last key?
And also, why do we remove the first key when the first is the most-recently-used, or isn't it?
Thank you!
First key is the key that is oldest. Last key is the most recent inserted key. So, we are removing first key.
Also for getting the last key in linkedHashMap, we need to iterate till end. It will be O(n) opeartion.
while (iterator.hasNext()) { last_key = iterator.next() }
or _map.keySet().toArray()[_map.size() -1]
public class LinkedHashMap
extends HashMap
implements Map
So, it doesn't provide interface for LinkedList but rather Map.
I have doubt when 1 was added 2nd time after that why it's not put in cache when it was not present there.
In this implementation of LRU get(key) calls donot insert a new (key,value) into the cache, since value info is not present in get() call. So, only key&value are inserted in put(k,v) calls.
Though you are correct. If the constraint of (key,value) is not there as imposed by LeetCode for this problem, and if we are just storing keys, and not values, get(key) should also insert keys into cache, if it is a cache miss.
So, in short the answer to your question is get(key) doesn't have value info, so no new insertion in get() calls here.
Thanks
Awesome playlist... thanks for this...
I have a question on C++ implementation of get function.How it gets compiled is making me confused..
keys.erase will need iterator of list as keys is of type list.
But you are passing _map[key].second
Isn't this a pair of int and list iterator?
bro _map[key] itself is giving you the access of the value of _map for the key and then doing .second, you are getting access to the second element of the pair.
Can you please make a video on the TTL variant of the same problem? Thanks!
Awssom video sir. When I'm using keys.end()then it's giving compile error. So what's the difference between .end() and . back ()
end() returns iterator pointing to 1 position after the last element. back() returns the last element. Both are different things.
@@KnowledgeCenter thanks sir
sir, I have a question.
Is that erase operation in list O(1) or O(n), since it need to traverse through the linked list to find the element to be deleted?
We are not storing index, but iterator itself, we have direct pointer to the node. We don't need to start from beginning.
unordered_map _map;
So, you see we are storing list::iterator, which is pointing to the node. No traversal required. So, O(1).
@@KnowledgeCenter thanks for your detailed explanation!
sir a strange question , actually i was wondering if people does this kind of questions at one go ? bcz i couldn think it ... i had to watch vedio for most of the standard questions .
+1
For java code directly go to 20:24
Why is this not working anymore? 14/21 test cases.
class LRUCache {
int cap;
listls;
unordered_mapmp;
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
if(mp.find(key)!=mp.end())
{
ls.erase(mp[key].second);
ls.push_front(key);
mp[key].second = ls.begin();
return mp[key].first;
}
return -1;
}
void put(int key, int value) {
if(mp.find(key)!=mp.end())
{
ls.erase(mp[key].second);
ls.push_front(key);
mp[key]={value,ls.begin()};
}else
{
if(ls.size()==cap)
{
mp.erase(ls.back());
ls.pop_back();
}
}
ls.push_front(key);
mp[key]={value,ls.begin()};
}
};
Why can't we use deque instead of list in c++? Using deque gives an error. Please REPLY.
are you a software engineer ?
what does map[key].second=keys.begin(); saving ?
position of that key in the List
does anyone else get TLE for c++ code submitted recently ?