1
00:00:01,510 --> 00:00:02,540
Hello, everyone.

2
00:00:02,560 --> 00:00:08,980
So in this video, we are going to discuss that we have discussed this problem in our last video and

3
00:00:08,980 --> 00:00:13,620
we discussed the two disadvantages of using that solution, the world map.

4
00:00:14,020 --> 00:00:18,060
So what we are going to do is now we have advanced our problem.

5
00:00:18,340 --> 00:00:21,370
So now we have a collection of words and not just a single word.

6
00:00:21,550 --> 00:00:27,120
For example, the good word is containing Lion the King and not a lion only.

7
00:00:27,430 --> 00:00:33,110
Similarly, that the word is containing the word tiger, the competitor, and not only the tiger.

8
00:00:33,400 --> 00:00:37,440
Similarly, Inocente leopard and dangerous shock and large logevall.

9
00:00:38,100 --> 00:00:40,240
So what do you need to do in the paragraph?

10
00:00:40,390 --> 00:00:41,500
Lion the King.

11
00:00:41,800 --> 00:00:45,700
So Lion the King is present here and Lion the King is present here.

12
00:00:45,730 --> 00:00:49,990
So you are going to replace this entire three words with the word cat.

13
00:00:51,860 --> 00:00:57,890
So similarly, you are going to replace the word innocent leopard with the word cat, and similarly

14
00:00:58,580 --> 00:01:05,390
you are going to replace the word Logevall with the word Oshin, and they will not replace Shakar because

15
00:01:05,390 --> 00:01:08,620
the word is dangerous and not only the shock.

16
00:01:09,590 --> 00:01:11,420
So that is the problem statement.

17
00:01:11,840 --> 00:01:13,930
And I told you what they can do.

18
00:01:13,940 --> 00:01:16,040
We can use Debrided as a teacher here.

19
00:01:16,070 --> 00:01:21,260
So basically what we can do, we can use tried it as a teacher here and how I am going to throw the

20
00:01:21,260 --> 00:01:22,050
words and try.

21
00:01:22,070 --> 00:01:23,540
That is the important thing.

22
00:01:23,550 --> 00:01:25,190
So I will told like this.

23
00:01:25,640 --> 00:01:27,270
I have the root node for a try.

24
00:01:28,490 --> 00:01:34,360
Let's take one word, for example, if I want to store Logevall so I will store large first.

25
00:01:34,850 --> 00:01:37,640
So L then a.

26
00:01:39,130 --> 00:01:40,570
And keep going on.

27
00:01:40,780 --> 00:01:47,770
I will also store the character space bill, so I am going to store the blue, which is correspond to

28
00:01:47,770 --> 00:01:52,720
Will and I was told the last character is E, so e.

29
00:01:53,960 --> 00:01:55,350
Will stole a lot of things.

30
00:01:55,370 --> 00:02:02,900
First of all, it is basically a terminal node, so I'm going to highlight this node and what else evil

31
00:02:02,900 --> 00:02:05,810
stole evil also stole the key.

32
00:02:07,030 --> 00:02:14,140
Evil also stole the key here, which is OCN, so you need to modify your Naude.

33
00:02:15,390 --> 00:02:23,820
And your note will contain is terminal U.A. will contain area of this exercise and you will contain

34
00:02:23,820 --> 00:02:24,750
one more.

35
00:02:25,060 --> 00:02:33,480
Uh, let's Namadgi only string key so you will told you need to modify your node and you will store

36
00:02:33,480 --> 00:02:35,700
one more data member, which is string key.

37
00:02:36,150 --> 00:02:45,180
And this terminal node, this terminal node is going to store the key, which is, Ossian, if you remember,

38
00:02:45,180 --> 00:02:51,000
I have discussed a similar application before and the application was Truecaller up, if you remember

39
00:02:51,000 --> 00:02:51,780
to call a rep.

40
00:02:52,110 --> 00:02:54,630
So I told you in that case what I will do.

41
00:02:54,780 --> 00:02:57,960
So let's say this number belongs to a person, John.

42
00:02:58,990 --> 00:03:05,230
So the last character, the last a. was starting the world, John.

43
00:03:06,330 --> 00:03:12,600
Distorting the name John, so similarly, we are doing exactly the same here, the last basically the

44
00:03:12,600 --> 00:03:14,130
last inaudible question.

45
00:03:14,400 --> 00:03:18,840
Similarly, you can enter the word dangerous dog.

46
00:03:19,170 --> 00:03:19,860
So de.

47
00:03:20,890 --> 00:03:27,870
Then dangerous, then space, then basically shark, and similarly, the last character, Turkey will

48
00:03:27,880 --> 00:03:28,810
store ocean.

49
00:03:32,010 --> 00:03:38,130
And obviously, this is the last character to come in 11, so we are going to highlight this, and in

50
00:03:38,130 --> 00:03:42,900
this way you will insert all the words, you will insert the king.

51
00:03:43,500 --> 00:03:46,370
So we will insert line then space.

52
00:03:46,380 --> 00:03:47,580
I have space here.

53
00:03:47,910 --> 00:03:49,080
So we will insert space.

54
00:03:49,080 --> 00:03:53,250
Then you will insert the so you will insert the then space.

55
00:03:53,730 --> 00:03:55,140
Then you will insert king.

56
00:03:56,370 --> 00:03:58,800
And we will store basically get.

57
00:04:02,280 --> 00:04:05,040
So that's how your trial will look like.

58
00:04:06,680 --> 00:04:12,350
Right, and what you need to do, you need to do this preprocessing only one time.

59
00:04:13,360 --> 00:04:16,579
Once your tribe is ready, what do you need to do?

60
00:04:16,600 --> 00:04:21,940
You need just you just need to iterate over this paragraph and start replacing the word, start searching

61
00:04:21,940 --> 00:04:24,110
the word and try and start replacing them.

62
00:04:24,610 --> 00:04:30,910
So we are going to construct this tribe only once and then, oh, basically, we will call the error

63
00:04:30,910 --> 00:04:37,060
function only once by once, meaning for inserting all the words after we have inserted all the words,

64
00:04:37,060 --> 00:04:38,550
our function will not be used.

65
00:04:38,560 --> 00:04:40,570
We will use only the search function.

66
00:04:41,650 --> 00:04:42,120
Right.

67
00:04:42,610 --> 00:04:46,700
We will just write it over the paragraph and we'll simply call the function search.

68
00:04:47,200 --> 00:04:50,860
So for example, let's take this example, Lion the King.

69
00:04:50,980 --> 00:04:52,150
So I will start from L..

70
00:04:52,240 --> 00:04:52,660
Yes.

71
00:04:52,660 --> 00:04:53,560
At this present.

72
00:04:53,710 --> 00:04:54,790
Next character line.

73
00:04:54,790 --> 00:04:55,060
Yes.

74
00:04:55,060 --> 00:04:55,950
Linus present.

75
00:04:55,960 --> 00:04:56,920
Sorry, this is line.

76
00:04:57,430 --> 00:04:58,630
So line is present.

77
00:04:59,110 --> 00:05:00,880
This present king is present.

78
00:05:01,120 --> 00:05:04,930
So at atlast you will be able to find King G.

79
00:05:05,650 --> 00:05:15,130
So just G I will replace the entire this word with Cat and I will move ahead to the word K then I will

80
00:05:15,130 --> 00:05:20,710
check escape as in no case not present then simply move to the next word.

81
00:05:21,400 --> 00:05:21,880
Right.

82
00:05:22,750 --> 00:05:25,500
So check I is present innocent.

83
00:05:25,570 --> 00:05:27,130
Yes I is present.

84
00:05:27,130 --> 00:05:29,950
We are going to insert this so we will replace everything.

85
00:05:30,610 --> 00:05:36,820
Similarly for large wheel I will start from L and then we will be able to find out at E.

86
00:05:37,570 --> 00:05:45,400
I have this option so I will replace this with Océane for please be so ps not present here.

87
00:05:45,550 --> 00:05:46,360
Don't do anything.

88
00:05:46,360 --> 00:05:47,320
Move to the next word.

89
00:05:47,560 --> 00:05:48,730
W is not pleasant.

90
00:05:49,030 --> 00:05:52,030
Move to the next world s s is not present.

91
00:05:52,030 --> 00:05:53,110
Move to the next world.

92
00:05:53,500 --> 00:05:58,390
So you can see we are able to optimize our algorithm.

93
00:05:58,660 --> 00:06:02,470
Our search function has been optimized and it's really, really fast now.

94
00:06:03,100 --> 00:06:09,400
And with the help of prioritization, we have solved all the two problems that we have with the previous

95
00:06:09,400 --> 00:06:09,940
approach.

96
00:06:11,620 --> 00:06:12,100
Right.

97
00:06:12,280 --> 00:06:16,030
We have a collection of words is working properly.

98
00:06:16,030 --> 00:06:19,030
Try is the best solution if you have a collection of words.

99
00:06:19,450 --> 00:06:21,250
So that problem is solved.

100
00:06:21,250 --> 00:06:23,320
And second problem was the memory problem.

101
00:06:23,980 --> 00:06:24,490
Right.

102
00:06:24,490 --> 00:06:30,040
And it will not take a lot of memory at Max.

103
00:06:30,040 --> 00:06:31,060
At each level.

104
00:06:31,060 --> 00:06:35,170
You are going to have a twenty six word array right at Max.

105
00:06:35,170 --> 00:06:38,050
You are going to have 26 words for twenty 26.

106
00:06:38,800 --> 00:06:43,540
At Max you can have twenty six node for each node, 26 child in order for each node.

107
00:06:43,690 --> 00:06:47,920
And what can be the depth, what can be the depth of this.

108
00:06:48,160 --> 00:06:52,390
Try so depth can be the largest number of characters.

109
00:06:52,390 --> 00:06:59,320
For example, we have a collection of words, so in this case four, then three and then four.

110
00:06:59,620 --> 00:07:02,920
So around around thirteen characters.

111
00:07:02,920 --> 00:07:05,220
So, so that will not be a problem.

112
00:07:05,530 --> 00:07:09,190
So this is this is taking very little space.

113
00:07:10,090 --> 00:07:14,800
This is taking very little space as compared to the previous approach.

114
00:07:15,340 --> 00:07:20,710
So we have solved both the two problems, the memory problems and the single word problem.

115
00:07:21,790 --> 00:07:29,990
So this problem was basically asked by the company Adobe, one of my friends interviewed for the emptiest

116
00:07:30,050 --> 00:07:32,890
job member of technical staff job for the lobby.

117
00:07:33,100 --> 00:07:36,100
And they got this problem in this first round.

118
00:07:36,670 --> 00:07:42,670
So they didn't ask them to write the code, but they just ask them the complete solution, starting

119
00:07:42,670 --> 00:07:45,570
from the previous video, the reverse solution.

120
00:07:45,580 --> 00:07:51,190
But the problem with that reverse type solution and then let's try a solution, they just ask the approach.

121
00:07:51,190 --> 00:07:54,010
And they didn't ask him to write the code.

122
00:07:54,280 --> 00:08:01,420
So knowing the approach is sufficient for this problem, writing the code for this problem is is not

123
00:08:01,420 --> 00:08:08,920
an interview task because for interview, we have only limited time, 45 to 60 Minutes, and this problem

124
00:08:08,920 --> 00:08:10,510
cannot be coded in that time.

125
00:08:10,690 --> 00:08:12,610
We also need to discuss these approaches.

126
00:08:12,610 --> 00:08:13,720
They are pros and cons.

127
00:08:14,170 --> 00:08:16,300
You will not be asked to write the code for this problem.

128
00:08:16,330 --> 00:08:18,940
The interviewer just asked you the approach and not the code.

129
00:08:19,780 --> 00:08:22,990
So I think that's all that I want to cover in this video.

130
00:08:22,990 --> 00:08:28,480
So, again, if you face any problem in understanding the solution or if you have any other problem,

131
00:08:28,480 --> 00:08:29,470
just ping me.

132
00:08:29,740 --> 00:08:30,850
We are ready to help.

133
00:08:31,300 --> 00:08:33,340
So that's it from this video, guys.

134
00:08:34,000 --> 00:08:35,549
So I will see you in the next one.

135
00:08:35,559 --> 00:08:36,100
Thank you.