1
00:00:01,080 --> 00:00:03,000
Hi, everyone, welcome to this new video.

2
00:00:03,150 --> 00:00:09,510
So in this video, we are going to solve one very important question, which is a location in a location.

3
00:00:09,870 --> 00:00:13,070
So what happens is you are provided with the capacity.

4
00:00:13,080 --> 00:00:18,570
So let's say the capacity of your cachets for academics, it can store four elements.

5
00:00:18,900 --> 00:00:19,260
Right.

6
00:00:19,710 --> 00:00:26,400
So first element you can insert because the capacities for second element, you can insert a third element.

7
00:00:26,400 --> 00:00:28,860
You can insert for element, you can insert.

8
00:00:29,040 --> 00:00:32,290
But now here comes the fifth element, Nate.

9
00:00:32,520 --> 00:00:34,960
So here comes the fifth element.

10
00:00:35,010 --> 00:00:36,090
Now what will happen?

11
00:00:36,120 --> 00:00:42,370
So what it does, it basically delete it, delete the oldest item.

12
00:00:43,980 --> 00:00:45,930
So what is the oldest item or list?

13
00:00:45,930 --> 00:00:49,980
Item is item one, but this item will be deleted.

14
00:00:51,070 --> 00:00:51,540
Right?

15
00:00:51,720 --> 00:00:54,330
So the capacity was for it.

16
00:00:54,330 --> 00:00:56,310
And you inserted four elements initially.

17
00:00:56,310 --> 00:00:58,200
So your allocation is full.

18
00:00:58,710 --> 00:01:00,360
Now here comes the fifth element.

19
00:01:00,540 --> 00:01:02,380
So avoid inserting the fifth element.

20
00:01:02,400 --> 00:01:05,140
What a does is it will be the oldest item.

21
00:01:05,340 --> 00:01:06,940
So all this item is one.

22
00:01:07,170 --> 00:01:12,390
So now I have one space left and that space can be given to five.

23
00:01:12,990 --> 00:01:13,340
Right.

24
00:01:13,440 --> 00:01:15,600
So again, your allocation will become full.

25
00:01:16,200 --> 00:01:18,570
Now here comes the next element, which is six.

26
00:01:19,170 --> 00:01:22,350
So again, this element will be deleted.

27
00:01:22,650 --> 00:01:26,040
So the capacity will remain, capacity will remain same.

28
00:01:26,370 --> 00:01:30,150
But the number of elements stored in the allocation will decrease by one.

29
00:01:30,300 --> 00:01:35,520
And then you can store six and after storing six and education will become full.

30
00:01:36,450 --> 00:01:38,250
So that is the meaning of LRU.

31
00:01:38,280 --> 00:01:45,850
What it does is it deletes the least recently used item and one of the functions that we need to implement.

32
00:01:46,020 --> 00:01:49,740
So we need to implement the capacity function, which is nothing but deconstructed.

33
00:01:49,890 --> 00:01:53,580
So capacity of the allocation will be passed to us in the constructor.

34
00:01:53,970 --> 00:01:56,210
And then we have a function.

35
00:01:56,250 --> 00:02:01,710
This guide, for example, return value and this function is it takes and value added, Stoll's them

36
00:02:01,710 --> 00:02:02,140
together.

37
00:02:02,160 --> 00:02:05,190
So we need to basically implement these three functions.

38
00:02:06,330 --> 00:02:10,650
So let's take one example and let's try to understand how alirocumab works.

39
00:02:11,250 --> 00:02:12,090
So let's see.

40
00:02:13,470 --> 00:02:15,300
So let's take one example.

41
00:02:15,450 --> 00:02:21,930
Let's say the capacity of your allocation is two and let me write some port and get operation.

42
00:02:22,330 --> 00:02:25,470
So put Kiva loopier.

43
00:02:26,310 --> 00:02:29,960
Then the next operation is again put let's say, five government.

44
00:02:29,980 --> 00:02:37,920
Well, then let's say the next operation is get operation, get the value corresponding to five, get

45
00:02:38,040 --> 00:02:46,890
the value corresponding to give one, get the value corresponding to the then bought or sold on the

46
00:02:46,890 --> 00:02:49,400
same thing, let's say six and 14.

47
00:02:50,130 --> 00:02:56,860
Then let's say I want to get a value five get value corresponding to five.

48
00:02:57,420 --> 00:02:58,640
So what will be the output.

49
00:02:58,920 --> 00:03:00,490
So how allocation works.

50
00:03:00,990 --> 00:03:02,970
So it's very, very simple.

51
00:03:03,810 --> 00:03:06,330
So the capacity is too right.

52
00:03:06,910 --> 00:03:12,270
So you will maintain a map and you will maintain list.

53
00:03:14,880 --> 00:03:20,170
Right, you will maintain a map and you will maintain a list, so in this list, the first item.

54
00:03:20,910 --> 00:03:25,110
So the first item is basically the latest item.

55
00:03:26,040 --> 00:03:33,330
First item is the latest item and the last item will be the oldest item, right?

56
00:03:33,330 --> 00:03:36,800
And we will have a map to store given loopier simple.

57
00:03:36,810 --> 00:03:38,570
So that's how we implement a location.

58
00:03:38,580 --> 00:03:40,800
So let's see what will happen in this example.

59
00:03:40,830 --> 00:03:45,570
So the capacity is to OK, fine now, but one in 10.

60
00:03:45,600 --> 00:03:45,990
OK.

61
00:03:46,020 --> 00:03:48,030
So I want to put one in ten.

62
00:03:48,040 --> 00:03:53,070
But I will do I will go to this map and I will store one and then.

63
00:03:54,220 --> 00:04:00,200
And also in this list, we actually we will stalky, right?

64
00:04:00,250 --> 00:04:04,630
So my list of Rite Aid, let's write it here only.

65
00:04:04,660 --> 00:04:06,180
So this is the first element, right?

66
00:04:06,190 --> 00:04:06,610
So I will.

67
00:04:06,610 --> 00:04:07,210
Stalky.

68
00:04:08,500 --> 00:04:08,890
Fine.

69
00:04:09,430 --> 00:04:11,370
Now, let's go to the next operation.

70
00:04:11,710 --> 00:04:14,170
So next operation is again put five in total.

71
00:04:14,500 --> 00:04:18,820
So I will store five and 12 here, which is fine.

72
00:04:19,180 --> 00:04:21,670
And the value is Ghys five.

73
00:04:21,910 --> 00:04:24,040
So I will store five here.

74
00:04:25,770 --> 00:04:32,410
To remember the property of the list, the properties, the first index, the first element of the store,

75
00:04:32,410 --> 00:04:34,650
the latest and the last to the store, the oldest.

76
00:04:34,660 --> 00:04:39,700
And then this order right from the test to all list.

77
00:04:39,700 --> 00:04:43,020
I restore the element in this order in that list.

78
00:04:43,570 --> 00:04:46,900
So according to this order, five must be inserted before one.

79
00:04:47,440 --> 00:04:47,810
Fine.

80
00:04:48,040 --> 00:04:54,760
Now the next is we have get operation, get five rate, so get five for it.

81
00:04:54,760 --> 00:04:56,310
I will do I will check in the map.

82
00:04:56,320 --> 00:04:57,120
Five percent.

83
00:04:57,130 --> 00:04:59,620
Yes, five percent return the value twelve.

84
00:05:00,040 --> 00:05:07,690
So I will return the value to L and also five is the latest element that I am accessing.

85
00:05:07,990 --> 00:05:13,210
So what I need to do, I need to put five in the beginning because in the beginning we need to put the

86
00:05:13,210 --> 00:05:13,830
latest.

87
00:05:14,080 --> 00:05:15,330
Five is the latest here.

88
00:05:15,430 --> 00:05:17,740
So five is already in the beginning.

89
00:05:17,740 --> 00:05:19,890
So then get one.

90
00:05:20,980 --> 00:05:24,100
So one is present in the map and the value is ten.

91
00:05:24,100 --> 00:05:25,420
So I will return ten.

92
00:05:26,860 --> 00:05:31,770
Now is the latest element, right, when is the latest, Alvin?

93
00:05:31,790 --> 00:05:35,800
So what I will do, I will remove one from the list wherever it is.

94
00:05:35,840 --> 00:05:42,670
Besant So I will remove one wherever it is in the list and I will put one in the beginning.

95
00:05:43,420 --> 00:05:49,300
I will put one in the beginning because what is the property of list letters to all list.

96
00:05:49,300 --> 00:05:53,320
And the latest element is one right now.

97
00:05:53,320 --> 00:05:55,660
The next element is get them.

98
00:05:55,960 --> 00:05:57,190
So I will check in the map.

99
00:05:57,370 --> 00:05:58,630
Give then is not present.

100
00:05:58,720 --> 00:06:02,440
I have boogies went into five, so 10 is not present.

101
00:06:02,740 --> 00:06:07,330
So I will not present or I will return some invalid value, for example, minus one.

102
00:06:08,500 --> 00:06:12,910
Right now the next value is put six and 14.

103
00:06:12,910 --> 00:06:21,630
So I will go in the map and I am going to store six and 14 and the latest element is six.

104
00:06:21,970 --> 00:06:24,700
So what I will do, I will store six in the beginning.

105
00:06:25,990 --> 00:06:35,290
But this is wrong, why this is wrong, because we have capacity, too, and you are inserting three

106
00:06:35,290 --> 00:06:36,400
elements, right?

107
00:06:36,430 --> 00:06:42,910
The capacity of your allocation is only to and here you are having three elements in your list, which

108
00:06:42,910 --> 00:06:43,950
is wrong.

109
00:06:45,070 --> 00:06:45,490
Right.

110
00:06:45,670 --> 00:06:46,640
Which is wrong.

111
00:06:46,780 --> 00:06:48,670
So I told you what Larry will do.

112
00:06:48,910 --> 00:06:54,760
It will delete the list item, a list item to create space.

113
00:06:55,120 --> 00:06:59,710
And the whole list item is the item which is present at the last in the list.

114
00:07:00,100 --> 00:07:00,510
Right.

115
00:07:00,760 --> 00:07:04,340
So which item is present that last five is present at last.

116
00:07:04,630 --> 00:07:10,350
So you will delete the last item from the list and obviously from m'appelle to.

117
00:07:11,270 --> 00:07:21,980
Right, obviously, from the map now, this is your list six and one right now what I'm doing, get

118
00:07:22,100 --> 00:07:24,280
five, so I will check in the map.

119
00:07:24,290 --> 00:07:26,960
FIFA's president no, FIFA's not present.

120
00:07:27,140 --> 00:07:29,300
So that's why the output will be minus one.

121
00:07:29,550 --> 00:07:29,980
Right.

122
00:07:30,140 --> 00:07:32,360
So that's how LRU cash works.

123
00:07:32,870 --> 00:07:34,310
So for implementing it.

124
00:07:34,320 --> 00:07:34,920
Okay.

125
00:07:35,180 --> 00:07:36,030
What do you need.

126
00:07:36,050 --> 00:07:45,590
You need one map and you need one list and you need to make sure that in the list we have order of elements

127
00:07:45,590 --> 00:07:52,790
from starting from basically attached to the list such that whenever we cross the limit, whenever the

128
00:07:52,790 --> 00:07:56,540
size of the list increases, we can delete the last element.

129
00:07:56,720 --> 00:07:57,130
Right.

130
00:07:58,550 --> 00:08:02,990
So that's how this basically allocation is implemented.

131
00:08:03,170 --> 00:08:06,950
So one example is already provided to us in the commission.

132
00:08:07,220 --> 00:08:13,430
And let's try to see how this example will work and whether our approach is correct or not.

133
00:08:13,850 --> 00:08:17,600
So let me again write.

134
00:08:17,630 --> 00:08:18,950
This will be our map.

135
00:08:20,180 --> 00:08:20,630
Right.

136
00:08:20,630 --> 00:08:27,050
And this will be my list from the latest to on list.

137
00:08:29,300 --> 00:08:35,960
And liquidate all the operations, so LRU, that means I'm calling the constructor, that is, I am

138
00:08:35,960 --> 00:08:38,330
passing the capacities or the capacities to.

139
00:08:38,360 --> 00:08:39,260
So let me right.

140
00:08:39,260 --> 00:08:42,520
The capacity of LRU cachets two, which is fine.

141
00:08:42,530 --> 00:08:51,200
Now, I have put and put two times put operation put and put and are reporting one on one to one and

142
00:08:51,200 --> 00:08:51,500
one.

143
00:08:51,830 --> 00:08:52,670
Then next is.

144
00:08:52,850 --> 00:08:59,120
And so to commit to this is one, next is get operation, get one.

145
00:08:59,420 --> 00:09:07,490
So get one next operation is again, put support and develop that entry.

146
00:09:08,090 --> 00:09:13,520
So give a loopier three and the next operation is get so get.

147
00:09:14,480 --> 00:09:24,980
And I'm calling it on to so get the next operation esport so forth and for enfold so for Khama for next

148
00:09:24,980 --> 00:09:25,960
operation is get.

149
00:09:25,970 --> 00:09:27,230
So I am writing here.

150
00:09:28,490 --> 00:09:28,940
Get.

151
00:09:30,130 --> 00:09:34,390
Get and get two times to get, so get, get and get.

152
00:09:36,590 --> 00:09:45,640
And the values are one, three and four, so the values are get one, get three and get four, right.

153
00:09:46,040 --> 00:09:48,110
So let's see how this will work.

154
00:09:49,130 --> 00:09:51,800
So first of all, I have capacity to very good.

155
00:09:51,920 --> 00:09:53,570
Then put one in one.

156
00:09:53,750 --> 00:09:57,920
So I will go in the map and I will put one and one.

157
00:09:58,550 --> 00:10:00,590
Also, you need to insert one.

158
00:10:01,070 --> 00:10:03,110
I will store only cookies.

159
00:10:03,530 --> 00:10:03,910
Right.

160
00:10:04,190 --> 00:10:05,090
This is case.

161
00:10:05,090 --> 00:10:06,680
I will store keys in the list.

162
00:10:07,250 --> 00:10:08,310
So I was told one.

163
00:10:08,990 --> 00:10:17,660
Now the next is put to Clamato so I will store to when doing the map and two is the latest element.

164
00:10:17,870 --> 00:10:21,260
So I will insert two in the front of the list.

165
00:10:22,540 --> 00:10:29,470
Now I have a great operation, get one, so get when there is one president minus the map and the value

166
00:10:29,470 --> 00:10:30,130
is when.

167
00:10:30,130 --> 00:10:36,600
So the value is one that I will return when and since when is the latest element.

168
00:10:37,000 --> 00:10:43,450
So you will remove one from the list and they will put one in the beginning, because one is the latest

169
00:10:43,450 --> 00:10:45,970
element that I am accessing.

170
00:10:46,360 --> 00:10:48,700
Next is basically three comma three.

171
00:10:49,120 --> 00:10:49,960
So check.

172
00:10:51,680 --> 00:10:58,190
I am inserting Tecoma three and three is the latest element, so I will put three in the beginning.

173
00:10:58,430 --> 00:11:04,130
But again, this is wrong because the capacity of the allocation is too.

174
00:11:04,400 --> 00:11:05,910
And we have three elements.

175
00:11:06,380 --> 00:11:07,610
So what do we need to do?

176
00:11:07,880 --> 00:11:14,450
We will delete the last element, delete the oldest element and the oldest element is present at last.

177
00:11:14,450 --> 00:11:16,650
So three one, two, two is the last.

178
00:11:16,670 --> 00:11:19,790
So I will relate to I am deleting two from the list.

179
00:11:20,000 --> 00:11:22,190
You need to also delete two from the map.

180
00:11:22,910 --> 00:11:23,320
Right.

181
00:11:23,810 --> 00:11:26,060
So this is successful now.

182
00:11:26,060 --> 00:11:26,690
Three entry.

183
00:11:26,960 --> 00:11:28,630
Now the next is get two.

184
00:11:28,850 --> 00:11:30,060
So I will check in the map.

185
00:11:30,070 --> 00:11:34,130
Two is not present so I will return minus one.

186
00:11:35,330 --> 00:11:36,530
Two is not present.

187
00:11:36,530 --> 00:11:37,880
So I will return minus one.

188
00:11:37,910 --> 00:11:42,710
Now the next is booked for four so I will store for my four in the map.

189
00:11:43,190 --> 00:11:46,510
And forward is the latest element that I am accessing.

190
00:11:46,760 --> 00:11:48,350
So I will put forward in the beginning.

191
00:11:48,350 --> 00:11:54,860
But now my list contains three elements and the capacity of a location is only two.

192
00:11:54,860 --> 00:11:56,930
So you need to delete the last element.

193
00:11:57,140 --> 00:12:02,290
And the only element is basically the element which is present at last, which is element one.

194
00:12:02,330 --> 00:12:05,330
So remove element one from the list as alleged from the map.

195
00:12:07,130 --> 00:12:07,510
Right.

196
00:12:07,520 --> 00:12:11,780
So put four and four is successful now get one.

197
00:12:12,110 --> 00:12:14,210
So one is present in the map.

198
00:12:14,210 --> 00:12:15,590
No one is not present.

199
00:12:15,590 --> 00:12:17,360
So this will be minus one.

200
00:12:17,480 --> 00:12:18,980
Get three to use present.

201
00:12:18,980 --> 00:12:22,310
Yes, the output is three, only four is present.

202
00:12:22,320 --> 00:12:22,600
Yes.

203
00:12:22,620 --> 00:12:24,320
The output is for only.

204
00:12:24,350 --> 00:12:24,680
Right.

205
00:12:24,860 --> 00:12:28,030
And this operation we will not return anything that way.

206
00:12:28,040 --> 00:12:29,470
They are written rate.

207
00:12:29,620 --> 00:12:30,920
We are not returning anything.

208
00:12:31,220 --> 00:12:33,170
So that's why they are writing null.

209
00:12:33,860 --> 00:12:37,490
And similarly for this capacity we will not return anything.

210
00:12:37,490 --> 00:12:40,020
So normal rate again.

211
00:12:40,220 --> 00:12:42,140
The operation so null again.

212
00:12:42,140 --> 00:12:45,410
Put operation so null here also.

213
00:12:47,840 --> 00:12:58,040
And let me check so we have null null initially evolutional so null then I have one null minus one and

214
00:12:58,520 --> 00:13:05,480
so when null minus one and now I have minus one, three four I have minus one, three, four.

215
00:13:05,690 --> 00:13:09,050
And that said, so basically our approach will work.

216
00:13:09,290 --> 00:13:12,050
And let me summarize what is our approach.

217
00:13:12,230 --> 00:13:13,820
So our approach is very simple.

218
00:13:14,240 --> 00:13:23,180
I will have one map and I will have one list list of keys and I will store in this order from the test

219
00:13:24,320 --> 00:13:28,810
to our list and then write nothing else.

220
00:13:28,820 --> 00:13:32,570
So if you want, you can try writing the code for this problem yourself.

221
00:13:32,930 --> 00:13:35,240
But in the next video I will be writing the code.

222
00:13:35,960 --> 00:13:38,980
So if you want to try coding this problem, do give it a try.

223
00:13:39,020 --> 00:13:41,390
Otherwise you can watch my solution in the next video.

224
00:13:41,420 --> 00:13:42,790
So I will see you in the next one.

225
00:13:42,950 --> 00:13:43,550
Thank you.