1
00:00:01,810 --> 00:00:03,550
Hi, everyone, welcome back.

2
00:00:03,790 --> 00:00:08,530
So in this video, we are going to write the code for this problem case, our telling list.

3
00:00:09,460 --> 00:00:17,860
So our approach was, if this is the last one, four five second one is one three four and the third

4
00:00:17,860 --> 00:00:19,150
one is 26.

5
00:00:19,480 --> 00:00:20,710
So we discussed that.

6
00:00:20,710 --> 00:00:26,650
What we need to do, we need to create one minimum because we want a minimum element each time and we

7
00:00:26,650 --> 00:00:29,750
will insert all these values in our minimum.

8
00:00:29,770 --> 00:00:34,930
Keep one thing to note here is the type of minimum.

9
00:00:35,380 --> 00:00:37,960
So basically the input is, listen, Wildstar.

10
00:00:37,960 --> 00:00:39,610
So this is not in German.

11
00:00:39,640 --> 00:00:40,720
This is old one.

12
00:00:41,020 --> 00:00:42,070
This is one note.

13
00:00:42,130 --> 00:00:43,360
This is another node.

14
00:00:43,660 --> 00:00:44,030
Right.

15
00:00:44,180 --> 00:00:47,880
So my minimum, he will be of type node and not integer.

16
00:00:48,220 --> 00:00:52,420
So we discussed that we need to create one priority queue.

17
00:00:56,250 --> 00:00:58,420
And the pressure to give will be minimum.

18
00:00:58,920 --> 00:01:02,060
So it will be of the type no.

19
00:01:02,080 --> 00:01:02,550
Right.

20
00:01:03,300 --> 00:01:04,590
This is our priority queue.

21
00:01:04,650 --> 00:01:08,810
So this is actually an index for Mexi and not minimum.

22
00:01:09,910 --> 00:01:11,460
We need to create minimum EHP.

23
00:01:11,470 --> 00:01:14,690
So we will come back to this line later that how to create a minimum job.

24
00:01:15,000 --> 00:01:17,410
But for now, let's assume this is my minimum.

25
00:01:18,330 --> 00:01:21,240
Now what I need to do, I need to insert the values.

26
00:01:21,570 --> 00:01:22,920
So let's I trade.

27
00:01:26,000 --> 00:01:37,070
List Nazis and I placeless what I need to do, I need to push these values in my priority queue.

28
00:01:37,280 --> 00:01:41,510
So Picador push list of I write.

29
00:01:44,280 --> 00:01:45,750
So what will happen?

30
00:01:46,320 --> 00:01:49,170
So basically, I have pushed all these values.

31
00:01:50,570 --> 00:01:57,500
So I have pushed no one in my priority queue, I have no one in the priority queue and I have No.

32
00:01:57,500 --> 00:02:03,800
Two in the priority queue, and we discussed that we will run the loop while the priority queue doesn't.

33
00:02:03,800 --> 00:02:06,440
While the priority is not empathy, right.

34
00:02:06,680 --> 00:02:10,460
While the priority queue is containing elements, I will I'll trade.

35
00:02:12,080 --> 00:02:18,710
So let's I'll trade while the priority queue is not empty.

36
00:02:21,570 --> 00:02:22,970
So what do we need to do here?

37
00:02:26,180 --> 00:02:35,090
List North Star, let's name it, temp Bambury A. This is basically your pick your top, right.

38
00:02:35,420 --> 00:02:36,950
And we need to remove this.

39
00:02:36,950 --> 00:02:39,220
Also pick your date, Pop.

40
00:02:40,040 --> 00:02:42,050
And what do you want to return?

41
00:02:42,050 --> 00:02:45,740
We want to return the head head of the newly created linked list.

42
00:02:46,100 --> 00:02:50,850
So list North Star Head, which is initially null.

43
00:02:51,440 --> 00:02:59,210
Similarly, we discussed that I will have one deal that is also null initially.

44
00:03:01,240 --> 00:03:10,610
So after removing this beacon, art, pop, if this is the first element, so if my head is in my head

45
00:03:10,630 --> 00:03:12,540
is nil, that means this is the first node.

46
00:03:12,970 --> 00:03:18,070
So my head and tail both will point towards this node.

47
00:03:18,070 --> 00:03:18,490
Right.

48
00:03:18,960 --> 00:03:22,720
Otherwise, if this is not the first node, what I'm going to do.

49
00:03:24,400 --> 00:03:31,570
I will make the connection so they'll add an extra stamp and I'm going to update my tail pointer, right,

50
00:03:31,570 --> 00:03:32,570
I'm inserting it.

51
00:03:32,800 --> 00:03:36,290
Bill, what else do we need to do here?

52
00:03:37,960 --> 00:03:48,150
See what I'm doing in my head until the board, until they head, until butat initially.

53
00:03:49,120 --> 00:03:52,680
So what I'm doing here is pick the first node.

54
00:03:52,690 --> 00:03:55,510
So the minimum notice when one or two.

55
00:03:55,510 --> 00:03:56,350
Which one is minimum.

56
00:03:56,920 --> 00:03:57,650
These two are same.

57
00:03:57,700 --> 00:04:04,300
So we can pick any let's say I am picking this so I will pick this node and this is the first node head

58
00:04:04,300 --> 00:04:04,920
until the board.

59
00:04:05,560 --> 00:04:07,960
So if the head until the blue tunnel.

60
00:04:07,980 --> 00:04:15,310
So what I'm doing, my head will point to this node and then we also point towards this node that if

61
00:04:15,310 --> 00:04:20,910
this is another node, let's say I have a list of nodes and this is my tail pointer.

62
00:04:21,370 --> 00:04:24,130
So if I have any of the node, then that will not be null.

63
00:04:24,130 --> 00:04:27,560
Had will be pointing towards this node remove tail from here.

64
00:04:28,000 --> 00:04:34,810
So in that case, what I am doing, I am inserting the node, I am inserting the node at the tail position

65
00:04:34,810 --> 00:04:37,320
and then I am updating tail.

66
00:04:37,630 --> 00:04:40,700
So then I am updating might be all right.

67
00:04:41,080 --> 00:04:42,340
So that's how it is working.

68
00:04:42,340 --> 00:04:43,790
But this is not enough.

69
00:04:43,810 --> 00:04:44,870
What else do we need to do?

70
00:04:45,190 --> 00:04:46,600
So we discussed that.

71
00:04:47,200 --> 00:04:49,120
Then we will pop three.

72
00:04:49,660 --> 00:04:50,980
So sorry.

73
00:04:50,980 --> 00:04:51,970
Then we will pop this.

74
00:04:51,970 --> 00:04:57,430
Norvan, what I will do, I need to insert four, I need to insert four.

75
00:04:57,430 --> 00:04:57,840
Right.

76
00:04:58,570 --> 00:05:00,100
So we need to insert.

77
00:05:02,930 --> 00:05:13,390
So what I can do, I can sort that is be good Bush next next of one and next of one is for right.

78
00:05:13,790 --> 00:05:21,380
Similarly, I think this quote is not correct way, because for this node, for this node, what is

79
00:05:21,380 --> 00:05:21,890
next?

80
00:05:21,890 --> 00:05:22,790
Next is null.

81
00:05:23,570 --> 00:05:27,520
So what we will be doing, you will be inserting null and which is wrong.

82
00:05:27,800 --> 00:05:31,340
So you should have one check here that you will not insert values.

83
00:05:32,210 --> 00:05:32,650
Right.

84
00:05:33,050 --> 00:05:35,570
So we should not insert null values.

85
00:05:40,170 --> 00:05:46,450
So before inserting, we must check whether the next is normal or not.

86
00:05:48,840 --> 00:05:54,660
So if the next is not null, then only you will insert.

87
00:06:01,890 --> 00:06:07,180
Right, and one more thing we are inserting here also.

88
00:06:07,560 --> 00:06:12,630
So whatever list of why does not exist, what if this is all right?

89
00:06:12,640 --> 00:06:13,730
It can be also.

90
00:06:14,160 --> 00:06:22,680
So you need to check here also, when a list of IP is not null, then only we will insert in the priority

91
00:06:22,700 --> 00:06:22,980
queue.

92
00:06:23,620 --> 00:06:27,540
We will not and certainly values in the prior to do so, we need to check here.

93
00:06:31,760 --> 00:06:32,140
Right.

94
00:06:33,350 --> 00:06:39,530
And finally, what you will do, you will return did fine.

95
00:06:41,690 --> 00:06:43,810
So let me try to explain you what we are doing.

96
00:06:44,390 --> 00:06:48,840
We discussed that we need to create a minimum heap, but this is not the code for minimum heap.

97
00:06:49,100 --> 00:06:50,350
This is the code for Makhzoumi.

98
00:06:50,480 --> 00:06:53,750
So we will be updating the code a little bit later then.

99
00:06:54,440 --> 00:06:59,810
But we need to do we need to insert these first value in the player dequeue.

100
00:07:00,290 --> 00:07:02,870
So am I trading and if the value is not nil.

101
00:07:02,900 --> 00:07:05,210
So yes, link list exist.

102
00:07:05,210 --> 00:07:07,220
Linked list exist, linked list exist.

103
00:07:07,470 --> 00:07:10,340
So I will push so I will push one, one and two.

104
00:07:10,370 --> 00:07:10,750
Right.

105
00:07:11,000 --> 00:07:16,910
So my priority will contain here when one and two these are nodes and not integer values.

106
00:07:17,360 --> 00:07:22,910
Then I need two pointers had until as I explained in previous we do and finally I answer will be held.

107
00:07:23,690 --> 00:07:23,950
Right.

108
00:07:24,200 --> 00:07:30,440
So what we are doing take the top element, basically the minimum value and remove the minimum value.

109
00:07:31,010 --> 00:07:35,400
And after removing the minimum value, you can check if this is the first node, you will update it

110
00:07:35,420 --> 00:07:40,630
until if this is not the first node, then you will insert at bill and even a battle.

111
00:07:41,090 --> 00:07:44,410
And what else do we need to do so after removing one?

112
00:07:44,600 --> 00:07:46,460
So the next one is four.

113
00:07:46,580 --> 00:07:52,790
So you should insert food, but before inserting four, you need to check whether next is an alternate.

114
00:07:52,820 --> 00:07:58,610
So for example, in case of five, in case of prayer, in case of six here, the next value will be

115
00:07:58,610 --> 00:07:59,870
none so vital.

116
00:07:59,930 --> 00:08:01,240
Insert the prior to.

117
00:08:01,760 --> 00:08:05,960
So we need to write this check that will not insert null values in priority.

118
00:08:06,620 --> 00:08:07,150
Simple.

119
00:08:07,340 --> 00:08:13,010
So the only thing remaining in this code is basically to write, to basically update this line.

120
00:08:13,440 --> 00:08:15,250
We want to create a minimum heap.

121
00:08:15,300 --> 00:08:15,700
Right.

122
00:08:16,100 --> 00:08:24,980
And this is a little bit complex or basically this is something very specific to C++ programming language.

123
00:08:25,430 --> 00:08:28,550
So the syntax for creating minimum heap is basically this.

124
00:08:33,140 --> 00:08:34,820
We need to list North Star.

125
00:08:36,370 --> 00:08:38,110
And we need to pass.

126
00:08:40,570 --> 00:08:47,290
A compare function, and now this will become your minimum heap.

127
00:08:50,650 --> 00:08:54,770
And what is this, my campaign slogan to define what is my campaign?

128
00:08:55,180 --> 00:09:05,290
So the syntax for defining this is basically struct might compare and then you need to write this function.

129
00:09:05,290 --> 00:09:06,220
Bool Operator.

130
00:09:09,210 --> 00:09:17,100
So this bull operator function takes two arguments and one of those arguments that will be this late

131
00:09:17,520 --> 00:09:19,950
analyst least that work prior to Google Contin.

132
00:09:20,760 --> 00:09:22,530
So we need to pass two arguments.

133
00:09:23,550 --> 00:09:27,540
A and B name can be anything.

134
00:09:27,570 --> 00:09:28,410
It doesn't matter.

135
00:09:30,250 --> 00:09:36,660
List an all star and B, and then you need to return a boolean value.

136
00:09:36,960 --> 00:09:43,530
So the value of E should be greater than value of B.

137
00:09:46,110 --> 00:09:48,970
Right, this is the code for creating minimum.

138
00:09:49,220 --> 00:09:53,540
I know this is a little bit complex, but this is the syntax, right?

139
00:09:53,540 --> 00:09:55,400
And we need to remember the syntax.

140
00:09:56,360 --> 00:09:58,710
So we need to create a minimum heap.

141
00:09:59,450 --> 00:10:01,850
So you need to write that type.

142
00:10:02,270 --> 00:10:05,870
The type of elements, a particular store, it will store one at least not start.

143
00:10:06,320 --> 00:10:07,630
Then you need to write this.

144
00:10:07,670 --> 00:10:12,870
So I forgot to close this bracket then comma and then might compare.

145
00:10:13,160 --> 00:10:18,870
Then you need to write struct my compare unit to write bool operator you need to write this index and

146
00:10:18,890 --> 00:10:20,610
Q is of type list Northstar.

147
00:10:20,930 --> 00:10:22,840
So that's why I type here.

148
00:10:22,850 --> 00:10:27,350
And you need to compare to values on what basis you want to compare elements in the prior to.

149
00:10:27,360 --> 00:10:32,990
Q So I want to compare the elements on basis of their values, so I'm comparing the element on basis

150
00:10:32,990 --> 00:10:33,780
of their values.

151
00:10:34,010 --> 00:10:36,020
So this is minimum heap, right.

152
00:10:37,760 --> 00:10:38,930
Values means integer.

153
00:10:38,940 --> 00:10:40,490
So it is given this is the value.

154
00:10:40,490 --> 00:10:40,810
Right.

155
00:10:41,600 --> 00:10:47,360
I know it's a little bit complex, but this is the syntax very specific to C++ and other programming

156
00:10:47,360 --> 00:10:48,050
languages.

157
00:10:48,050 --> 00:10:49,820
You can find different defensive backs.

158
00:10:50,090 --> 00:10:54,770
But what I suggest is basically do not complicate things.

159
00:10:54,770 --> 00:11:00,440
Do not do not try to indulge in and try to learn why this is the syntax.

160
00:11:00,740 --> 00:11:05,950
Just remember the syntax that this is how we write minimum heap and we can move forward.

161
00:11:06,230 --> 00:11:07,670
This is more than enough, right?

162
00:11:07,910 --> 00:11:10,480
So this is the entire goal for solving this problem.

163
00:11:10,790 --> 00:11:17,390
And before submitting, let's first run so that if there is any bug, we can figure it out and we can

164
00:11:17,390 --> 00:11:18,050
fix the bug.

165
00:11:18,500 --> 00:11:21,610
And if everything works fine, then obviously we will submit.

166
00:11:22,700 --> 00:11:25,820
OK, so we need to write actually a column here.

167
00:11:30,670 --> 00:11:34,310
And yet, obviously, I told you that we need to close this record.

168
00:11:35,080 --> 00:11:36,620
So now let's listen to it.

169
00:11:36,640 --> 00:11:38,400
I think it will work fine now.

170
00:11:41,870 --> 00:11:48,050
So we got competition out of here because this must be semicolon.

171
00:11:52,720 --> 00:11:55,280
Yep, so basically our goal is working.

172
00:11:55,540 --> 00:12:00,550
So this is very simple problem, I don't know why they have mentioned it as hard, but this was really

173
00:12:00,550 --> 00:12:01,000
simple.

174
00:12:01,880 --> 00:12:08,980
Right now, one more thing that I want to discuss before ending this video is the other variation of

175
00:12:08,980 --> 00:12:09,540
this problem.

176
00:12:09,760 --> 00:12:15,880
So what the interviewer will say so let's say you have hundreds of data interviews, says you have hundreds

177
00:12:16,090 --> 00:12:18,990
of data, and we want to sort this data.

178
00:12:20,760 --> 00:12:21,060
Right.

179
00:12:21,580 --> 00:12:27,610
So one obvious approach that you will give him is basically sir or ma'am, I can sort this data with

180
00:12:27,610 --> 00:12:31,580
the help of my chart or with the help of quicksort or any other sorting algorithm.

181
00:12:32,320 --> 00:12:34,060
He will say it's fine, right?

182
00:12:34,300 --> 00:12:34,900
It's fine.

183
00:12:34,910 --> 00:12:35,620
It will work.

184
00:12:35,950 --> 00:12:44,290
But now he modified the question and he's giving one limitation that at one time in my memory, you

185
00:12:44,290 --> 00:12:46,460
can load only tangible data.

186
00:12:47,800 --> 00:12:56,980
So if we can load MGB of data at one time, then how much it will be able to sort of data that.

187
00:12:57,010 --> 00:12:57,850
You got my point.

188
00:12:58,540 --> 00:12:59,700
So I'm repeating myself.

189
00:13:00,970 --> 00:13:03,370
The interviewer is saying you have a limitation.

190
00:13:03,640 --> 00:13:07,190
At one time in my memory, you can have only tangible data.

191
00:13:07,480 --> 00:13:11,560
So this much certain quicksort will have access to tangible data only.

192
00:13:11,800 --> 00:13:14,120
So it will start on the tangible data.

193
00:13:14,410 --> 00:13:19,140
But the problem is we want to store hundreds of data, thousands of data.

194
00:13:19,390 --> 00:13:20,550
So how we can do that?

195
00:13:21,250 --> 00:13:22,790
This is the question.

196
00:13:24,040 --> 00:13:24,970
So what we can do?

197
00:13:26,720 --> 00:13:33,860
For example, if I have hundreds of data and I can load only tangible data at one time in my memory,

198
00:13:34,490 --> 00:13:42,890
so I will divide this hundred into fences, into ten parts, and each part contains tangible data rate.

199
00:13:43,250 --> 00:13:47,270
So tangible data and then parts.

200
00:13:48,180 --> 00:13:48,520
Right.

201
00:13:49,280 --> 00:13:57,320
So what I will do next, I will pick one part and I will load it in the memory and my will sort that

202
00:13:57,320 --> 00:13:58,310
part right.

203
00:13:58,490 --> 00:14:00,870
So one by one, I will look at all the 10 parts.

204
00:14:01,340 --> 00:14:03,160
And finally, what we will have.

205
00:14:03,440 --> 00:14:07,700
So finally we will have 10 sorted parts, right.

206
00:14:08,060 --> 00:14:09,380
Then sorted parts.

207
00:14:09,560 --> 00:14:15,640
And each part is basically storing tangible data, 10 GB of sorta data.

208
00:14:17,150 --> 00:14:24,500
And then the problem statement is this only we have sorted data rate.

209
00:14:24,680 --> 00:14:28,900
We have 10 GB sorted data, 10 parts, and we need to merge them.

210
00:14:29,820 --> 00:14:37,550
We have 10 sorta data and then parts, and we want to merge them so we can use this algorithm for merging

211
00:14:37,910 --> 00:14:41,970
10 parts, then sorted parts, right.

212
00:14:42,950 --> 00:14:44,390
So this is the other way.

213
00:14:44,390 --> 00:14:47,890
And this this is the other way in which this problem can be fixed.

214
00:14:48,140 --> 00:14:48,540
Right.

215
00:14:49,190 --> 00:14:51,050
So that's how you can solve this problem.

216
00:14:52,010 --> 00:14:54,230
So this is all that I want to discuss.