LRU Cache - Twitch Interview Question - Leetcode 146

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

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

[@shadyplaysgoodgames]

how did ur interview go?

[@zishiwu7757]

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

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

[@TehCourier]

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

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

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

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

[@aaditya_87]

lmao neetcode used to put music at the start of videos

[@BrennenSongyongYu]

I'm gonna make it habit to say thank you on every LeetCode video I watch of yours. I remember your recent LinkedIn post where you talked about how you enjoy doing these, but they don't bring as much views as your other content. Just want to show that your work is meaningful!

[@brucebatmanwayne8514]

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

[@puzzle-headed-cat]

was thinking the same, the logo was pretty good ngl

[@Wes-Tyler]

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.

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

[@tesuji-go]

I implemented LRU for an in-process cache a couple years ago and both Java and Javascript have a Map variant that returns the keys in insertion order. They already have the linked list built in between the nodes, you don't need to make a second one. What Javascript doesn't do is update the key order on overwrite, so you have to delete and add every time. But it saves a ton of code.

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

[@mama1990ish]

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

[@strawberriesandcream2863]

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

[@maria_sitkovets_tech]

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

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

[@haibangi]

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

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

[@VenomIsLazy]

Best Channel I ever seen for any DSA problem thank you so much even if I don't get placed in any company still learned alot.

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

[@Sulerhy]

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

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

[@potaot573]

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

[@nikhildinesan5259]

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

[@NeetCode]

Glad you like them!

[@crit19871]

Thanks

[@NeetCode]

Thank you so much!!!

[@anangelsdiaries]

I was so close yet so far, thank you for this!

[@TSS554]

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

[@niko-l-]

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

[@navaneeth67]

The rare occasion where the coding part is longer than the drawing part in a NeetCode video

[@abhayattri974]

try using ordered dict for the implementation, will make the code whole lot easier. when getting if key is found move_to_end(key) else -1 when putting - add key then move_to_end(key) and if len(dict) > cap: pop(last= false)

[@PJ-hi1gz]

thanks so much.

[@QuadQuadQuadQuad]

Nice explanation and diagramming! Keep them coming

[@AustinCS]

I think it would be helpful to consider different naming conventions for left and right - essentially because they are sentinel nodes that basically reference the head and tail of the doubly linked list.

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

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

[@dheepthaaanand3214]

Just want to point out that get() reuses the same node pointer, but in put (), if the node exists, we are de-linking the existing node pointer, creating a new node pointer and linking that, but we aren't clearing the memory of the old node pointer, i.e, using del function like how we did for deleting the LRU node if capacity exceeds, so i think we should add that extra line

[@saurabh2802]

i have never felt so fucking dumb in my life, this is so fucking hard man

[@AhmedMarzookisabeast]

thanks for the explnation main part i got stuck on was thinking of using a queue but a doubly linked list makes sense should have checked the topics section in LeetCode for some clues here is my solutions got a 169ms runtime but didn't use dummy nodes and had to cover the null scenarios: class NodeItem: def __init__(self,key, val): self.key = key self.val = val self.next = None self.prev = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = None self.tail = None def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self.remove_node(node) self.add_to_mru(node) return node.val else: return -1 def put(self, key: int, value: int) -> None: new_node = NodeItem(key, value) if key in self.cache: self.remove_node(self.cache[key]) self.cache[key] = new_node self.add_to_mru(new_node) return if len(self.cache) >= self.capacity: del self.cache[self.head.key] self.remove_node(self.head) val = self.cache[key] = new_node self.add_to_mru(val) def add_to_mru(self, value: NodeItem): if self.head == None and self.tail == None: self.head = value self.tail = value else: self.tail.next = value value.prev = self.tail self.tail = value def remove_node(self, node: NodeItem): if node == self.head: self.head = node.next if self.head: self.head.prev = None else: node.prev.next = node.next if node == self.tail: self.tail = node.prev if self.tail: self.tail.next = None else: node.next.prev = node.prev if self.head is None: self.tail = None

[@akhma102]

Thank you Neet! Learnt something new today!

[@sy_alty]

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

[@ares9335]

What was it originally? Hard?

[@harshnegi5811]

@@ares9335 yes it was marked hard in leetcode, since a lot of companies are asking this nowadays.. its marked medium now

[@dawitz362]

Nice explanation. Thanks NeetCode.

[@vyomdavep18]

Great videos! Please keep up the good work!

[@NightDay1]

I think I reached my brain limit. I withdraw

[@SomethingNick]

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

[@symbol767]

This is an incredible explainable, thank you!

[@quirkyquester]

this solution is so elegant! Thank you!

[@DelShott]

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

[@sijunchen7270]

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

[@shantipriya370]

this solution is the best i've come across.. thank you..

[@sachleenkaur8731]

why do we initialise lru = self.left.next and not lru = self.left at 13:54

[@racecarjonny8460]

Among all the neetcode videos I have watched, this one takes longer to code the solution than drawing the explanation.

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

[@anabelberumen]

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

[@MP-ny3ep]

AWESOME EXPLANATION. THANK YOU !!!

[@25kirtan]

beautiful. great code and implementation.

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

[@biskitpagla]

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.

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

[@vteckickedin2365]

@@dmytrodieiev9338 yep I was able to get it first time, but only because they mentioned the topics. Implementation was a nightmare though lol

[@syedzami-ul-haquenavid9392]

Amazing explanation man!

[@devanshimittal7986]

Hi Neetcode, we can use deque . i think it would provide more optimized solution. what do you think?

[@k0tyak1t15]

It don't works in the case you put a new value into existing key because you should move element from the middle of deque to its tail.

[@InfoBuzz0830]

Love it beautiful explanation

[@Susjeevs]

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

[@saladHz]

Shouldnt you also delete the node after you check if it already exists? since all the remove() function does it disconnect the nodes to the node itself, however the node itself is still connected to other nodes. It won't be deleted in the capacity check since you already inserted the new node in its place. Correct me if im wrong since im still learning but for c++ the put check condition should like this. if (cache.find(key) != cache.end()) { Node *replace = cache[key]; remove(cache[key]); delete replace; } Effectively detaching any pointers that point to the node to be replaced, and then deleting it.

[@atulkumar-bb7vi]

Nice Explanation!

[@nikhilaradhya4088]

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

[@xjlonelystar]

beautiful drawing lol best part of the video

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

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

[@aishwaryaranghar3385]

thankYou neetcode!!

[@nikhil6842]

Your channel is gem

[@johnyha9236]

this question honestly cooked me so hard

[@XxRazcxX]

Why do you need to have tail pointers? Why not has the left and right nodes point to the real values rather than the (0,0) tails?

[@emzx111]

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

[@_XY_]

Very good explaination 👏👏

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

[@memeproductions4182]

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

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

[@maryokhin]

I can imagine how you would implement LRU will be an instant follow-up question

[@sanjeevrajora7335]

thanx for the explanation

[@quirkyquester]

elegant solution!

[@OrphanedZombie]

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

[@daniyalkabir6527]

This is super helpful!

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

[@TheTrendSupreme]

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

[@soninirav]

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

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

[@shashwatshekhar5676]

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

[@jashangill4089]

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

[@tonyz2203]

nice explanation!

[@bonle3771]

THIS IS BRUTALLLLLLLLLL

[@pcccmn]

damn...this question is so hard hahaha

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

[@leonscander1431]

I'm not sure, but OrderedDict probably implemented with some kind of tree. And operations on trees are not O(1).

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

[@notlooce]

what is the benefit of using left and right dummy nodes here as opposed to just left and right pointers?

[@harshit4190]

Please Explain LFU cache too!

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

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

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

[@dheepthaaanand3214]

When there are no nodes initially, we just have left and right, and so we need to insert between right and right.prev which is left. For upcoming nodes, we again need to insert between right and right.prev which would be the recently added node

[@lawrencezhang3899]

This solution is awesome