LRU Cache | (C++, Java, Python) |30 day Challenge | Day 24 | LeetCode

[@KnowledgeCenter]

Share your interview experience. If it was asked to you in any programming interview?

[@riteshsrivastava3447]

that god it was wrongly put into capacity function else i was just getting frustrated ;-

[@gokulnaathbaskar9808]

Best video explanation of LRU Cache, short and clear!!!

[@KnowledgeCenter]

Thanks. Glad you think so.

[@bleakMidWinter8]

Best solution to this problem till now. This was asked in Goldman Sachs last technical interview round I couldnt answer it properly

[@jimwoodward7293]

Your explanations are very clear and very easy to follow. You have impressive programming knowledge. Thanks for posting your videos.

[@KnowledgeCenter]

Glad it was helpful!

[@jimwoodward7293]

@@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.

[@KnowledgeCenter]

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.

[@jimwoodward7293]

@@KnowledgeCenter That would be great -- thank you so much!

[@revanthvenkateswar622]

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 !!

[@KnowledgeCenter]

Glad it was helpful!

[@harshthakkar7503]

Best explaination 👏🏻

[@KnowledgeCenter]

Glad it was helpful!

[@techspiritzz2268]

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)?

[@f3-faithfitnessfinance]

In Java To find out the initially inserted element is that the only way or is there an alternate way?

[@KnowledgeCenter]

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.

[@shubhamsood1406]

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.

[@inFamous16]

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

[@dhanashreegodase4445]

thanks man!

[@KnowledgeCenter]

Welcome.

[@tomasmachacek2468]

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!

[@KnowledgeCenter]

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.

[@monojit104]

Could you plz make a video for the LFU, leetcode 460?

[@KnowledgeCenter]

Sure. Will create it immediately after May challenge ends. Already 3 leetcode questions Queued based on other Coders' requests. Thanks for suggesting.

[@rishisharma5249]

Nice video sir!!!

[@KnowledgeCenter]

Thank you!

[@AshokKumar-sw9oc]

Nice video , can u make a series of important questions asked by companies

[@KnowledgeCenter]

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??

[@poojaagarwal1480]

@@KnowledgeCenter Yes that will be good! Please keep uploading solutions to leetcode problems. This keeps us going.

[@KnowledgeCenter]

@@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...

[@poojaagarwal1480]

@@KnowledgeCenter Yes Thank you

[@aditgulia]

For java code directly go to 20:24

[@siddarthvaranasi1175]

Can you please make a video on the TTL variant of the same problem? Thanks!

[@elrey0801]

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?

[@KnowledgeCenter]

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).

[@elrey0801]

​@@KnowledgeCenter thanks for your detailed explanation!

[@anonymous_upsc_asprnt]

I have doubt when 1 was added 2nd time after that why it's not put in cache when it was not present there.

[@KnowledgeCenter]

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.

[@anonymous_upsc_asprnt]

Thanks

[@rishikeshkumarsingh3283]

waiting for the video from the morning

[@KnowledgeCenter]

Hope you enjoyed it!

[@ketanlalcheta4558]

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?

[@inFamous16]

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.

[@RishiRaj-dl1mg]

Awssom video sir. When I'm using keys.end()then it's giving compile error. So what's the difference between .end() and . back ()

[@KnowledgeCenter]

end() returns iterator pointing to 1 position after the last element. back() returns the last element. Both are different things.

[@RishiRaj-dl1mg]

@@KnowledgeCenter thanks sir

[@tarunsingh3687]

Why can't we use deque instead of list in c++? Using deque gives an error. Please REPLY.

[@riteshsrivastava3447]

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 .

[@adityasrivastava7956]

+1

[@TheMsnitish]

are you a software engineer ?

[@PradeepKumar-so5wq]

what does map[key].second=keys.begin(); saving ?

[@arpit_singh10]

position of that key in the List

[@arpanpandey5869]

does anyone else get TLE for c++ code submitted recently ?

[@piyushanand6664]

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()}; } };