Implementing an LRU Cache

[00:00:00]
>> Okay, so we kinda have our written operations. So again, we need to start defining some of these types. So the first thing we'll do is just go type Node of value. Usually I use t as my over generic T. So I'm gonna have a value, which is gonna be T, we're gonna have a next which is gonna possibly be A node T.

[00:00:21]
And we're gonna also have a previous which will be A node T. Awesome, okay, we've defined our node structure. This is a doubly linked list, looks very familiar. this.length = 0 of course. Now we need to define our head and our tail, right? So private head, which really can be undefined, right?

[00:00:43]
There is no guarantee that it's gonna exist. Now what's our T in this case? Our T is the B, right? It's the value we want to store. Our linked list is the list of values, correct? Awesome. We do the same thing with tail. Okay, so we're starting to get through this whole idea here.

[00:01:00]
So this.head equals this.tail = undefined, I like to be super duper explicit here. Now, we need to define something else, right? What are we missing? Well, we're missing our traversal in the linked list. We're missing our instant lookup in our linked list, which is going to be our key to node, makes sense?

[00:01:21]
Yes, so let's put that thing in there. So we're gonna have to have a private lookup, which is going to be a map of key two node of V, right? That's the big trick right here. We have to have the linked list as the fundamental storage unit, right?

[00:01:42]
All right, and for convenience, I'm gonna add a quick function called Create Node, which is gonna take a value of V, and return out value, and this thing will be of course as a node B. Just make it super easy, cuz or else I have to do that whole as node if I do it in line, blah, blah, blah.

[00:02:06]
This just helps with the types. Fantastic. So we need to create that lookup. this.lookup equals new map, as of course, a K and a NodeV. There we go, we now have that but we're still missing one thing. What's the thing we're missing?
>> Capacity?
>> Capacity, awesome job.

[00:02:24]
Yeah, we need a capacity. How many items do we wish to have inside of our cache? So capacity, which is gonna be a number. We cannot exceed this capacity. This is the capacity of our LRU. Go forth and evict, right? So there we go. We have everything we want right now.

[00:02:44]
For fun, I'll put a little = 10 here just in case my unit test just assumed it was 10. I don't remember what I wrote for my unit test. So there we go, I covered both conditions there. So now we have the length, how many items we have in the cache, we have the head and tail being undefined.

[00:02:56]
We have the lookup being the map we're gonna use to look up from the key to the value. Are we missing anything else? I felt like I had a second map. I'm gonna probably go, probably not, right? We probably don't have a map. We'll find out. Actually, we do have a second map.

[00:03:12]
What's the second map? The second map, of course is gonna be, what happens when we evict, right? How do we find out what key was stored for our lookup? Right? We have to be able to clean up all of our data. We're gonna know what node to remove, but we won't know what key is associated with our node that is used as part of our lookup.

[00:03:38]
That means our lookup will just sit there and infinitely leak memory, or even worse give us wrong results and actually store those results indefinitely. So we need a reverse lookup, right? Classic blunder, again, land war in Asia, just don't do it. So we need to be able to go from a node back to the key, delete that out, then delete out the key that is in the lookup.

[00:04:02]
Does that make sense? Again, why would we ask this question in an interview? I want you to riddle me that one. This is pretty complicated, right? All right. So there we go we have this go reverse lookup equals new map, and of course I'm just gonna yank everything in between there because I really don't wanna write it again.

[00:04:19]
Paste that, and do that and K, awesome. So we have the lookup, we have the reverse lookup, we have the head, we have the tail, we have the length, and everything is set for us to be able to do these operations. Is everyone ready? All right. So I'm gonna start with get, cuz get is really, really simple, right?

[00:04:41]
So first, let's check for existence, all right. const node = this.lookup(key), right? So if, my goodness! Yeah, yet I forget. You gotta use it like that, right? So if this thing doesn't, what kind of indenting was that? If this thing does not exist at this point, what happens?

[00:05:04]
Well, we can't get this for you, right? Sorry, it doesn't exist. We can't do anything at this point. So return undefined, awesome. But what if we do find a value? Well, we've to follow these steps. We need to update the value that we have found, and by moving it to the front, correct?

[00:05:24]
All right, so that is the unfortunate move we now have to do. We now have to do those sweet linked list operations. So we can do some kind of checking to make sure how this thing is going, so we're gonna have to kind of give me a bit of playing here.

[00:05:37]
So, I'm gonna have let's have a detach function, right? Call this thing private detach, right? And we'll pass in a node that is of a value, right? We're just gonna simply detach this node from our linked list. And then we could also have a private prepend, right? And this will take in a node and then do that.

[00:06:01]
It's kinda for me, it's a lot easier to break up these operations, as opposed to trying to be like okay, we're gonna do this, this, this. Cuz then you just get a huge wall of nexts and previous, and all that kind of stuff. For me it's a little bit harder to accomplish this, first try.

[00:06:15]
So that means what we're gonna have to do is we're going to have to detach the node. To detach the node. All right, it's now no longer on our linked list, but it's still in our lookup, it's still in our reverse lookup, which is good. Then we have to this.prepend, add it to the front.

[00:06:32]
Everything's good, everything's great. I feel like that's gonna be pretty easy to program. I'm sure there's some shortcuts we could take that would reduce the amount of lines of code by having those two functions put together. Cuz we're gonna have this whole tail and head check that goes on for some of these, but right now we don't care.

[00:06:48]
All right, lastly, we need to return out the value or undefined if it not exist. We already did that eight line ups. So therefore we're gonna just return out node.value. Right here. There we go, we just did get. Get was actually not all that hard, right? Well, I don't think it was all that hard.

[00:07:06]
All right, so now let's do update. So first we need to check does this thing even exist? So we'll do the same thing we did right here, and just go bam, right? Does this thing even exist? We're gonna go look for it. Now what if it doesn't exist?

[00:07:21]
What do we do? Well, it's simple, right? Now we need to come in here and we need to be able to create a new node, right? So node = createNode, and we need to create it with the value, right? There we go, we've now created the node that didn't exist.

[00:07:42]
But if it does exist, we have this whole thing we have to do, right? Or we have to do this side, right? We have to do these two sides. So if it does exist, let's do that one cuz that's honestly easier. If it does exist, we just simply need to move this to the front of the list, right?

[00:07:58]
So again, this.detach(node), this.prepend(node), we've just moved it to the front, everything's great, the end, correct? It's this one that's the trickier one. Now we need to adjust the length of how many we have, we need to prepend it, then we may need to delete from cache. So let's go like this, this.length ++, add one to our length.

[00:08:24]
this.prepend, our node we've added it to the front. And then of course, this.trim cache. I'll just call it trim cache, right? It's a function in which will ensure that our cache remains no greater than our capacity. Sounds good? Yeah, sounds great. Awesome, all right. So let's do one more, private trimCache.

[00:08:45]
We're gonna say, void. Look at all those proper, proper function definitions right there. These two don't have voids on them, very disappointed by myself. All right, so now we just simply need to do each one of these operations. So we can start first with detach. Which is gonna simply need to kind of remove out the links, place it right here.

[00:09:05]
So the first thing we need to do is I could do something as simple as this. If node.prev, then nodes.prev.next = node.next, right? We've went backwards and say hey, backwards forward must be our forwards, or must be our forward, right? Did the whole thing, which of course is this operation right here.

[00:09:26]
We went back to this thing and pointed its next, not to us but to the one ahead of us, awesome. Do it again the other direction. So if our next exists, then our next.prev must be our current node.prev. So again, we go to our previous, we already did that direction.

[00:09:50]
We go to our next previous which is pointing here, and say no, point over here, right? Our next previous needs to point to our previous, yeah. I wish there was more words I could say, it feels like it cuts off too soon. All right, so there we go.

[00:10:04]
So we have our previous in our next conditioning. So we've now removed ourselves effectively from the graph. Now all we have to do is break our links pointing to the ones that are still within that linked list. I call it a graph, or linkless graph. Yeah, they're totally graphs.

[00:10:21]
They're just all in a big line, right? That's just the whole big line, of course I'm right. All right, so node.next = undefined, node.prev = undefined, right? Did I do this correctly? Yes, I really do think I did this correctly, but there is, of course, the tail and the head checking that we need to figure out, right?

[00:10:41]
So there's a couple different ways in which we can approach this. One way we could approach this is we could always have this.length = 0, right? Or if this.length = 1, well, that means our length is now 0 for a moment, which means that our head and our tail should become undefined, right?

[00:11:03]
Detached does not alter length, it just simply detaches it from the graph. So in a real sense, this.tail needs to become this.head, which needs to become undefined, right? That makes sense. The problem is, of course, is if this.head === node, the thing we are removing is our current head.

[00:11:26]
If that's the case, this.head = this.head.next, right? We need to shift our head over one before we break all the links. Cuz if we break all the links, we just cut off our own head. Nobody wants to be discombobulated like that, that'd be just terrible! Again, this.tail, again this worst circular linked list could come in handy right here.

[00:11:48]
This if our tail is the node then this.tail = this.tail.prev, awesome. Does that sound good? Yes, awesome. So another thing we do is, if you think about this right here, if this is true, if our length is 1, quick question. Is head next gonna be undefined? Yes, it is.

[00:12:15]
Is tail.prev gonna be undefined? Yes, it really is. Which means we don't even need that check, right? We're simply gonna just remove the links, by accident, everything is great, there we go, we just did it. So, now we have detach effectively written, pretty happy about that. I'm feeling pretty good about this.

[00:12:34]
And so, we need to do the next one, which is prepend. We add it to the front of the list. So let's do some simple checks. If this.head, if there is no head, then this.head = this.tail = node, right? If there's no head, there's no tail, now we have a head and we have a tail, all right.

[00:12:57]
So if that's not the case, then we need to do something slightly different, right? So I'm gonna just do a little quick return right here. And we this simply take the head, we need to point to it, then have our head points to the node we're adding, and then move the head to where we're at, right?

[00:13:15]
So Step one, let's point to the head, node.next = this.head. Awesome, right? Next, our head needs to point to node, right? Or our head.prev needs to point to node, so there we go. So if you saw A at the front of the list and we're now adding Z, Z points to A, A points to Z.

[00:13:39]
Now we just simply need to have our head point to Z. So this.head equals node. There we go, all right? So I believe we have prepend correctly. Now the last one is gonna be the tricky one. We're going to make some assumptions here. If this.length is greater than this.capacity, well, we need to do some removals.

[00:14:01]
So let's just swap this thing around. If length is less than or equal to our capacity, we can return else. Let's remove the tail. So the first thing we need to do is we need to remove the tail, right? So we can go like this. Const tail = this.tail.

[00:14:18]
We hold on to a reference to our tail, and then this.detach, remove our tail from the graph, right? There we go, we've now removed, oopsies. As, I mean we already know this is true, right? We did the check right here. We already know this is true. Typescript's like, well, I don't know what.

[00:14:40]
We're like, but we do know. I'm sure there's a sweet TypeScript. I've seen what TypeScript does, and I'm sure there's a way to make this true. All right, so there we go. We have that, we now have the tail completely removed from our linked list, but we don't have it removed from our lookups.

[00:14:59]
So we can go const key = this.reverseLookup.get(tail), right? So we're gonna get the, my goodness, as node V, yeah. There we go. That should be totally not undefined, dang it! I thought that was gonna work, I thought it was genius, I thought that always works. I don't even know.

[00:15:23]
Do I have to do this one? Sorry, this is just a TypeScript moment of me just sucking. Man, I can just hear TypeScript has gone, [SOUND] don't do it. All right, there we go. So we go and do a reverse lookup of our tail, it does work, we get our key out of here.

[00:15:40]
There should never be a moment in which that key doesn't exist, or we have severely messed up our insertion, right? When which we currently have, but we'll get there. So we'll just do this as k, right? It is the key. Next, we'll take this and go this.lookup.delete(key), awesome.

[00:16:02]
This.reverse lookup.delete(tail). There we go, we have now deleted everything out, we've detached our tail. We're fully ready to go, awesome. The only thing we have less to do is that length needs to be reduced by one, cuz we have fully just trimmed the cache. Everything's good to go, we've done it, awesome.

[00:16:22]
Last thing we need to do, which I just realized right now, is inside of our update method right here. Or what did we not do? We prepend, we trimmed the cache, but we don't have ourselves a beautiful update our lookups, right? So this.lookup.set of course is gonna be the key we want to use, plus of course, the node we're gonna be inserting.

[00:16:48]
And our reverse lookup is going to have to be this node, right? We're gonna do a reverse.lookup.set(node, key), right? Awesome. And then I also realized this one other part right here, is that we actually didn't update the node's value. So node value needs to equal the new value that's passed in, just in case the value has been changed, we don't know if the value has been changed.

[00:17:12]
You can see right above me the update function takes in a new value, right? Fantastic, so I believe we have finished programming our entire LRU at this point. How does everyone feel, pretty good about this thing? [LAUGH] Yeah, like really good? Okay, we got sturdy head nods going on right now.

[00:17:32]
And no one would ever lie to me. So we know for a fact that this is good. All right, just LRU. We're gonna run it. My goodness, we got it first try, that was actually. I have impressed myself, because the test is actually fairly lengthy, right? We got 69420s in there, all sorts stuffs going on in here.

[00:17:55]
So we did properly actually do all this stuff. There you go, that is an LRU. It's the combination of two data structures. We understood, a map plus a linked list to be able to create something that can actually cache data, and this is something that we use at Netflix.

[00:18:07]
This is something I had to build, spent many years crafting and building this thing. So again, these data structures are things you will eventually run into as you build libraries. Now if you're just doing UI components, if you're just doing something light, you're not gonna probably run into these things.

[00:18:22]
But the moment you cross the boundary from just simple UI features into something that the UI uses, you will often run into any of these things.