Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)

[@BackToBackSWE]

Table of Contents: (I'm screaming in this video. I know. I am sorry.) Messing Around 0:00 - 0:23 Problem Introduction 0:23 - 0:36 What Does LRU (Least Recently Used) Mean? 0:36 - 1:10 Short Example of The LRU Policy 1:10 - 2:28 What Is A Cache? 2:28 - 2:53 What Is An LRU Cache? 2:53 - 3:12 The Properties of An LRU Cache 3:12 - 6:44 LRU Cache Operations Walkthrough 6:44 - 12:18 Summarizing The Ideas 12:18 - 12:53 More Subscriber Begging 12:53 - 13:12 Notes: 10:52 -> We need the nodes to hold their own keys. This matters when the LRU entry is evicted when capacity is surpassed. We just pop the item from the doubly linked list's end BUT I made the mistake to say the nodes won't need keys. They will need their respective key. We need the removed node's key to remove it from the hashtable since it is now out of the cache completely. Comments: Yes. I am screaming. I know. I messed up the first like 30 videos because I was still learning audio. The code is in the description. Note, we could also use Java's LinkedHashMap, but I choose to use this code example since it takes all that abstraction away so you see all of the critical operations that need to be taken care of if you were to really implement this.

[@evanxg852000]

It's ok to scream bro, it's just that passion driving you I guess. loving the channel.

[@BackToBackSWE]

@@evanxg852000 hahahahha, nah, I just didn't have a mic

[@michaelfekadu6116]

THANK YOU FOR SCREAMING! IT MADE LRU CACHE MAKE MORE SENSE! THIS VIDEO IS MORE MEMORABLE 😫😄

[@toprank9602]

@@BackToBackSWE is this a system design question?

[@asifbherani3490]

Such a nice explanation but very disappointing end to it as we dont have the code in description. Please update the video and description :(

[@MostafaAliMansour]

This channel is underrated, dude u r really awesome !

[@BackToBackSWE]

Let's increase the rating

[@RohitKumar-so9ik]

Yup seriously this man is way more than what we predict through his subs!!

[@srijaanand2793]

Cannot appreciate enough how well you explain the problem, and not just read out the problem statement and code! Sometimes just understanding the code is required but often I need an in-depth understanding of the question and what was the thought process etc. Whenever I come across a question like that, I just hope that you would have made a video on it and come to your channel :)

[@BackToBackSWE]

sure, and great to hear

[@TKNinja007]

Great video, I love how you spent the entire video breaking down the concepts instead of showing any code.

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@maripaz5650]

just answered this question yesterday in an interview, bless your channel. Thanks to you, I was able to stumble upon the optimal solution a lot quicker than if I was working on my own!

[@BackToBackSWE]

great

[@sddhrtha]

I have my campus recruitment in a month, and your entire channel is on my revision list. Dude, I can't thank you enough for making these high-quality videos.

[@BackToBackSWE]

yw, go get the offer now! haha, u can do it

[@zummotv1013]

DataStructure and Algo group on WhatsApp.Please Join chat.whatsapp.com/GKVxU5dvU1e3v7h9ctDpXn

[@ninja3514]

u Got a Job now?

[@zahranajib5528]

Your energy and spirit is unmatched. Love ya man

[@ANGELINK999]

I feel so lucky that I found your channel. Your videos are so easy to understand. You're awesome!

[@BackToBackSWE]

Thanks haha - shameless plug, releasing a course in 1-2 months - it'll be 🔥

[@snowing906]

Wow how is this channel so underrated. I feel like I found hidden treasure and I want others to also find it...

[@BackToBackSWE]

Let's add to the treasure.

[@kevin-lg3hs]

There's always a Back To Back SWE video to explain the leetcode problem that confused me. Thanks!!!!!

[@BackToBackSWE]

haha

[@zummotv1013]

DataStructure and Algo group on WhatsApp.Please Join chat.whatsapp.com/GKVxU5dvU1e3v7h9ctDpXn

[@giannizamora7247]

I'm about a month into my DS&A study and so many data structures and principles just clicked. Thank you for this!!!

[@aditisaha99]

Really great channel. The level of energy you have is insane. It motivates me more to put more energy to practice and prepare. very well explained and great content. you earned my subscription. Specially with the weather outside when you feel sleepy and dull and cant read more than a page, this is a must watch channel for anyone who is preparing for interviews in this season. Don't change your style :)

[@BackToBackSWE]

will do

[@hihistorystory]

Been watching many tutorial resource these days. This is the best video. Wish I've seen this in the beginning and saved a lot of my time watching others.

[@wadichemkhi]

insane level of energy

[@BackToBackSWE]

lol, old video, I was crazy. Still am.

[@danni6113]

This channel is so underrated. Great work!

[@BackToBackSWE]

wassup

[@shivakrishna7293]

I think u r not an employee u r a perfect teacher i have seen very few people like you sir awesome

[@BackToBackSWE]

ok lol

[@EcheChanga]

Didn't understand this problem until I watched n I been looking at it for days Bless you brother.....and the energy made this so dope

[@abcdeereijgfhd3215]

Holy shoot~! I 've never thought about a double-linked list on this. Thank you for your clarification.

[@amansinhparmar3336]

Thanks man, i literally spent 3 hours on this and finally get after watching this

[@BackToBackSWE]

excellent!

[@LetsBeHuman]

@10:42 - Anytime we interact with the node, it moves to the front of the list. So, lets say we are going to update (that is, put( ) ) 4,10 as 4,20. Shouldn't it take O(n) to traverse the doubly linked list and find where 4 is? each time when we update an existing item in the list, what is the big O for searching that element? By the way, you are welcome to our home for delicious food.

[@BackToBackSWE]

Hahahahahahahaha. Thanks for the offer. And no, access is O(1). We have a hashtable mapping to the memory address of each node. This costs us more space (excluding the list itself) but that is fine since it improves access time.

[@xxiinsanexx]

very very well done. explanations on point. i was asked this question during an interview. got hash table but never remembered doubly linked list. now im quite sure im going to remember it for life. thanks once again mate!

[@lings628]

Your channel is brilliant. I love it so much that I told all my friends about this channel. The clarity in your explanation filled with the energy and passion to teach is just fantastic 🙌

[@BackToBackSWE]

thanks

[@paulonteri]

The Greatest Explanation i've found... Please do more leeetcode.

[@BackToBackSWE]

thx

[@1point0tennis]

I kept getting stuck on how the doubly linked list removal would be O(n) then it clicked when you helped me realize the HashTable value points to the nodes themselves.

[@BackToBackSWE]

yeah, the nodes have unique representations in memory and the hashtable maps those memory addresses.

[@aayushvrshney]

Best LRU cache explanation on whole KZbin!

[@BackToBackSWE]

thanks

[@keshavrastogi5005]

I have not seen such a great explanation and code. You are just awesome man. God bless you!

[@BackToBackSWE]

thanks, if you liked this join our class, I'll be doing more explanations like this there

[@Ana-vx5vx]

You teach better than my professor. Thanks

[@BackToBackSWE]

ye

[@sagarrajput7172]

You are really good at what you do. It is rare to find genuine smartness and passion in same place. You should be proud of yourself. And yes humour makes it good too.🔥

[@BackToBackSWE]

thx

[@kamaboko1]

Dude, you're a rock star. An explanation that made sense.

[@BackToBackSWE]

nice

[@airysm]

Thank u for making this question seem way less scary lol

[@BackToBackSWE]

you are awesome.

[@manishasharma2863]

I am your Fan! No one can explain this with such simplicity. Thanks a ton! :)

[@BackToBackSWE]

sure

[@anssha2643]

You are the best at what you are doing. Love the way you explain and makes things so easy. Its kind of motivating to me. Looking forward to more of your videos. God bless you.

[@BackToBackSWE]

Thanks

[@ananyaashrivastava2783]

Wow ! You made the Question little easy to me ,thanks.

[@BackToBackSWE]

great to hear

[@jkmaksy]

Jeez, having MS interview in two days and then this video comes up :)

[@BackToBackSWE]

lol, a prophecy it is

[@DennisSmdFreefightTrainer]

How did you prepare for your MS interview when you didn't even know this problem?

[@lugiadark21]

Bro your channel is underrated, your explanations are the best

[@perlaz1166]

The opening is really cute!

[@BackToBackSWE]

thnaks? lol, this was way back when no one watched this channel

[@yasmineelezaby5197]

WOW! that's the most clear and easy explanation for this problem. Thanks!

[@cambeeler6374]

Thank you! The way you break-down the problem, and then explain your thinking, really helps me to identify the pattern and approach to thinking around the problem for myself. I really appreciate your investment of time and energy !

[@BackToBackSWE]

sure

[@JoeWong81]

I like your yelling bro it prevents me from falling asleep. nice explanation too

[@BackToBackSWE]

hahahaha ok

[@FrootNinja]

yea it really does help

[@BackToBackSWE]

@@FrootNinja haha ok

[@keshavsethi1610]

thanks, man one of the neatest and most crisp explanation's I have heard

[@BackToBackSWE]

sure

[@seymour_videos]

i legit love his videos because of his sheer excitement and enthusiasm

[@riskyferyansyahpribadi6984]

a very detailed explanation and easy to understand, thank you Back to Back SWE

[@BurhanWani1]

Really liked your explanation. It might have also helped to explain how the hash table stores the address (or the objects in case of Object Oriented languages) of each node corresponding to a key. Good stuff overall.

[@BackToBackSWE]

yep

[@FrootNinja]

first video watched, the fact you left it at sooo i'm hungry then left was dope. smashed that like button and subbed

[@BackToBackSWE]

hha thx

[@poojaguru2516]

Please make more videos Ben coz I'm just surviving by learning through Your videos!! Best explanation :) All of your videos are great! You are an inspiration :) keep doing more videos !! Thanks a ton!

[@BackToBackSWE]

haha nice. I'm starting a class soon. I'll be making 3-4 vids a day w/ Chris Jereza. It'll be good.

[@poojaguru2516]

Waiting 😋😋

[@BackToBackSWE]

@@poojaguru2516 haha

[@bostonlights2749]

Can we just give a shout-out to the awesome intro

[@BackToBackSWE]

lol sorry - no one watched back then

[@madhurapattekar5815]

Very nice video. Please do more videos on LeetCode Questions. It will be helpful. Thanks!!

[@BackToBackSWE]

Yeah, I have 250 scheduled as of now. Will take me over a year to do but we will see how far I get.

[@wawwaw7063]

thank you for your video, I came across this problem today and I had no idea how to implement O(1) put method until I see this

[@BackToBackSWE]

sure

[@TheRadistOne]

Thank you, my guy! This was so clear & I love the ENERGY!

[@BackToBackSWE]

thanks

[@ganeshchandrameesala257]

@@BackToBackSWE where is the code, I couldn't find it in the description

[@karankanojiya7672]

Teaching is an art, certainly mastered by this man! Respect++

[@BackToBackSWE]

thx

[@方宇凡-g4d]

Your videos are always the best, so clear, thank you~!

[@BackToBackSWE]

sure

[@doruwyl]

I appreciate a lot your dedication for explaining things to the other people. Well done!

[@BackToBackSWE]

thanks

[@shantanushende6]

8:40 explained why the left has the LRU and why the right has MRU. Said it before saying it again, legend!!

[@shilinwang2958]

hash table & singly linked list! Thank you, the explanation is really clear.

[@mrthelovepanda]

You can remove a node from a singly linked list in constant time. void RemoveNode (Node N){ N.data = N.next.data; N.next = N.next.next; } Great video, though. Helped a lot.

[@BackToBackSWE]

yeah

[@miry_sof]

Can you remove the last item?

[@MrFTW1001]

But isn’t searching for the item not constant time ?

[@BackToBackSWE]

@@miry_sof yeah

[@BackToBackSWE]

@@MrFTW1001searching would be O(n) time but if we over-write the node being deleted it can be done in O(1) time even for a single linked list. I'll cover that on the site I'm making: twitter.com/thebigoguide I didn't consider this when I made this video months ago

[@FrootNinja]

Your channel should have subs like josh fluke, tech lead, joma tech & cs dojo. You're amazing bro! like keep this format up please!

[@BackToBackSWE]

ok

[@ravikanthreddy89]

insane energy levels !! and nice editing/tranisitions in the algo tracing out. Liked it.

[@BackToBackSWE]

I had a bad mic, sorry

[@ashleylove308]

This intro is everything...Nice walkthrough += entertaining

[@BackToBackSWE]

ye

[@ayushagrawal258]

Man you made this problem look so easy 🔥🔥

[@BackToBackSWE]

thanks

[@yuxinshi2098]

Really helpful! You made this question simple and easier to understand, love the graph!

[@BackToBackSWE]

Everything can be made clear with the proper instruction. I am trying to get better at teaching daily. It is very hard. Thank you for watching.

[@xavierelon]

That intro had me dying 🤣 thanks for the amazing content as always

[@nagamass]

Excellent video. I think, if reached capacity, we need to delete node first before adding. This way, we won't be out of space allocated for Cache

[@BackToBackSWE]

If we reach capacity we eject the LRU item right? Why the first node if that is where the freshest item is inserted?

[@nagamass]

@@BackToBackSWE I feel, we can do eviction before adding new node if we reach limit. let say, limit 4, before adding 5th node, we can do eviction and add the node. but in video, we are adding 5th node then deleting node.

[@nagamass]

@@BackToBackSWE I feel, we can do eviction before adding new node if we reach limit. let say, limit 4, before adding 5th node, we can do eviction and add the node. but in video, we are adding 5th node then deleting node.

[@BackToBackSWE]

@@nagamass We can do it in either order, the final state after removal is the same.

[@sarahm5750]

Great video and insightful, also love your energy!!

[@marlegagaming1274]

You deserve more subscribers

[@BackToBackSWE]

Thanks!

[@ReneeSLiu-zx5tj]

I appreciate your thought-process sharing!

[@BackToBackSWE]

sure

[@AShahabov]

Awesome LRU explanation!

[@john_rambo_27098]

I LOVED the starting...

[@BackToBackSWE]

haha I remember it

[@pulkitagrawal5054]

Wonderful Explanation !! Great work Dude !! Keep making such videos !

[@BackToBackSWE]

thx

[@krishnapurohit3494]

You can delete in O(1) from singly linked list given the pointer to delete.

[@BackToBackSWE]

yeah

[@helloworld4475]

Thanks, you have very good whiteboard skills.

[@BackToBackSWE]

sure

[@satheshbm92]

Man you are the killer. Binge watching all videos :)

[@BackToBackSWE]

Haha. Excellent. Learn. Grow. And dominate the interview.

[@margeshpatel8456]

Like the energy and enthusiasm for teaching. Keep up :)

[@BackToBackSWE]

thx

[@architgoyal2336]

I am new to your channel and this is a great channel. Loved the enthusiasm. Subscribed

[@BackToBackSWE]

thanks

[@r1jsheth]

This was one hell of explanation! Many thanks.

[@BackToBackSWE]

Haha sure

[@humansofcrypto9746]

You can delete an item in a singly ll without knowing its previous node as well, just overwrite the data and the ptr from the next node and delete it.

[@BackToBackSWE]

Yeah that is true, there is just an edge case if you are deleting the last ndoe - correct? I haven't deeply thought about this.

[@vijayj1997]

Best explanation than many other youtubers If it possible can you explain manacher's algorithm ?

[@BackToBackSWE]

yes

[@tashifhoda2414]

Really nice explanation. I was able to implement it with STL on my own!

[@BackToBackSWE]

great!!

[@ok.google]

Glad I've guessed implementation right

[@Adam-tz6gk]

Outstanding explanation thank you so much

[@Siddarthathota]

Can you also create a video on HashMap Implementation. This video about LRU cache is one of the best explanation I came across.

[@BackToBackSWE]

Yep, I had this in the pipeline until I started working on the website I'm making rn for the channel...you'll see it in 1-2 months

[@sergebyusajabo2138]

This is a really good explanation. Thank you.

[@sumanthm4605]

I couldn't find the code in description.. Can somebody tell me where it is.. It's a bit urgent.

[@xiaoruizhou694]

very clear explanation! Thank you sir.

[@BackToBackSWE]

ye

[@anupkulkarni1703]

Good Job Mate! Subscribed to the channel!

[@BackToBackSWE]

love.

[@unanimous8510]

Once I watched the first 15 secs of this video I immediately smashed the like button lol

[@LipsaSenapati]

Thank you for the awesome explanation! Very energetic! Request: It will be very very helpful if you upload a video for the Priority Expiry Cache with python code (probably using 2 heaps and 2 hashmaps works well but I am trying to use an OrderedDict for better performance likely improvement from O(log n)->O(1))

[@vm1662]

Great explanation! Also, the code is very clear. Really appreciate it. :)

[@BackToBackSWE]

sure

[@alvintan4900]

When you use the get function such as get(3) in this video, i understand the 'get' lookup uses the hashtable which is O(1) to retrieve. However, isnt it worst case O(n) to go through the doubly linked list to find the value of 3 in the DLL because you need to traverse through the nodes and thus making overall time complexity of the retrieval to be O(n)?

[@BackToBackSWE]

the hashtable will give us O(1) lookup

[@alvintan4900]

@@BackToBackSWE in this same process, you have to move the 3 key into the head in the DLL, which is what I am referring to the time complexity

[@BackToBackSWE]

@@alvintan4900 Ah, yes we have reference to the head node so we can grab that reference and wire the touched node to the front in O(1) time

[@BackToBackSWE]

@Lisa Jones I did dang chill 😨😨

[@randomuser66438]

@@BackToBackSWE You still didn't answer the question. If you want the least recently used value, you'll have to traverse the whole DLL to get the hash-table reference, regardless of bringing the node to the front afterwards. Doesn't this make the retrieval time O(n)?

[@hz3600]

love your energy, very engaging, and this was a very useful video. Thank you so much!

[@amarajavijayakumar938]

are u able to see the code on the description?

[@MrLazini]

Very clear explanation, much appreciated :)

[@BackToBackSWE]

Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=MrLazini 🎉

[@laminendy]

That's an awesome explanation! Thank you!

[@BackToBackSWE]

sure!

[@rishabkumar4940]

Thanks for explaining it so clearly, I was having a tough time understanding it as its solution is locked on Leetcode😅

[@BackToBackSWE]

great

[@20041537]

easy to understand. well done!!!

[@BackToBackSWE]

thx

[@kumarprateek1279]

Really good implementation and loved your thought process.

[@BackToBackSWE]

thx

[@zummotv1013]

DataStructure and Algo group on WhatsApp.Please Join chat.whatsapp.com/GKVxU5dvU1e3v7h9ctDpXn

[@kishantiwari3221]

Great Explanation...Thankl you

[@BackToBackSWE]

sure

[@asishsandhya]

Great video dude..You made the problem so simpler. Thanks for that. I just subscribed to your channel.. yayyy

[@BackToBackSWE]

sure, welcome to the party

[@Nampjg]

Loved your energy man!

[@BackToBackSWE]

thanks

[@quentinlassalle1321]

Awesome explanation, many thanks!

[@BackToBackSWE]

sure.

[@sihanyang8393]

Where is the code plz? I didn't find it in the description. Thanks for the excellent video!

[@lakshitaagarwal400]

Awesome Explanation......... Can you please provide the code also as you said in the video.....I didnt find the code in description.