Hi, everyone, welcome to this new video.
So in this video, we are going to solve one very important question, which is a location in a location.
So what happens is you are provided with the capacity.
So let's say the capacity of your cachets for academics, it can store four elements.
Right.
So first element you can insert because the capacities for second element, you can insert a third element.
You can insert for element, you can insert.
But now here comes the fifth element, Nate.
So here comes the fifth element.
Now what will happen?
So what it does, it basically delete it, delete the oldest item.
So what is the oldest item or list?
Item is item one, but this item will be deleted.
Right?
So the capacity was for it.
And you inserted four elements initially.
So your allocation is full.
Now here comes the fifth element.
So avoid inserting the fifth element.
What a does is it will be the oldest item.
So all this item is one.
So now I have one space left and that space can be given to five.
Right.
So again, your allocation will become full.
Now here comes the next element, which is six.
So again, this element will be deleted.
So the capacity will remain, capacity will remain same.
But the number of elements stored in the allocation will decrease by one.
And then you can store six and after storing six and education will become full.
So that is the meaning of LRU.
What it does is it deletes the least recently used item and one of the functions that we need to implement.
So we need to implement the capacity function, which is nothing but deconstructed.
So capacity of the allocation will be passed to us in the constructor.
And then we have a function.
This guide, for example, return value and this function is it takes and value added, Stoll's them
together.
So we need to basically implement these three functions.
So let's take one example and let's try to understand how alirocumab works.
So let's see.
So let's take one example.
Let's say the capacity of your allocation is two and let me write some port and get operation.
So put Kiva loopier.
Then the next operation is again put let's say, five government.
Well, then let's say the next operation is get operation, get the value corresponding to five, get
the value corresponding to give one, get the value corresponding to the then bought or sold on the
same thing, let's say six and 14.
Then let's say I want to get a value five get value corresponding to five.
So what will be the output.
So how allocation works.
So it's very, very simple.
So the capacity is too right.
So you will maintain a map and you will maintain list.
Right, you will maintain a map and you will maintain a list, so in this list, the first item.
So the first item is basically the latest item.
First item is the latest item and the last item will be the oldest item, right?
And we will have a map to store given loopier simple.
So that's how we implement a location.
So let's see what will happen in this example.
So the capacity is to OK, fine now, but one in 10.
OK.
So I want to put one in ten.
But I will do I will go to this map and I will store one and then.
And also in this list, we actually we will stalky, right?
So my list of Rite Aid, let's write it here only.
So this is the first element, right?
So I will.
Stalky.
Fine.
Now, let's go to the next operation.
So next operation is again put five in total.
So I will store five and 12 here, which is fine.
And the value is Ghys five.
So I will store five here.
To remember the property of the list, the properties, the first index, the first element of the store,
the latest and the last to the store, the oldest.
And then this order right from the test to all list.
I restore the element in this order in that list.
So according to this order, five must be inserted before one.
Fine.
Now the next is we have get operation, get five rate, so get five for it.
I will do I will check in the map.
Five percent.
Yes, five percent return the value twelve.
So I will return the value to L and also five is the latest element that I am accessing.
So what I need to do, I need to put five in the beginning because in the beginning we need to put the
latest.
Five is the latest here.
So five is already in the beginning.
So then get one.
So one is present in the map and the value is ten.
So I will return ten.
Now is the latest element, right, when is the latest, Alvin?
So what I will do, I will remove one from the list wherever it is.
Besant So I will remove one wherever it is in the list and I will put one in the beginning.
I will put one in the beginning because what is the property of list letters to all list.
And the latest element is one right now.
The next element is get them.
So I will check in the map.
Give then is not present.
I have boogies went into five, so 10 is not present.
So I will not present or I will return some invalid value, for example, minus one.
Right now the next value is put six and 14.
So I will go in the map and I am going to store six and 14 and the latest element is six.
So what I will do, I will store six in the beginning.
But this is wrong, why this is wrong, because we have capacity, too, and you are inserting three
elements, right?
The capacity of your allocation is only to and here you are having three elements in your list, which
is wrong.
Right.
Which is wrong.
So I told you what Larry will do.
It will delete the list item, a list item to create space.
And the whole list item is the item which is present at the last in the list.
Right.
So which item is present that last five is present at last.
So you will delete the last item from the list and obviously from m'appelle to.
Right, obviously, from the map now, this is your list six and one right now what I'm doing, get
five, so I will check in the map.
FIFA's president no, FIFA's not present.
So that's why the output will be minus one.
Right.
So that's how LRU cash works.
So for implementing it.
Okay.
What do you need.
You need one map and you need one list and you need to make sure that in the list we have order of elements
from starting from basically attached to the list such that whenever we cross the limit, whenever the
size of the list increases, we can delete the last element.
Right.
So that's how this basically allocation is implemented.
So one example is already provided to us in the commission.
And let's try to see how this example will work and whether our approach is correct or not.
So let me again write.
This will be our map.
Right.
And this will be my list from the latest to on list.
And liquidate all the operations, so LRU, that means I'm calling the constructor, that is, I am
passing the capacities or the capacities to.
So let me right.
The capacity of LRU cachets two, which is fine.
Now, I have put and put two times put operation put and put and are reporting one on one to one and
one.
Then next is.
And so to commit to this is one, next is get operation, get one.
So get one next operation is again, put support and develop that entry.
So give a loopier three and the next operation is get so get.
And I'm calling it on to so get the next operation esport so forth and for enfold so for Khama for next
operation is get.
So I am writing here.
Get.
Get and get two times to get, so get, get and get.
And the values are one, three and four, so the values are get one, get three and get four, right.
So let's see how this will work.
So first of all, I have capacity to very good.
Then put one in one.
So I will go in the map and I will put one and one.
Also, you need to insert one.
I will store only cookies.
Right.
This is case.
I will store keys in the list.
So I was told one.
Now the next is put to Clamato so I will store to when doing the map and two is the latest element.
So I will insert two in the front of the list.
Now I have a great operation, get one, so get when there is one president minus the map and the value
is when.
So the value is one that I will return when and since when is the latest element.
So you will remove one from the list and they will put one in the beginning, because one is the latest
element that I am accessing.
Next is basically three comma three.
So check.
I am inserting Tecoma three and three is the latest element, so I will put three in the beginning.
But again, this is wrong because the capacity of the allocation is too.
And we have three elements.
So what do we need to do?
We will delete the last element, delete the oldest element and the oldest element is present at last.
So three one, two, two is the last.
So I will relate to I am deleting two from the list.
You need to also delete two from the map.
Right.
So this is successful now.
Three entry.
Now the next is get two.
So I will check in the map.
Two is not present so I will return minus one.
Two is not present.
So I will return minus one.
Now the next is booked for four so I will store for my four in the map.
And forward is the latest element that I am accessing.
So I will put forward in the beginning.
But now my list contains three elements and the capacity of a location is only two.
So you need to delete the last element.
And the only element is basically the element which is present at last, which is element one.
So remove element one from the list as alleged from the map.
Right.
So put four and four is successful now get one.
So one is present in the map.
No one is not present.
So this will be minus one.
Get three to use present.
Yes, the output is three, only four is present.
Yes.
The output is for only.
Right.
And this operation we will not return anything that way.
They are written rate.
We are not returning anything.
So that's why they are writing null.
And similarly for this capacity we will not return anything.
So normal rate again.
The operation so null again.
Put operation so null here also.
And let me check so we have null null initially evolutional so null then I have one null minus one and
so when null minus one and now I have minus one, three four I have minus one, three, four.
And that said, so basically our approach will work.
And let me summarize what is our approach.
So our approach is very simple.
I will have one map and I will have one list list of keys and I will store in this order from the test
to our list and then write nothing else.
So if you want, you can try writing the code for this problem yourself.
But in the next video I will be writing the code.
So if you want to try coding this problem, do give it a try.
Otherwise you can watch my solution in the next video.
So I will see you in the next one.
Thank you.