LRU Cache - Twitch Interview Question - Leetcode 146

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
CODE ON GITHUB: github.com/neetcode-gh/leetco...
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/lru-cache
0:00 - Read the problem
2:00 - Drawing solution
7:30 - Coding solution
leetcode 146
#twitch #interview #python
Song: Bamboo by Oak Studios
Creative Commons - Attribution ND 4.0
• [Royalty Free Music] B...

[@NeetCode]

LFU Cache: kzbin.info/www/bejne/mH2oenukYqmapaM 🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@RMarcus05]

Watched so many of your videos prepping for an SDE 1 FAANG interview. I was asked this exact question (OO LRU Cache) and also Walls and Gates (which you have a video on). I managed to remember/and work through the problems incredibly easy b/c I could vividly remember your explanations and drawings. Happily, I received an offer today! Can’t thank you enough :)

[@NeetCode]

That's awesome Ryan, you just made my day! Congrats 🎉

[@shauryakapoor2122]

what company? CONGRATSSS!!!!!!!!!

[@anonymoustv8604]

That's so cool man. Congrats!!

[@boscodomingo]

Aaaaaaand that is the perfect example of how broken these interview questions are. I'm glad you got it, but you didn't necessarily work it out yourself. You were lucky enough to be asked a question you already knew the answer to. This rarely ever happens in real life! And when it does, all you have to do is use a method from a library 99% of the times. You need problem solving skills these interviews don't ask for, and I hate it. Glad you got to game the system, and best of luck when facing actual programming problems!

[@minciNashu]

@@boscodomingo on the other hand, this evens out the playfield

[@brucebatmanwayne8514]

1:33 love how he drew the chrome logo completely to explain about the browser😂

[@ChanChan-pg4wu]

This has been a dreadful question that I did not want to touch until today. Thank you, Neet for the clear explanation! You will make a hell of an instructor!

[@CST1992]

He's already a hell of an instructor.

[@TannerBarcelos]

Been deep into my work in my current job and have gone completely rusty on algorithms / data structures. Hell, I was never good to begin with but just worked hard enough to land my gig. Starting to look into a fresh start at a new company, so getting back to the Leetcode - algorithms grind, and came across your channel again. This was an awesome solution but also a very helpful, straightforward explanation of the problem, data structures to use, solution, and everything in between. Thanks a ton.

[@zishiwu7757]

Thanks! I have an interview tomorrow. Been preparing by watching your videos on the Blind 75 and Neetcode 150 questions. Really appreciate the time you take in making these videos and giving clear explanations. Hope you can keep it up.

[@NeetCode]

Thank you so much!! And best of luck!!

[@shavitl.306]

Hi, I'm doing this too! so thanks too, NeetCode. How did it go @Zishi Wu? are you happy about this way of preparation? any suggestions?

[@shady4071]

how did ur interview go?

[@zishiwu7757]

​@@shady4071 Interview went well and I got the job. I've been working 6 months so far and really like. Now I'm hoping not to be impacted by layoffs in tech industry.

[@JRK_RIDES]

​@@zishiwu7757 I know I'm late but really happy to see someone succeed. Thank you for sharing your experience.

[@FasTical]

It took me 1 night to figure out the traversal node between insert and remove, it's hard to imagine without doing any drawing, and I glad that I'm able to figure it out :) You're truly a legend to be able to figure this.

[@TehCourier]

I think this is one of the most insane questions I've ever tried lol

[@Retrosenescent]

This was explained so well, and I massively appreciate that you talked slowly because that was a ton to take in all at once

[@CST1992]

That is the only reason that I keep coming back to this channel - he talks at a reasonable pace unlike some other channels that go on and on like a machinegun.

[@prafulparashar9849]

I was asked this question just today in a system design round and absolutely and horribly tanked it big time. Regretting why I did not see this before but also happy that I got to see this solution. This is engraved in my brain now !! Thanks for the good work ✅

[@mariasitkovets]

Your explanation was so good! I'm gonna watch more of your videos now

[@bronchiel]

a way i thought of solving this problem was with a queue and a hashmap, but i soon realized that there was no way to do such a thing in O(1) since finding an element would require me to go through the entire queue in worst case, and that having a map would be entirely useless in this case… so, i appreciate the solution you’ve brought here for us

[@ShiftK]

This was exactly my train of thought as well! Using a LinkedList for keeping track of the LRU and of the "most used" is better than a queue since we can store the Nodes directly into the HashMap. Therefore, when we access this node, we already have its next() and right() siblings to make the Get and Put function O(1)

[@QuadQuadQuadQuad]

Nice explanation and diagramming! Keep them coming

[@mama1990ish]

This channel is much better to the point and easy to understand then others.

[@symbol767]

This is an incredible explainable, thank you!

[@strawberriesandcream2863]

never would have thought to use a doubly linked list🤦‍♀thanks for the explanation!!

[@vyomdavep18]

Great videos! Please keep up the good work!

[@linchen4535]

I would give you X100 thumbs up if I could! Clear explanation and makes me fully understand why using those data structures and design a class!!

[@NeetCode]

Happy to help 😊

[@nikhildinesan5259]

Thnxx bruv...your videos are just awesome... keep it coming

[@NeetCode]

Glad you like them!

[@niko-l-]

Omg. I found you today and am watching toy all evening I can't stop

[@jxw7196]

Hey man your videos are great! Keep up the good work - it looks like you have taken your time to plan your videos carefully too.

[@NeetCode]

Thanks! I'm happy they are helpful!

[@TSS554]

You're awesome dude, thanks for all the work you do to help us out

[@thelonearchitect]

It took me a good two hours to understand why we should have a map to Node and not a map to Value but now it just makes so much sense. Algorithms really has a way to enlarge the mind.

[@sijunchen7270]

Thank you so much, it saved my day of struggling it using python

[@Sulerhy]

I need more than 1 hour to understand your brilliant idea. GOD!

[@stormarrow2120]

I stopped the video at 5:20 and was able to solve the rest on my own. Thanks for making this video. Great explaination.

[@MP-ny3ep]

AWESOME EXPLANATION. THANK YOU !!!

[@codeunited5905]

I attempted to make an LRU cache on my own without watching the video in Go. I come up with a more naive and slow version which takes advantage to slices and map in Go. But I'll definitely try to rewrite the code using LL and map. It was really fun!

[@Artemius10]

Awesome, thx! It amazes me how clear and easy it gets after explanation, yet how complicated it seems (and actually is) when you have to solve this in a stressful limited time environment like in an interview. One note though - in case if key is already present in cache in insert function, before inserting node itself, we should return before doing len(cache) > capacity check, this way we get quite a significant optimization by not doing redundant heavy logic. Another note would be to add a current count property to LRUCache to not execute len(cache) at all and reduce time complexity from O(n) to O(1).

[@sumeshbharathiramasamy8559]

Hi @Artemius10, I think both your proposals are invalid. 1. the second "if' loop (capacity check) will be true only if new insert is going to happen. Calling "return" before it, won't significantly improve performance, i believe. 2. len(HashMap) will be always O(1). Because in Python, Hashmaps will always keep track of their sizes, so iterations will not be performed for length.

[@emzx111]

Great video thank u ! Just had a q. Whats the difference here using a linkedlist vs double linked list?

[@quirkyquester]

this solution is so elegant! Thank you!

[@25kirtan]

beautiful. great code and implementation.

[@fed3919]

Thanks man! I am scared of this type of "Medium" questions. I would certainly freeze during an interview...

[@potaot573]

Thanks Mr. NeetCode. I got LRU Cache on my last interview and got the offer.

[@anabelberumen]

I love you boy!!! you made me understand many things

[@pranotidesai5084]

I was preparing for this ques in Nov and why do I feel I saw a different approach of using Orderdict instead. I was looking for LinkedList approach but couldn't find that back in Nov.

[@g7parsh]

Hey man, i've been watching a ton of your videos lately in order to learn about data structures and problem solving and it's been really good stuff. A question i have though is how do you know what types of structures would be best fit for a given problem? What about a question makes you notice that you should use a hash map or a DLL or a stack? Or is that something that just comes about from just drawing out how an algorithm plays out?

[@raianmr2843]

Most problems don't require you to use any particular data structure. This one is different tho. It's the O(1) insertion and lookup that implies a hash map. There many are other data structures that offer similar performance, but for 80% of all problems you don't actually have to stray further than the same old five or more data structures. The DLL part is a bit hard to grasp for newbies like us but long story short, DLLs play nicely with hash maps, more so than others.

[@watchlistsclips3196]

Neetcode you are amazing i saw many people are using doubly linked list but not linked list but i am not getting why we should use doubly linked lists i saw videos from top 3 of my youtube channels but they didn't explain the clear intuition behind taking doubly linked lists.I am scratching head why doubly linked lists for 1 hour. Now i got reason😌😌.Thank you

[@brentjackson6966]

This is a badly described coding problem. For one thing, it does not describe a LRU or a MRU. It describes a FIFO queue - the first entry added will be the first evicted. The second added will be the second evicted. etc. To answer your question. Imagine a MRU - like the 'recent files' in VS Code. When you open a file it gets added to the front of the 'recent files' list and if the list is 'full' (at capacity) the oldest gets removed from the end of the 'recent files' list. If you open the 7th file in the 'recent files' it is moved from the 7th spot to the start of the list. To do this, you can find the linked list entry using the hash map but for a single linked list you would now need to walk the linked list from the start to find the 6th entry so you can link it to the 8th, thus removing the 7th from the list so you can put it at the start. Walking the linked list is an O(list-size) operation. If you have a double linked list, each node has a pointer to the previous and next next node so you can remove the 7th in O(1) time. And the puzzle mentions doing 'put' and 'get' in O(1) time. That's why people use a double linked list for this problem. However, since the problem does not involve moving entries from the middle to the front of the list, there is no reason to use a double linked list.

[@nikhil_a01]

@@brentjackson6966 It's not correct that it's a FIFO queue. The first entry added is not always the first one evicted, because any `get()` or `put()` on an existing key counts as a use. The linked list is maintained in access order, not insertion order. Simple example: The cache's capacity is 3 and I add keys 1, 2, and 3. Then I read key 1 which counts as a use. When I add key 4, key 2 will be evicted even though key 1 was the first one added. And it does move entries from the middle to the end of the list, which is why it's doubly linked. Every use (get or update) removes the node with that key and puts it at the end.

[@InfoBuzz0830]

Love it beautiful explanation

[@syedzami-ul-haquenavid9392]

Amazing explanation man!

[@shashwatshekhar5676]

Would it be recommended to do this problem using OrderedDict in an interview?

[@soninirav]

awesome explanation as always... can you please make video on LFU cache too

[@_XY_]

Very good explaination 👏👏

[@haibanglol3498]

tough problem.. it was hard LC before I think maybe would've been better to take a case where capacity is like 4 or 5, problem is already confusing with left/right pointers and prev/next variables but overall great video, thanks

[@SomethingNick]

I got asked a version of this for Bloomberg yesterday, wish I'd seen this video beforehand 😥

[@jeevansinghbanga6393]

The insert helper function inserts the node in the middle of the linked list but the # comment says it inserts at the right?

[@chenzhuo9]

Thank you!!

[@daniyalkabir6527]

This is super helpful!

[@atulkumar-bb7vi]

Nice Explanation!

[@sudharsanka8413]

What is the need for a previous pointer (MRU) for this question? We only need to have the pointer for the LRU right?

[@xjlonelystar]

beautiful drawing lol best part of the video

[@erickmwazonga8871]

Awesome videos Neetcode. Do you have a website?

[@ziyiyang4550]

Great video and excellent design! One question though: in put(), if we end up evicting a node and insert a new one, there is no guarantee that the new key is going to map to the same spot as the old one in hash table (if we peek into the array implementation of hash table). So effectively, even if we are within the capacity limit, there could be collision in the hash table, which means some spots are empty and wasted?

[@nikhil_a01]

There are always going to be some spots empty in a hash table. If a hash table gets too full the chance of collisions increases hugely. So hash tables resize themselves once they get too full. In Python it resizes when it gets 2/3rds full, and in Java by default it's at 75% full (but it's configurable in Java). In the example from the video, even though we set our LRU cache's capacity to 2, the underlying hash table has whatever capacity Python decides (which is 8 since that's the starting size for any Python dictionary).

[@sanjeevrajora7335]

thanx for the explanation

[@aishwaryaranghar3385]

thankYou neetcode!!

[@tonyz2203]

nice explanation!

[@BuyHighSellLo]

What writing software are you using? it looks so smooth!

[@NeetCode]

Thanks, I use Paint3D

[@anushavishwanathan8276]

This is GREAT love all your videos. In this case isn't using only one data structure - OrderedDict in Python sufficient? Just coded up a solution on THELEET that beat 80% so was curious could Neet or someone post for me the advantages of using a doubly linked list with a normal hash map?

[@somdebdatta9086]

In the insert function, we are inserting the node at the end right? Which means appending. Why are we inserting between the right most element and the second right most element?

[@nikhilaradhya4088]

In short: 1. Double linked list 2. Cache key: node

[@aaditya_87]

lmao neetcode used to put music at the start of videos

[@memeproductions4182]

I think this could also be implemented with a circular queue, what do you think?

[@danielbzhang3280]

Just one quick question: in the get method, if you remove the node "self.remove(self.cache[key])", then how can you insert it to the list again since the node is already removed (self.insertRight(self.cache[key]))

[@Mohammed-lo7mf]

when you remove it, you're removing it from the linked list, not the cache.

[@nikhil6842]

Your channel is gem

[@fayezabusharkh3987]

Thank you!

[@aneeshbhandari4560]

While doing this question in C++, is it possible to implement the linked list with a struct instead of a class? If not, why not? If yes, are there any drawbacks?

[@lawrencezhang3899]

This solution is awesome

[@rishabhnitc]

as always top quality

[@harshit4190]

Please Explain LFU cache too!

[@sy_alty]

The fact that this is now a MEDIUM difficulty question 💀 Seems like companies' hiring standards have gone up...

[@joannelin5597]

Thanks!

[@sujeet4410]

i implemented the exact same code in JS but i'm getting "time limit exceeded" ... anyone else has workarounds?

[@ritwik_shivam]

Amazing explanation as always, just a doubt 6:35, why are we removing [2,2] instead of [1,1] since it was leftmost and least recently used, shouldn't that be [2,2], [3,3] after re-arranging the cache.

[@amandaflood]

1 was asked for by 'get' so counts as most recently used. I was confused by this too to start with.

[@mastermax7777]

bro what the fuck . why is leetcode so hard

[@PAVANKUMAR-vj8oi]

any cons if I implement it with python list instead of creating doubly linked list ?

[@moteq6598]

Deleting keys will be costly and will be O(n)

[@sidhartheleswarapu]

I was able to do it an inefficient way using a Deque to keep track of the lru lol

[@PinkRosePurpleMauve1]

When I tried to run your solution, there is an error at this line: prev.next, nxt.prev = nxt, prev Error message: AttributeError: 'tuple' object has no attribute 'next' I cannot seem to find the error, and I can't fix it. What do you think could be the cause of this?

[@NeetCode]

Hmm, not sure but I just posted my code on github: github.com/neetcode-gh/leetcode/blob/main/146-LRU-Cache.py Hope it's helpful. Let me know if you figure out the issue.

[@CallOfShadyBlackOps]

@NeetCode @Vy Nguyen The video is missing a line in insert function where you assign node.next,node.prev=nxt,prev . It is correct in his Git Repo.

[@daniekpo]

I tried solving this by myself first but did not use a dummy left and right node. My left and right were null until they pointed to something. That added an extra check and I kept running into different edge cases. I spent a bit of time trying to make it work to show that you can solve the problem without dummy nodes, but I need to move forward now. Did you ever try to solve it with left and right pointing to actual nodes and could potentially by null?

[@mama1990ish]

very good content

[@crit19871]

Thanks

[@NeetCode]

Thank you so much!!!

[@jashangill4089]

Got asked on Google, should have watched this earlier :(

[@analisamelojete1966]

I was just asked this today 😂, couldn’t finished it in 10 mins but the guy got the idea of what I was doing. Thought oh this is a great exercise just to find it’s been asked constantly. :/

[@analisamelojete1966]

Solved it later using a class attribute called recent. The most right item is always the most recent. Although the complexity is O(n) where n is the class attribute.

[@s8x.]

no way people can solve this for the first time without preparing for it

[@dmytrodieiev9338]

solved it using c++ without preparation, the hint was on the LT under "topics": "hash map", "DLL" - then figured out the solution, which was pretty the same as showed here

[@angeldiaz3018]

@@dmytrodieiev9338 then you're a robot or a special human

[@Wasif1998]

For this, isn't it better and simplier to use an OrderDict() in Python?

[@nikhil_a01]

In real-life it's better to use OrderedDict. They've basically already implemented this for you. But in a coding interview, they probably wouldn't let you otherwise this problems becomes a 2 minute one.

[@bonle3771]

THIS IS BRUTALLLLLLLLLL

[@lixujin1698]

Can anyone kindly tell me why LRU = self.left.next rather than self.left when it excceds the capacity?

[@sujeet4410]

left and right are there just to point ... the actual LRU is left.next and most recently used is right.prev ....

[@panzach]

@@sujeet4410 Thank you! That confused me too!

[@robr4501]

you are a savior !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@nataliagrigoryeva6615]

I love NeedCode and use its explanations to create solutions in JavaScript. For this particular problem, it's overcomplicated for JavaScript. There, you will need only the Map data structure (no need for a double-linked list). Just a heads-up for those using JavaScript.

[@pcccmn]

damn...this question is so hard hahaha

[@TheThickPizza]

You can make this a lot more simpler by using an OrderDict from collections: from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = OrderedDict() def get(self, key): val = self.cache.get(key) if val is None: return -1 self.cache.move_to_end(key) return val def put(self, key, value): self.cache[key] = value self.cache.move_to_end(key) if len(self.cache) > self.capacity: _ = self.cache.popitem(last=False) Using `move_to_end` will handle the LRU part for you.

[@itvaya]

can anyone tell me which app is he using for this video

[@mshohag4229]

Can you please make a video of 723. Candy Crush?

[@Anon-ce2hk]

I don't quite understand the logic of the insert() helper function. Neetcode mentions verbally that he wants the node to be the right most node, but then the diagram shows Node being inserted before the right-most node. Could anyone explain what's going on there in this implementation?

[@RM-xr8lq]

he is using sentinel (dummy) nodes, the head of the linked list is at left's `next` and the tail is at right's `prev`

[@SwiftYMB]

Thank you bro that helped me too@@RM-xr8lq

[@harshitvh1]

@@RM-xr8lq your explaination saved me!, i was getting mad at this from like 2 hours

[@sirrus3009]

got asked this in my amazon phonescreen

[@igalkop]

Not sure why do we need to keep the "Key" in the Node object, Why can't we have the Node object only contain the value, prev & next ?

[@dmytrodieiev9338]

Because if the LRU value has to be evicted, it should be removed from the DLL and also from the hash map; having only "value" in Node wouldn't allow to remove entry from the hashmap - so the key is needed there

[@dmytrodieiev9338]

consider key in the Node as a backpointer to the entry in the hash map

[@christendombaffler]

I hate it when Hard questions get bumped down to Medium just because they're popular and/or they're known to be asked by famous companies. As someone who's in the middle of a career break and one job away from changing careers away from the IT world in general, this is probably leetcode's biggest shortcoming.

[@nan5715]

How long does it take to solve this?

[@hynguyen7375]

Can someone please explain to me the logic behind this line: pre,nxt = self.right.prev,self.right I can't seem to understand why he pick self.right.prev and self.right?

[@waiyanleung5199]

Why the node needs to have key and value, but not value only?

[@gradientO]

Answered at 13:53

[@user-fq2lo2nb3k]

AMAZING