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 :)
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!
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.
@@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.
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.
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
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)
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!
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.
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!
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.
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.
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 ✅
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.
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
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
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)
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).
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.
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.
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
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.
@@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.
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!
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
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.
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.
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.
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?
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.
I might have missed if you mentionned it in the video (sorry if i did) but It is also possible to use orderedDict to solve this question in a more pythonic way, dare i say, although i would recommend the doubly linked list+dict version in an interview setting (+ orderedDict is actually built on a doubly linked list): from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.root = OrderedDict() self.capacity = capacity def get(self, key: int) -> int: if key not in self.root: return -1 val=self.root[key] del self.root[key] self.root[key] = val return val def put(self, key: int, value: int) -> None: if key not in self.root: self.root[key] = value if self.capacity
there is a purpose that leetcode ask you to use specific data structure for the problem. And companies also want to test us on the same, its very easy to get the problem done using ordered dict and solve everything in just O(1) but if companies want to test ur knowledge depth in linked list they might ask you to solve this problem using linked list instead of ordered dict
OrderedDict actually provides a method, `move_to_end(key)`, to move a key to the end of the linked list. And it provides a way to remove the first item from the linked list using `popitem(last=False)`. So there's an even shorter solution than yours. class LRUCache: def __init__(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity def get(self, key: int) -> int: if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) -> None: if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.capacity: self.cache.popitem(last=False)
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. :/
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.
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
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.
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?
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).
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?
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
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?
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?
Some things to notice: 1. Available capacity should be checked before adding things to cache. In this case, an item is added, and then another is removed if size exceeds capacity. 2. When updating existing values, there's no need to discard the old node and create a new one. The old node's value can be update in place and the node reused. The remove method should be called something like 'splice' because you're disconnecting a node from the list, and that node can be pasted elsewhere in the list. In this case you paste it at the end of the list to signify it's the most recently used.
The remove() method should not be called splice(). It only removes the node and doesn't do anything else with it. The fact that you *sometimes* re-insert it elsewhere is irrelevant to remove(). ('Sometimes' because when we evict the LRU we just remove the node and don't re-insert it). In C where there's a distinction between removing a node and actually freeing it I might agree with you. In Python it would just be confusing. Checking the capacity before adding is fine, but doesn't make any difference in this case. It's a logical capacity, not a physical one. The underlying hashmap isn't bounded so it doesn't matter if you go over by 1 temporarily.
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?
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.
I am having an existential crisis after solving this question using just a dictionary and it got accepted in neetcode as well as leetcode, I don't understand how it is possible to be that simple when everyone is using like LL or queues and stuff: class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.dictionary = {} def get(self, key: int) -> int: if key in self.dictionary.keys(): val = self.dictionary[key] del self.dictionary[key] self.dictionary[key] = val return val else: return -1 def put(self, key: int, value: int) -> None: if key in self.dictionary.keys(): del self.dictionary[key] self.dictionary[key] = value if len(self.dictionary) > self.capacity: first_key = next(iter(self.dictionary)) del self.dictionary[first_key]
I came with the same solution but I thought this medium prblm wouldnt be this complicated that You would need to use hashmap and linked list at same time
Very clean and logical code. In a real implementation, the Node is actually better placed as the hash-map key, so the key itself does not need to be repeated too. Here, the key is an int, so there's little to no benefit.
LFU Cache: ua-cam.com/video/bLEIHn-DgoA/v-deo.html
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
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 :)
That's awesome Ryan, you just made my day! Congrats 🎉
what company? CONGRATSSS!!!!!!!!!
That's so cool man. Congrats!!
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!
@@boscodomingo on the other hand, this evens out the playfield
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.
Thank you so much!! And best of luck!!
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?
how did ur interview go?
@@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.
@@zishiwu7757 I know I'm late but really happy to see someone succeed.
Thank you for sharing your experience.
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.
I think this is one of the most insane questions I've ever tried lol
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
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)
lmao neetcode used to put music at the start of videos
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!
He's already a hell of an instructor.
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.
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!
1:33 love how he drew the chrome logo completely to explain about the browser😂
was thinking the same, the logo was pretty good ngl
This was explained so well, and I massively appreciate that you talked slowly because that was a ton to take in all at once
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.
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.
I stopped the video at 5:20 and was able to solve the rest on my own. Thanks for making this video. Great explaination.
This channel is much better to the point and easy to understand then others.
never would have thought to use a doubly linked list🤦♀thanks for the explanation!!
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 ✅
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.
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
Your explanation was so good! I'm gonna watch more of your videos now
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
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.
I need more than 1 hour to understand your brilliant idea. GOD!
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)
thanks so much.
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).
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.
Thanks Mr. NeetCode. I got LRU Cache on my last interview and got the offer.
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.
Thanks! I'm happy they are helpful!
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!!
Happy to help 😊
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.
The rare occasion where the coding part is longer than the drawing part in a NeetCode video
Thanks
Thank you so much!!!
I was so close yet so far, thank you for this!
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
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.
@@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.
You're awesome dude, thanks for all the work you do to help us out
Hi Neetcode, we can use deque . i think it would provide more optimized solution. what do you think?
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.
The fact that this is now a MEDIUM difficulty question 💀
Seems like companies' hiring standards have gone up...
What was it originally? Hard?
@@ares9335 yes it was marked hard in leetcode, since a lot of companies are asking this nowadays.. its marked medium now
Nice explanation and diagramming! Keep them coming
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!
I got asked a version of this for Bloomberg yesterday, wish I'd seen this video beforehand 😥
Omg. I found you today and am watching toy all evening I can't stop
Thnxx bruv...your videos are just awesome... keep it coming
Glad you like them!
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
i have never felt so fucking dumb in my life, this is so fucking hard man
I think I reached my brain limit. I withdraw
this solution is so elegant! Thank you!
Among all the neetcode videos I have watched, this one takes longer to code the solution than drawing the explanation.
Thank you Neet! Learnt something new today!
Great videos! Please keep up the good work!
Nice explanation. Thanks NeetCode.
This is an incredible explainable, thank you!
Thanks man! I am scared of this type of "Medium" questions. I would certainly freeze during an interview...
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.
this solution is the best i've come across.. thank you..
Thank you so much, it saved my day of struggling it using python
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.
In short:
1. Double linked list
2. Cache key: node
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.
I can imagine how you would implement LRU will be an instant follow-up question
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?
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?
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.
AWESOME EXPLANATION. THANK YOU !!!
I might have missed if you mentionned it in the video (sorry if i did) but It is also possible to use orderedDict to solve this question in a more pythonic way, dare i say, although i would recommend the doubly linked list+dict version in an interview setting (+ orderedDict is actually built on a doubly linked list):
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.root = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.root:
return -1
val=self.root[key]
del self.root[key]
self.root[key] = val
return val
def put(self, key: int, value: int) -> None:
if key not in self.root:
self.root[key] = value
if self.capacity
there is a purpose that leetcode ask you to use specific data structure for the problem. And companies also want to test us on the same, its very easy to get the problem done using ordered dict and solve everything in just O(1) but if companies want to test ur knowledge depth in linked list they might ask you to solve this problem using linked list instead of ordered dict
@@aishwariyaaish8305 yep
OrderedDict actually provides a method, `move_to_end(key)`, to move a key to the end of the linked list. And it provides a way to remove the first item from the linked list using `popitem(last=False)`. So there's an even shorter solution than yours.
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
@@nikhil_a01 Waaaah so coool, orderedDict really turns this lion of a problem into a puppy
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. :/
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.
I love you boy!!! you made me understand many things
no way people can solve this for the first time without preparing for it
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
@@dmytrodieiev9338 then you're a robot or a special human
@@dmytrodieiev9338 yep I was able to get it first time, but only because they mentioned the topics. Implementation was a nightmare though lol
beautiful. great code and implementation.
I think this could also be implemented with a circular queue, what do you think?
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.
1 was asked for by 'get' so counts as most recently used.
I was confused by this too to start with.
why do we initialise lru = self.left.next and not lru = self.left at 13:54
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?
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).
what is the benefit of using left and right dummy nodes here as opposed to just left and right pointers?
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?
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
I actually thought of them as individual answers, but no way I could have come up with such a solution to integrate both concept as one............
Amazing explanation man!
What is the need for a previous pointer (MRU) for this question? We only need to have the pointer for the LRU right?
Great video thank u ! Just had a q. Whats the difference here using a linkedlist vs double linked list?
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?
I'm not sure, but OrderedDict probably implemented with some kind of tree. And operations on trees are not O(1).
The insert helper function inserts the node in the middle of the linked list but the # comment says it inserts at the right?
I was able to do it an inefficient way using a Deque to keep track of the lru lol
awesome explanation as always... can you please make video on LFU cache too
Funny enough i just used a queue no keep track of the least recently used items with a dictionary and it seems to work fine.
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?
Very good explaination 👏👏
this question honestly cooked me so hard
Would it be recommended to do this problem using OrderedDict in an interview?
Some things to notice:
1. Available capacity should be checked before adding things to cache.
In this case, an item is added, and then another is removed if size exceeds capacity.
2. When updating existing values, there's no need to discard the old node and create a new one. The old node's value can be update in place and the node reused.
The remove method should be called something like 'splice' because you're disconnecting a node from the list, and that node can be pasted elsewhere in the list.
In this case you paste it at the end of the list to signify it's the most recently used.
3. get method doesn't need to remove and insert if key is already MRU
The remove() method should not be called splice(). It only removes the node and doesn't do anything else with it. The fact that you *sometimes* re-insert it elsewhere is irrelevant to remove(). ('Sometimes' because when we evict the LRU we just remove the node and don't re-insert it). In C where there's a distinction between removing a node and actually freeing it I might agree with you. In Python it would just be confusing.
Checking the capacity before adding is fine, but doesn't make any difference in this case. It's a logical capacity, not a physical one. The underlying hashmap isn't bounded so it doesn't matter if you go over by 1 temporarily.
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?
Awesome videos Neetcode. Do you have a website?
Love it beautiful explanation
Your channel is gem
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.
Didn't need to do interview prep for 7+ years and now get to "enjoy" all the LC questions that were bumped down from hard to medium in the meantime
I am having an existential crisis after solving this question using just a dictionary and it got accepted in neetcode as well as leetcode, I don't understand how it is possible to be that simple when everyone is using like LL or queues and stuff:
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dictionary = {}
def get(self, key: int) -> int:
if key in self.dictionary.keys():
val = self.dictionary[key]
del self.dictionary[key]
self.dictionary[key] = val
return val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.dictionary.keys():
del self.dictionary[key]
self.dictionary[key] = value
if len(self.dictionary) > self.capacity:
first_key = next(iter(self.dictionary))
del self.dictionary[first_key]
lmfao
Nice Explanation!
Please Explain LFU cache too!
thankYou neetcode!!
Got asked on Google, should have watched this earlier :(
beautiful drawing lol best part of the video
This is super helpful!
Can't we use an Ordered HashMap which abstracts the use of LinkedList here and provides the same functionality and complexity?
I came with the same solution but I thought this medium prblm wouldnt be this complicated that You would need to use hashmap and linked list at same time
Very clean and logical code.
In a real implementation, the Node is actually better placed as the hash-map key, so the key itself does not need to be repeated too.
Here, the key is an int, so there's little to no benefit.