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

Code - backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement an LRU Cache.
It is a cache replacement policy that says to evict the least recently used item in the cache.
Every time an item is used it goes to the "front" of the cache since it has been used and has priority.
Items that are not used will go to the "end" of the cache eventually and get evicted since they are the least used items, they never got a bump up by being used.
Additional Cache Eviction Policies: en.wikipedia.org/wiki/Cache_r...
What is a Cache?
A cache is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere.
What Is An LRU Cache?
So a LRU Cache is a storage of items so that future access to those items can be serviced quickly and an LRU policy is used for cache eviction.
The Constraints/Operations
Lookup of cache items must be O(1)
Addition to the cache must be O(1)
The cache should evict items using the LRU policy
The Approach
There are many ways to do this but the most common approach is to use 2 critical structures: a doubly linked list and a hashtable.
Our Structures
Doubly Linked List: This will hold the items that our cache has. We will have n items in the cache.
This structure satisfies the constraint for fast addition since any doubly linked list item can be added or removed in O(1) time with proper references.
Hashtable: The hashtable will give us fast access to any item in the doubly linked list items to avoid O(n) search for items and the LRU entry (which will always be at the tail of the doubly linked list).
This is a very common pattern, we use a structure to satisfy special insertion or remove properties (use a BST, linked list, etc.) and back it up with with a hashtable so we do not re-traverse the structures every time to find elements.
Complexities
Time
Both get and put methods are O( 1 ) in time complexity.
Space
We use O( n ) space since we will store n items where n ist the capacity of the cache.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 13.3 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

[@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 :(

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

[@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 🔥

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

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

[@giannizamora7247]

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

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

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

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

[@amansinhparmar3336]

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

[@BackToBackSWE]

excellent!

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

[@zahranajib5528]

Your energy and spirit is unmatched. Love ya man

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

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

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

[@doruwyl]

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

[@BackToBackSWE]

thanks

[@aayushvrshney]

Best LRU cache explanation on whole KZbin!

[@BackToBackSWE]

thanks

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

[@randomguy-ew6ez]

Another awesome video. I like the screaming to be honest. I was hyped throughout the video.

[@BackToBackSWE]

hahahaha ok, good to know

[@8Trails50]

mans are yelling CS. good shit

[@BackToBackSWE]

@@8Trails50 I know: backtobackswe.com/im-sorry

[@edgarsanmartinjr.4278]

His excitement was contagious. LETS IMPLEMENT A LRU CACHE

[@danni6113]

This channel is so underrated. Great work!

[@BackToBackSWE]

wassup

[@victorkung8922]

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.

[@seymour_videos]

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

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

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

[@riskyferyansyahpribadi6984]

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

[@user-ee5rl7wv8l]

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

[@BackToBackSWE]

sure

[@deeptigaur]

Such a great tutorial on cache implementation ! Thanks for sharing 👏🏻👏🏻

[@BackToBackSWE]

ye

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

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

[@wadichemkhi]

insane level of energy

[@BackToBackSWE]

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

[@ravikanthreddy89]

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

[@BackToBackSWE]

I had a bad mic, sorry

[@karankanojiya7672]

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

[@BackToBackSWE]

thx

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

[@keshavsethi1610]

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

[@BackToBackSWE]

sure

[@lugiadark21]

Bro your channel is underrated, your explanations are the best

[@kamaboko1]

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

[@BackToBackSWE]

nice

[@ReneeSLiu-zx5tj]

I appreciate your thought-process sharing!

[@BackToBackSWE]

sure

[@abcdeereijgfhd3215]

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

[@yasmineelezaby5197]

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

[@dance2die]

Love the explanations and edits!

[@sarahm5750]

Great video and insightful, also love your energy!!

[@paulonteri]

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

[@BackToBackSWE]

thx

[@architgoyal2336]

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

[@BackToBackSWE]

thanks

[@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 😀

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

[@vm1662]

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

[@BackToBackSWE]

sure

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

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

[@anupkulkarni1703]

Good Job Mate! Subscribed to the channel!

[@BackToBackSWE]

love.

[@pulkitagrawal5054]

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

[@BackToBackSWE]

thx

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

[@r1jsheth]

This was one hell of explanation! Many thanks.

[@BackToBackSWE]

Haha sure

[@tashifhoda2414]

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

[@BackToBackSWE]

great!!

[@kumarprateek1279]

Really good implementation and loved your thought process.

[@BackToBackSWE]

thx

[@zummotv1013]

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

[@Nampjg]

Loved your energy man!

[@BackToBackSWE]

thanks

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

[@margeshpatel8456]

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

[@BackToBackSWE]

thx

[@shilinwang2958]

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

[@perlaz1166]

The opening is really cute!

[@BackToBackSWE]

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

[@satheshbm92]

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

[@BackToBackSWE]

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

[@saadtajwar2105]

Amazing videos as always

[@xavierelon]

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

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

[@ayushagrawal258]

Man you made this problem look so easy 🔥🔥

[@BackToBackSWE]

thanks

[@ananyaashrivastava2783]

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

[@BackToBackSWE]

great to hear

[@cleozhang5695]

Nice video!! Dude! Really enjoyed it.

[@BackToBackSWE]

Thank you. I appreciate you.

[@xiaoruizhou694]

very clear explanation! Thank you sir.

[@BackToBackSWE]

ye

[@sergebyusajabo2138]

This is a really good explanation. Thank you.

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

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

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

[@fl7883]

Thanks! you helped me a lot. very clear explain.

[@BackToBackSWE]

sure

[@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))

[@AShahabov]

Awesome LRU explanation!

[@garimasarangal4811]

Brilliant Video Thanks so much

[@gatorademe]

Wow, amazing explanation!

[@BackToBackSWE]

thanks

[@architranjan9]

Awesome explaination, thank you for making this video :)

[@BackToBackSWE]

sure!

[@_battery]

This is awesome. Thank you so much!

[@BackToBackSWE]

yw

[@airysm]

Thank u for making this question seem way less scary lol

[@BackToBackSWE]

you are awesome.

[@azeeztaiwo2802]

Great explanation, great energy!

[@BackToBackSWE]

sure

[@laminendy]

That's an awesome explanation! Thank you!

[@BackToBackSWE]

sure!

[@nagarjunprasad]

Awesome video as always!

[@BackToBackSWE]

hey

[@mshahzaib4195]

Amazing video !!

[@ashwinthobbi]

Love your energy :)

[@BackToBackSWE]

fascinating

[@marlegagaming1274]

You deserve more subscribers

[@BackToBackSWE]

Thanks!

[@contactdi8426]

Friend.. this was awesome!!! Thanks a lot :)

[@quentinlassalle1321]

Awesome explanation, many thanks!

[@BackToBackSWE]

sure.

[@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 🎉

[@kishantiwari3221]

Great Explanation...Thankl you

[@BackToBackSWE]

sure

[@eug_gino]

incredible, thanks so much brotha

[@BackToBackSWE]

sure

[@saitejanagam5748]

Awesome video man

[@BackToBackSWE]

ay

[@ShaliniNegi24]

Thank you and God bless you!

[@BackToBackSWE]

sure

[@addiegupta]

Great video as always

[@BackToBackSWE]

thanks

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

[@Ana-vx5vx]

You teach better than my professor. Thanks

[@BackToBackSWE]

ye

[@abdoaboganima]

Thanks a lot. You made my day :)

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

[@ramyasivaraman2383]

Very nice explanation!

[@BackToBackSWE]

thanks