Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)

Key Takeaways

[Music] alright so in this video today we are going to talk about an apparent Microsoft question I don't know if other companies ask this but implement and LRU cache so first off let's get started with terminology what is LRU and what is a cache LRU stands for at least recently used it is a cache eviction policy when we have a loose collection of items and we want to remove items in a certain order a restricted order remember how we have LIFO first at the last item to go in is the first item to come out for a queue the first item to come in is the first item to come out the least recently used if a similar policy to the FIFO policy except it's you where you can get point of cash so here's an example say we have one two three four in a cache and it is sized for say I want to add another item zero so let me add zero so when we add zero we add it to the front of the cache what this shows is the temporal order of access to items access this item most recently this height of second most recently this item third most recently and what happens is this cache is restricted to a size of four a capacity of four it is a five we need to evict an item and what we understand is that our eviction policy is using the least recently used what is the least recently used item the least recently used item is four so what we do is we evict four from the cap and so now this is our new cache this is our new order of items and now let's access item number two and see what happens so what happens when we access to is that abuse to the front of our cache it is the most accessed item so what you notice is when we access an item used to the front of the list when we go over in size we need to remove an item we ruined at least recently used where will the item be is going to be at the tail of our list the end of our list and the verb I'm using is starting to hints to you the kind of data structures we'll use we'll get into that soon what is it cash you probably are familiar with this if you already are watching this a cash is just something that stores computations so that look up later can be served very quickly and not just computations but also it can store redundant data so that we have quick access to it instead of reaching out to the database instantly it could be many things but the whole point is to speed up future requests for whatever resources that are being asked for what is it LRU cache now now that we've covered LRU we cover in the cache so an LRU cache is a cache will often have a finite capacity and we use the LRU cache eviction policy now let's see our constraints and see how that hints to us how we're going to solve this problem so now imagine getting this problem in an interview and you don't really know what data structures you're going to use you don't really know how we're going to approach this problem let's just look at the requirements that are asked of us we need to support an API of two functions we need to support a get operation which is where we get an item from our cache and we need to support a put operation where we add an item to the front of the cache and we evict the least used item if we hit capacity if we've in capacity and we're going to use the LRU eviction policy if we go over capacity we're gonna remove the least used item keep in mind we're going to need to know where what where that item is we need facts fast access to it we need to be able to get an item in constant time and we need to put an item in constant time these are our constraints for time complexity for space complexity we can go heavy with it and you'll see that this is kind of a space heavy approach which with event space here are the two things we need we need fast look ups and we need backs removals and if you've taken a data structures class have you've done any study on this you might be getting a light bulb in your hand right now when we reduce it to these constraints we know we need these things from this structure we're being asked to build so fast look ups what data structure can help us with that I think great thing my brain goes to is a hash table whatever we're trying to do fast lookups hash tables will allow us to use a set of keys where we can hash them and have fast lookups based on those keys and our hash function that we define we want fast lookups hash table okay but there's another problem how are we going to know where the least recently used item is the last item and how are we going to remove items quickly how are we going to do that maybe we could use a binary search tree that has elevate search time maybe we could use some other structure like an array so just start thinking through data structures in your head another thing that comes fast to my mind when I think of fast removals I think of a doubly linked list and this is for two reasons one if we have instant access to a doubly linked list node we can remove it in constant time because I can touch my next node I can touch my previous node and I can remove myself if it were a singly linked list I won't have access to my previous and it would take all event time to find my previous okay so doubly linked list that makes sense we're going to be able to remove in constant time and another thing is we're going to be able to prevent ourselves from having to resize an array if we use the linear structure like an array for this if we remove an item we need to shift all the elements over with a linked list it's just an abstraction of pointers and we don't need to shift items so it prevents us from doing linear work during resizing because we we don't need to resize a linked list it's an abstraction of pointers between objects doubly linked list looks very good for this problem and a hash table looks very good for this problem and what you'll notice is this is a Araki pattern backing up a special data structure with the properties that we want backing it up with a hash table for fast access into that special property data structure so say we use a binary search tree but we don't want to spend all of each time searching we can back it up with a hash table so always keep this in mind that a hash table is very nice for fast lookups on a special property data structure our special data structure here is our doubly linked list and our hash table is our fast lookup thing that backs us up so now look at the approach you're going to take alright so what we're going to do is we're going to use a doubly linked list backed by a hash table we're going to run through a list of actions whatever we choose a node understand that a hash table is backing that fast lookup if we didn't have the hash table we would potentially do all event operations to find an item but we're just going to act as if we have a hash table to back us up and we're gonna walk through an example and also the code is in the description it is not my code but I heavily commented and reformatted someone else's code to make it very very understandable and internalized Abul so that is in the description so let's walk through this example alright so we're going to walk through this list of actions remember we have constant I'm forget and in constant time for put operation the overall space we're going to use is all of n where n is the capacity we're going to evicted item if it goes over capacity and we're going to be storing an item so this is a space happy thing but at the same time to get fast look ups and fast flip operation so let's begin our capacity is 5 if we go over capacity we have vikt the least recently used item so what we're going to do is we're going to put 1 1 the key of 1 the value of 1 we're going to put that in our list so before we start anything we want to initialize our list with a dummy head and a dummy tail pointer so this is our initialize list we have a dummy head and a dummy tail or capacity is 5 our size is 0 right now what we're going to do is we're going to put the key of 1 and the value of 1 so we're going to put that into the list okay so now we have inserted 1 into the list and now our nesic it next command is put to 3 so let's insert to 3 into the list ok and now we had inserted to 3 so notice when we insert an item it goes to the front of the cache it is the most recently added or accessed item which is at the front and he notice the items that haven't been touched will slowly float towards the back and they're eventually going to be evicted we have these two eye so now let's add 3/4 okay so now we just added 3/4 again 3/4 goes to the front of our cache and now we have 3 4 2 3 1 1 and notice that the top-left corner is our keys and the sting inside is our value we look up by the keys so just keep that in mind so now we're going to add the item 4 7 so let's add 4 7 now we have added the item 4 7 again we added it to a front of our cache we have 4 key the key for key 3 key to key 1 this is our list and now we need to add 6 10 okay and now we've inserted the item to the front of our list notice when we put an item if it already exists we just update the value we have it add any values keys that already existed so we just add them to the list add it to the front of our list and now we have a get operation so we're going to get the value with the key 1 so we're going to retrieve this item and our hash table will allow us to do this in constant time we're gonna have instant access into our list without having to start from the front and traverse all the way up to the key 1 we can retrieve this item and it's going to move to the front of the list because it's just then access okay so we just access one one who is at a tail a borderless we move it to the front of our list we have constant time insertion and deletion from our list or constant time removal and then replacement in our list and we also are able to quickly find an item with our hash table so now we've done this and now we need to get to the item with the key 3 doesn't exist and yes it does we know it exists in constant time so we move this to the front of our list okay so we just accessed three four and now reduce to the front of our list item with the key 3 so now yeah this is this we still are at capacity five we have not needed to exercise our addiction policy so our next operation is we need to put 1 5 we notice that this is the key already in the list so since it is already in the list we're just going to update its values but every time we interact with a node whether we update its value the foot or we get it we need to move it to the front of the list because it was just interactive anytime you interact with a node it was the front of the list so let's move this to the front all right so we updated the value of the note of the key 1 and we moved it to the front of our list the thing is you see these keys but in reality the hash table would be keeping the keys the notes would just be their nodes with their values we wouldn't need to keep the keys on their nodes we could but the hash tables job is to keep the keys this is just for demonstration purposes now we need to look the item 12 7 does that exist in the list no but does not is going to move to the front but we're going to go over capacity we're going to go over the capacity of 5 so we're going to need to evicted item what item do we evict we remove the last item the least recently used item which is sitting at the end of our list so we're going to have instant access to that item so we could just remove this item and then we're going to add this to the front of our list so let's do that so now we have just added the other 12 with the key 12 with the value 7 we've added it to the front of our list we are still at capacity 5 where then we're within capacity so we're going to put 5 to does 5 already exist in our list no it does not we're going to add it to the front we're going to remove our last entry which is the least recently used item we added the item we added the item to the front of our list and now we're still within capacity and now we perform our last operation and we're going to get the item with a key of 4 but the problem is notice that we just removed the item with the key of 4 so we're going to either return null return minus 1 whatever we want to do to signify an empty state and we are basically if finish we can't get the item 4 because it just was removed so this is how the LRU cache works this is what happens whenever we interact with an item that goes to the front of the list we want to remove the least recently Center entry and this kind of a temporal order of the usage of items and is very useful for certain things and remember the code is in the description I have commented every single line of that code walk through that code look through it it's very intuitive it follows the same as our example and really let that let it internalize these concepts so it's in the description go check that out basically this is the video if you like this video hit the like button subscribe to the channel I'm trying to do videos like this every day to help prepare other engineers for the interview that's what this is about so [Music]