LRU Cache Setup

[00:00:00]
>> Okay, awesome. Now the real question is, do I even have [LAUGH] it's like I plan this. All right, we have, really, three functions in which we need to actually fill out. We have an update function and we have a get function. So a get takes in a key and hopes for a value to come out.

[00:00:20]
An update takes in a key and a value and should update how we have everything set up. Now the thing is that notice that there's no insert, right? Cuz we don't know if you have the value in the cache. Now we're just gonna say, hey, update this thing, right?

[00:00:33]
If it's in there, move it to the front. If it's not in there, add it to the front. So we kinda need a way to be able to do both operations. A get will naturally move it to the front. So let's write out these pseudocode operations so we're not confused.

[00:00:46]
The first thing we need to do is, let's see, check the cache for existence. I think I spelled existence wrong, I never know if it's an e or an a. Existence, they both look correct me, I will never know. Don't correct me, please. Just accept it. Breathe in the correctness or incorrectness.

[00:01:07]
Okay, second, we update the value we found and move it to the front, right? Because now that we've used it, it is no longer the least recently used, it is now the most recently used piece of cache, right? Is most recently used or least recently used correct? I can't really tell which direction is supposed to be correct, I'm using the term most recently used as the newest possible used and least recently used as the oldest.

[00:01:38]
It's like turn the AC down or turn the AC up, do you mean you want the temperature more down, is that what you're trying to say? It's one of those confusing which way is the actual correct way. So I'm gonna go with the way I like to say it in my head, sorry.

[00:01:51]
Anyways, then lastly, we need to return out the value found or undefined if not exist, right? Pretty straightforward. I think we can kinda see that that one shouldn't be too hard. Let's talk about update now. Update's a bit trickier than get. Cuz the first thing we need to do is, does it exist?

[00:02:10]
So we can use that with get, right? So we can technically just simply call get, right? If we get the value out, well, guess what, it's gonna be updated. One tricky part is if we change the value right here, then we may not want to use that. Now, in some LRUs, we have this whole rule that if the key already maps to an item in the cache, we're not technically updating the contents of the cache, we're only updating its position within the list.

[00:02:34]
For us, we're gonna actually update the contents of the cache as well, assuming that it's meant to be changed, all right? So just in case someone suggest that as a tricky way like, look what I found. So first we have to find out it doesn't exist. If it doesn't, we need to insert.

[00:02:52]
But, of course, if we insert, what do we have to do? We have to check capacity and evict if over, right? If we've over done our capacity, we need to evict some item from the cache, correct? Correct, awesome. Let's see, let's see, let's see. If it doesn't, we need to insert it, yep.

[00:03:17]
If it does, we need to update to the front of the list and update the value, right? Makes sense? All right, awesome.