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.
@@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.
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 ✅
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
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.
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.
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)
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.
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 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 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.
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.
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.
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 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 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?
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?
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)
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
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.
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?
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).
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.
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.
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 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]
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]))
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.
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.
This problem is just annoying, because figuring out how to solve it isn't really that difficult. There's just so many tricky edge cases with pointers. Hate that it's so frequently asked
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.
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?
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?
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.
I'm probably missing something, but why are we inserting as second most right Node and removing as second most left Node? can't we just insert the most right one and remove the most left one?
ok I get it - nodes = Node(0, 0) are just our dummy Nodes which are not stored in cache and we never remove them, they are just needed for initializing LinkedList
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?
LFU Cache: ruclips.net/video/bLEIHn-DgoA/видео.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?
@@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.
@@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.
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!
He's already a hell of an instructor.
I think this is one of the most insane questions I've ever tried lol
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.
1:33 love how he drew the chrome logo completely to explain about the browser😂
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!
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.
The fact that this is now a MEDIUM difficulty question 💀
Seems like companies' hiring standards have gone up...
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 ✅
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
I stopped the video at 5:20 and was able to solve the rest on my own. Thanks for making this video. Great explaination.
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.
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!!
Your explanation was so good! I'm gonna watch more of your videos now
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.
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.
Thanks Mr. NeetCode. I got LRU Cache on my last interview and got the offer.
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.
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 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.
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 😊
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.
lmao neetcode used to put music at the start of videos
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 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!
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.
I was so close yet so far, thank you for this!
I need more than 1 hour to understand your brilliant idea. GOD!
Thnxx bruv...your videos are just awesome... keep it coming
Glad you like them!
Nice explanation and diagramming! Keep them coming
In short:
1. Double linked list
2. Cache key: node
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.
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.
You're awesome dude, thanks for all the work you do to help us out
i have never felt so fucking dumb in my life, this is so fucking hard man
I think this could also be implemented with a circular queue, what do you think?
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.
Omg. I found you today and am watching toy all evening I can't stop
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
Thank you Neet! Learnt something new today!
Thanks man! I am scared of this type of "Medium" questions. I would certainly freeze during an interview...
Among all the neetcode videos I have watched, this one takes longer to code the solution than drawing the explanation.
this solution is so elegant! Thank you!
this solution is the best i've come across.. thank you..
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?
I got asked a version of this for Bloomberg yesterday, wish I'd seen this video beforehand 😥
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 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?
This is an incredible explainable, thank you!
Great videos! Please keep up the good work!
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?
The insert helper function inserts the node in the middle of the linked list but the # comment says it inserts at the right?
Thank you so much, it saved my day of struggling it using python
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
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
what is the benefit of using left and right dummy nodes here as opposed to just left and right pointers?
What is the need for a previous pointer (MRU) for this question? We only need to have the pointer for the LRU right?
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.
Would it be recommended to do this problem using OrderedDict in an interview?
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).
Got asked on Google, should have watched this earlier :(
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.
AWESOME EXPLANATION. THANK YOU !!!
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).
I was able to do it an inefficient way using a Deque to keep track of the lru lol
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
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.
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 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
beautiful. great code and implementation.
Great video thank u ! Just had a q. Whats the difference here using a linkedlist vs double linked list?
I love you boy!!! you made me understand many things
Awesome videos Neetcode. Do you have a website?
Your channel is gem
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]))
when you remove it, you're removing it from the linked list, not the cache.
Amazing explanation man!
Can anyone kindly tell me why LRU = self.left.next rather than self.left when it excceds the capacity?
left and right are there just to point ... the actual LRU is left.next and most recently used is right.prev ....
@@sujeet4410 Thank you! That confused me too!
Please Explain LFU cache too!
thankYou neetcode!!
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.
Nice Explanation!
i implemented the exact same code in JS but i'm getting "time limit exceeded" ... anyone else has workarounds?
For this, isn't it better and simplier to use an OrderDict() in Python?
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.
This problem is just annoying, because figuring out how to solve it isn't really that difficult. There's just so many tricky edge cases with pointers. Hate that it's so frequently asked
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.
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?
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`
Thank you bro that helped me too@@RM-xr8lq
@@RM-xr8lq your explaination saved me!, i was getting mad at this from like 2 hours
Love it beautiful explanation
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?
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.
@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.
awesome explanation as always... can you please make video on LFU cache too
elegant solution!
I'm probably missing something, but why are we inserting as second most right Node and removing as second most left Node? can't we just insert the most right one and remove the most left one?
ok I get it - nodes = Node(0, 0) are just our dummy Nodes which are not stored in cache and we never remove them, they are just needed for initializing LinkedList
@@mlevvy96 We need them to have o(1) access to the LRU and MRU
Can you please make a video of 723. Candy Crush?
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?
THIS IS BRUTALLLLLLLLLL