LFU Cache - Leetcode 460 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve lfu cash the problem that will make you hate your life it's very similar to the lru cash problem which we have solved before I will link to that problem below I definitely recommend understanding how to solve that before you understand lfu cache because this problem is basically built on top of that other problem the idea is mostly simple we have a cache that has a certain capacity that is passed into the Constructor and we want to implement two simple operations we want to be able to get a value based on the key and we want to be able to put a key and map it to some value in the cache now if we're inserting a new key we will add that key to our cache if we're inserting an existing key and just changing the value we're just going to update the value the interesting thing happens though what happens if we're adding a new value but our capacity is already be full like we don't have any room to add any new values but we want to add a new value then we have to remove a value the way we're going to do it is by removing the least frequently used value so clearly we're going to be able to need to count for every key how many times has it been used and they tell us how we can count that basically when we put a value for the first time we say the count of it is equal to one and if we put that same key value again and just change the value of that key then we're going to have to increment the count to two now every time we get the same key value we're also going to increment the count so if we got that value we'd have to increment this to three for that single key value now if that wasn't complicated enough what happens if there's a tie what happens if we're adding a new value but there's multiple values that are least frequently used what if there's two values that have been used once and we want to choose which one of those we should remove we can't just choose ran randomly then if there's a tie we have to then choose the least recently used value just like they mentioned over here that's why you probably need to solve the lru problem before trying to solve this one and on top of that we have to implement both the get and put operations in constant time so I don't want this to be a super long explanation so I'm going to quickly go over how we solve the lru problem we have to use a doubly linked list so suppose this is the left side this is the right side and this is where we add the most recently used value so suppose we add a value to our linked list like this is what it is and then we add another value to the linked list we'd add it over here so suppose we add values like this these two every node will be connected to the previous and the next node so that's how we would put new nodes every time we call the put operation but what happens if we get a value how do we make sure that this now moves all the way over here so suppose like we this value is one and we call get on this key now we want to say this is the most recently used so we'd want to move it over here this would be our new least recently used while we're also on top of this doubly linked list we're going to have a hash map which is going to map every single key value to the node itself so when we map from the hashmap to the node notice how we have all the information we need to perform insertions and deletions because every node has a pointer to the previous and the next so we can easily remove the node from anywhere in the linked list and then move it to the end of the linked list over here so we're going to use that idea here but what makes this even more complicated is that we don't just have a single doubly linked list in this case because remember if there's a tie among multiple nodes it's going to be because all of those nodes have the same count they've been used the same number of times so actually we need to map the count of every single key value to a linked list a doubly linked list like this and then those key values will be nodes in that linked list so maybe this linked list will be all nodes that have been used once maybe this linked list will be nodes that have been used twice then if we perform a bunch of put operations and we end up evicting some of these nodes we will evict them from the appropriate list now also we need to keep track of what that least frequently used count is because that's going to tell us which linked list do we want to remove from let's suppose that count is currently one we're going to be removing these and removing these and by the time we remove all of them where we need to notice that weight this list is now empty so we can't say our least frequently used count now is one we have to update it to two for example and then we'll start removing nodes from this list and the way we're going to store a bunch of linked lists like this this is within a hash map so the hashmap key will be the count that those keys have been used before and then the value will be that doubly linked list I know this is really complicated I think the best way to explain it would be for me to just show you the code so let's go into that now but the way we're coding it both of these operations are going to be constant time operations the memory complexity though is going to be big of n where n is the number of keys so I'm going to mostly skip the doubly linked list implementation I'll quickly go over it now we'll have a list node each node will have a value and two pointers previous and next simple enough we'll have a doubly linked list class where we're going to have two dummy nodes this is a pretty common pattern this basically allows us to not have to deal with as many edge cases and this map will map every value to the node so then we can identify it in constant time that's very important and this is basically part of the lru cache problem and we're going to have a few methods here one is the length we want to be able to get the number of nodes we've inserted so far are so and that will let us know if our list ever becomes empty because that's going to be important as I mentioned earlier there's a few operations we want to do to this linked list one is push to the right so every time we insert a new node we're going to push it to the right of the linked list we want to be able to pop from anywhere in the linked list because if we're removing a node we will want to do that popping left is basically popping the least recently used because we know on the left side is where the least recently used will be updating is kind of important if a node in the middle of the linked list was just recently used then we want to pop it from the middle and then push it all the way to the right because now it is the most recently used there are different ways to code this up so maybe there's a more concise way to organize this but this does work now for the lfu cache I have several variables here that I defined one is the capacity we're just going to be saving that one is the least frequently used count we have no elements so far so we're going to initialize that to zero one is the value map every time we add a key we want to map it to the value so basically then we can return it so in here in our key map I'm going to say return whatever the key we were given we're going to take our value map map it to the correct value and then return that but there was an edge case what if this key is not in the value map yet in that case we want to return a default value of negative one but every time we get a key value we want to increment the number of times that key has been used and that's what this counter is for this is like our helper function every time we call get on a key we want to also call the counter for that key every time we put on a key we also want to call the counter on that key so here before we return I'm going to call self.counter on this key value and now let's start actually filling in that counter what we want to do is first get the current count of that key and that's why we have this count mapped up above we're going for every value we want to map it to the count that it's been used we have a dictionary a hash map here the default value of that will be an integer that means if I do this right now so for that count map with uh the key what if this key has not already been inserted yet well this will then return a default value of zero now of course we want to increment the count of it so we're going to say to this account map for this key let's increment that by one this will do the same thing if the key wasn't inserted this will evaluate to zero adding one to zero we'll set it to one that's what we want to do but don't forget we also have a list map here for every key we want the count of every key and we're going to map that to a linked list where that key will be inserted when we're incrementing the count of this key we want to remove it from the previous linked list it was added to and then add it to to the new linked list we can do that pretty easily just like this so self dot list map for this particular count we want to pop this key value from it and now we want to add that same key value to the next list which is going to be at count plus one now what would happen if we tried to remove a key that wasn't even inserted into that list in the first place well I thought of that edge case and that's why we have this if statement here because otherwise you're going to get an error I learned that the hard way oh and actually this isn't going to be pop this is going to be push right because we're adding this key to the new list now lastly don't forget we are maintaining the least frequently used count so in which case would that ever be updated well if the current count of the key well the original count of the key was equal to the self.lfu count and now we removed it from that list map so how do we know if there's any more keys still left with this minimum count value well that's why we can just get the length of this list map so now if the list map length or we have a method I think it's called length let's double check yep it's called length over here just giving us the number of values added to it if this is equal to zero now in that case we will have to update the count the lfu count and it will now be plus one we're just going to add one to it now this was the original minimum count but now there's there's no other keys with that minimum count left so we have to increment it simple as that well not super simple that is the rest of that method and now we only have Push left this one's a bit tricky and there's another Edge case here that what if our capacity is equal to zero in that case we're not going to do anything and actually I called it cap it's possible that we initialize an lru cache with zero capacity and I just don't want to have to deal with that edge case so I'm just going to add an if statement here but every time we add a key value whether it's new or it's an old key value we want to say for the value map this key is now going to be mapped to this value whether it's a new key or an old key and we want to update the count for that key so we're going to call self.counter for that key which will end up updating the count map for that key and possibly now we might have to update our lfu count for we might have to update our least frequently used count in which case would we possibly need to do that when we're putting a key only if the count for this key is smaller than the current lfu count so an easy way to do that is just to take the minimum of self.lfu account and the count of this key that we just added did which we can get just like that now there are a couple edge cases here remember in the case that we exceed the capacity we have to evict some note how do we know if that's going to be the case well it's only going to happen if this key is not already in self dot value map meaning that this key has not already been added because if it's already been added then the capacity is not going to change at all but if it hasn't been added and now the length of self.val map which tells us how many keys have already been added is equal to the self dot capacity which you can now tell that this self.cap is going to be constant I'm the way I'm writing this code I'm never going to change it so the way I'm measuring if we ever get full is just by taking the length of the value map and comparing it to the length of the capacity or the value of the capacity if it gets reached then we know we're full and at this point we know we have to evict some value how do we decide which one to evict well that's exactly why we have ourself.lfu count we're going to take this count and map it to the linked list that has the values in it so we can do that just like this and now from this linked list we want to pop but we want to pop the least recently used we can do that with pop left and when we pop it I believe we are returning the value that we just popped that's going to be important because we're going to need it right now since we popped this value we have to now remove it from the self.value map I'm going to do that just like this self.value map dot pop this result value and also we want to remove it from the count map so we can also do that just like this and then I believe we are good to go whoops I had a typo here before we get the length of that list map we do have to map the count to the actual linked list and then we can call the length method that we defined up up above which just gives us the length of nodes that have been added okay now let's run this to make sure that it works and as you can see yes it does and it's pretty efficient you can probably tell just how much I love this problem I would hope in a real coding interview you would not have to Define an entire doubly linked list because this is quite a lot of code to write it's possible I believe to solve it with some built-in data structures but if this was helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon