1
00:00:01,010 --> 00:00:02,000
Welcome back, everyone.

2
00:00:02,600 --> 00:00:08,720
So let's talk about Tri's and how they show up in your interview questions, generally speaking, tries

3
00:00:08,720 --> 00:00:15,440
are not that common in terms of what they'll test you on, because the data structure itself is pretty

4
00:00:15,440 --> 00:00:15,890
simple.

5
00:00:15,890 --> 00:00:18,900
There's not much complexity to how to create one.

6
00:00:19,280 --> 00:00:26,900
So if you do get tested on a try, it's generally going to be around implementing one from scratch and

7
00:00:26,900 --> 00:00:33,650
maybe utilizing it very efficiently in a straightforward search based question or string autocomplete

8
00:00:33,650 --> 00:00:34,250
question.

9
00:00:34,610 --> 00:00:41,450
So the core of what we need to learn is actually how to implement our own try and then maybe modify

10
00:00:41,450 --> 00:00:44,130
it ever so slightly with an additional method.

11
00:00:44,630 --> 00:00:50,960
So here we're going to see an overlap in this try question with what we just learned from interface

12
00:00:50,960 --> 00:00:52,960
design throughout this question.

13
00:00:52,970 --> 00:00:58,760
I'm also going to extensively show you how to implement a try and we'll walk through all of these try

14
00:00:58,760 --> 00:01:05,080
basics again in case you're still a little unfamiliar, just so that we're rock solid on the concepts.

15
00:01:05,750 --> 00:01:12,190
The question we're going to look at says to implement a try with insert search and starts with methods.

16
00:01:13,010 --> 00:01:16,610
So this will be the interface of the TRAI that we need to implement.

17
00:01:16,820 --> 00:01:22,010
In my case, once again, because it's JavaScript, I'm going to implement it using a JavaScript class.

18
00:01:22,850 --> 00:01:27,470
The three methods are insert search and starts with.

19
00:01:28,290 --> 00:01:33,630
Insert receives a string, which will be the word that we're trying to insert into the tri, we're going

20
00:01:33,630 --> 00:01:39,000
to return nothing back from this function because all we're going to do is insert that word into the

21
00:01:39,000 --> 00:01:41,100
tree if it doesn't already exist.

22
00:01:41,790 --> 00:01:43,970
The search method also receives a string.

23
00:01:43,980 --> 00:01:45,640
That's the word that it's looking for.

24
00:01:45,930 --> 00:01:51,090
So we're going to search inside of our try to see if the word has been previously inserted before,

25
00:01:51,570 --> 00:01:53,370
if it's already existing in a try.

26
00:01:53,400 --> 00:01:54,180
Then we return.

27
00:01:54,180 --> 00:01:54,720
True.

28
00:01:55,350 --> 00:01:58,650
If it has not been inserted before, then we return false.

29
00:01:59,990 --> 00:02:06,350
Next, we have the starts with method, this is similar to search, except we don't need to see if the

30
00:02:06,350 --> 00:02:09,470
full word exists inside of our Srei.

31
00:02:09,830 --> 00:02:11,810
We're really just looking for a prefix.

32
00:02:11,810 --> 00:02:15,690
Hence why the argument it takes is called a string prefix.

33
00:02:16,190 --> 00:02:22,100
So here what we're going to look through is whether or not the characters of the prefix exist in the

34
00:02:22,100 --> 00:02:22,500
try.

35
00:02:22,700 --> 00:02:25,700
It doesn't have to be the full inserted word.

36
00:02:25,700 --> 00:02:28,430
And once again, if the prefix exists, we return true.

37
00:02:28,550 --> 00:02:34,610
If it doesn't return false, and we'll break down all three methods very extensively so we know how

38
00:02:34,610 --> 00:02:37,970
it all works as well as diagramming it with a try.

39
00:02:39,340 --> 00:02:45,010
So let's start with our base try we have a root node that represents the entry point for this tri data

40
00:02:45,010 --> 00:02:45,430
structure.

41
00:02:46,090 --> 00:02:50,410
Let's say we call that insert method and we insert the string apple.

42
00:02:51,040 --> 00:02:53,320
Well, we're going to do is we're going to start from the root.

43
00:02:53,320 --> 00:02:58,330
And look, do we have an AI already inserted from this entry node?

44
00:02:58,810 --> 00:02:59,930
No, there's nothing here.

45
00:03:00,280 --> 00:03:03,600
So what we're going to do is start inserting we insert the AI from here.

46
00:03:03,610 --> 00:03:04,480
We look at the AI.

47
00:03:04,480 --> 00:03:05,380
Is there a P?

48
00:03:05,380 --> 00:03:08,770
No, insert a P at the P, we look again.

49
00:03:08,800 --> 00:03:10,210
Is there another P?

50
00:03:10,480 --> 00:03:10,960
No.

51
00:03:10,990 --> 00:03:16,660
So we insert the other P then from this third P we say, OK, what's the next character.

52
00:03:16,660 --> 00:03:17,310
It's an L..

53
00:03:17,320 --> 00:03:18,280
Do we have an L here.

54
00:03:18,280 --> 00:03:18,730
No.

55
00:03:18,730 --> 00:03:20,670
Insert it from the L.

56
00:03:20,680 --> 00:03:21,580
Is there an E.

57
00:03:21,670 --> 00:03:22,150
No.

58
00:03:22,150 --> 00:03:25,720
Insert it at this point we've reached the end of the word.

59
00:03:25,750 --> 00:03:31,330
So what we want to do is we want to say that this E represents the end of a word.

60
00:03:31,630 --> 00:03:38,920
So we would need to designate this E as the end somehow, maybe for each of these different nodes that

61
00:03:38,920 --> 00:03:42,580
represent the characters we have and is n the property.

62
00:03:42,820 --> 00:03:45,000
And this property is a boolean value.

63
00:03:45,010 --> 00:03:48,750
So if this E represents the end, then is and will be true.

64
00:03:49,090 --> 00:03:55,240
That's all we need in order for us to ensure that we know that when you hit this end, you have found

65
00:03:55,240 --> 00:04:00,040
the end of a word up until this point, continuing onwards.

66
00:04:00,730 --> 00:04:05,310
Let's say that what we do now is we want to search for the word dog.

67
00:04:05,620 --> 00:04:11,260
What happens is that we would start from the root node and we would look, is there a D?

68
00:04:11,290 --> 00:04:14,240
Because we want the first character of the word that we're searching for.

69
00:04:14,680 --> 00:04:17,890
No, there's no D so then what we return is false.

70
00:04:18,070 --> 00:04:20,470
The word dog does not exist in our tri.

71
00:04:21,380 --> 00:04:25,390
So what we would do is we would insert the word dog, let's say that's what happens next.

72
00:04:26,060 --> 00:04:28,510
Now from the root, we would look OK.

73
00:04:28,520 --> 00:04:29,300
Is there a D?

74
00:04:29,450 --> 00:04:32,060
No inserted from the D?

75
00:04:32,060 --> 00:04:32,960
Is there an O?

76
00:04:33,080 --> 00:04:33,530
No.

77
00:04:33,710 --> 00:04:35,600
Insert the O from the O.

78
00:04:35,600 --> 00:04:36,440
Is there a G?

79
00:04:36,530 --> 00:04:38,380
No, insert the G.

80
00:04:38,660 --> 00:04:40,160
We've reached the end of the word.

81
00:04:40,310 --> 00:04:43,460
Once again, G needs to be designated as an end.

82
00:04:43,460 --> 00:04:44,450
So we flipped.

83
00:04:44,450 --> 00:04:51,650
That is end to being true on the G and now we've inserted the dog word into our try.

84
00:04:52,190 --> 00:04:56,150
Let's say from here we were to research for the word dog.

85
00:04:56,630 --> 00:05:00,320
What would happen is that we would start from our roots and we would look for the first character.

86
00:05:00,740 --> 00:05:02,000
Is there a D?

87
00:05:02,330 --> 00:05:03,080
Yes, there is.

88
00:05:03,590 --> 00:05:05,350
And then from the D, is there an O?

89
00:05:05,630 --> 00:05:06,440
Yes, there is.

90
00:05:06,890 --> 00:05:08,500
And then from the oh, is there a G?

91
00:05:08,690 --> 00:05:09,470
Yes, there is.

92
00:05:09,620 --> 00:05:12,760
We've reached the end of the actual word search.

93
00:05:13,010 --> 00:05:17,060
But what about in our tree is the G an end character.

94
00:05:17,420 --> 00:05:21,140
We see that it is so here are searching successful.

95
00:05:21,140 --> 00:05:21,710
We return.

96
00:05:21,710 --> 00:05:28,070
True, but let's try and figure out if this works without the end character.

97
00:05:28,220 --> 00:05:30,440
Let's say we were searching for the word app.

98
00:05:31,040 --> 00:05:32,720
What would happen is we would start from the root.

99
00:05:32,750 --> 00:05:33,980
We would look for the first character.

100
00:05:33,980 --> 00:05:38,900
A it exists then P that also exists, then P after that.

101
00:05:39,080 --> 00:05:40,190
It's also existing.

102
00:05:40,370 --> 00:05:42,140
But we've reached the end of the word.

103
00:05:42,650 --> 00:05:44,780
Is this P an end character?

104
00:05:44,960 --> 00:05:45,740
It's not.

105
00:05:45,770 --> 00:05:47,810
There is no end value here.

106
00:05:47,810 --> 00:05:51,680
So this means that we return false for search.

107
00:05:51,980 --> 00:05:56,630
But this is different than if we were to call for the prefix of app.

108
00:05:56,960 --> 00:05:58,430
Prefix is a different method.

109
00:05:58,430 --> 00:06:03,650
It does not care about whether or not the last character that we go through with our traversal search

110
00:06:04,160 --> 00:06:05,930
is a good character or not.

111
00:06:06,140 --> 00:06:07,850
So we would once again start from the roots.

112
00:06:08,240 --> 00:06:13,010
We would look for the A, we would look for the P, then we would look for the P and we would reach

113
00:06:13,010 --> 00:06:14,090
the end of prefix.

114
00:06:14,090 --> 00:06:15,800
At this point, there could be more characters.

115
00:06:15,920 --> 00:06:19,210
It might not even be an end character for P, but that doesn't matter.

116
00:06:19,250 --> 00:06:26,000
We return true because we've reached the full end of the prefix word that we're searching for and all

117
00:06:26,000 --> 00:06:28,220
those characters exist in our try.

118
00:06:28,820 --> 00:06:31,340
This is the difference between prefix and search.

119
00:06:31,700 --> 00:06:38,150
Now, if we wanted the search to succeed, we would have to insert that word API into this try.

120
00:06:38,310 --> 00:06:41,660
So what would happen is that we would go from the root and we would look.

121
00:06:41,660 --> 00:06:42,920
Does the AI exist?

122
00:06:43,100 --> 00:06:43,640
Yes.

123
00:06:43,940 --> 00:06:45,230
Does the P exist?

124
00:06:45,230 --> 00:06:45,740
Yes.

125
00:06:46,190 --> 00:06:47,450
Does the other P exist?

126
00:06:47,450 --> 00:06:47,900
Yes.

127
00:06:48,290 --> 00:06:52,820
At this point, if none of these characters existed, we would insert them in, but they already exist.

128
00:06:52,820 --> 00:06:55,910
So we just continue to traverse down through the characters.

129
00:06:56,120 --> 00:07:01,610
But once we reach the end of the word that we're trying to build, then we say, OK, this P is now

130
00:07:01,610 --> 00:07:02,750
an end character.

131
00:07:03,260 --> 00:07:08,780
And now if we were to perform search AP again, we would start from the Roots, find the AI, find the

132
00:07:08,780 --> 00:07:11,870
P, find the P, realize that it's an end character.

133
00:07:12,050 --> 00:07:13,520
So here we would return.

134
00:07:13,520 --> 00:07:19,190
True, these are all the different conditions we need to satisfy when we build out our try.

135
00:07:19,430 --> 00:07:26,330
The main thing here is that we have that new prefix method on top of the existing try methods that we

136
00:07:26,330 --> 00:07:29,090
need to implement for any basic tried data structure.

137
00:07:29,660 --> 00:07:32,060
This is the trick question we have to solve.

138
00:07:33,120 --> 00:07:36,000
So let's go through our steps of solving this problem.

139
00:07:36,990 --> 00:07:42,240
The first thing that we need to do is verify the constraints, and here we want to ask the similar question

140
00:07:42,240 --> 00:07:48,270
that we asked with our previous interface design question can we implement any helper classes and objects

141
00:07:48,390 --> 00:07:49,580
to make it easier for us?

142
00:07:50,040 --> 00:07:55,050
And honestly, they'll always say, yes, you can use any features you see fit unless they're trying

143
00:07:55,050 --> 00:07:57,390
to challenge you in a different way just to test you.

144
00:07:57,690 --> 00:07:59,380
But most of the time they will say yes.

145
00:07:59,880 --> 00:08:04,130
So with that, we want to implement our tri interface.

146
00:08:04,140 --> 00:08:09,090
So take a look at this and remember that this is what you're implementing because I want you to try

147
00:08:09,090 --> 00:08:09,960
and do it yourself.

148
00:08:10,410 --> 00:08:14,010
So pause the video, copy this down so you know what you're implementing.

149
00:08:14,250 --> 00:08:19,350
And then let's move on to the next step, which is writing out some test cases here.

150
00:08:19,350 --> 00:08:24,300
I just want you to go through the previous test cases we walk through when we looked at what the question

151
00:08:24,300 --> 00:08:25,590
and these methods were doing.

152
00:08:25,800 --> 00:08:33,210
Just to give you a quick reminder here, what we see is that exact same try that we just built and the

153
00:08:33,210 --> 00:08:38,580
methods that we need to go through and to test that everything works is first we insert the word apple,

154
00:08:39,150 --> 00:08:40,680
then we search for the word dog.

155
00:08:40,920 --> 00:08:44,340
We know that dog doesn't exist at this point, so it should return false.

156
00:08:44,770 --> 00:08:49,350
So we insert dog and when we search again, now that we've added the dog, it should return.

157
00:08:49,350 --> 00:08:55,740
True, if we look for starts with app, this should also return true because we previously had inserted

158
00:08:55,740 --> 00:08:58,590
the app characters through Apple.

159
00:08:59,850 --> 00:09:05,730
But if we search for app, this should return false, because while we inserted Apple, we did not insert

160
00:09:05,730 --> 00:09:10,770
the word app, so we insert app and then when we search for app again, this should now return.

161
00:09:10,770 --> 00:09:11,140
True.

162
00:09:11,790 --> 00:09:15,740
These are the test cases that you want to make sure that you can pass with your try.

163
00:09:16,410 --> 00:09:20,000
So try and implement this solution yourself.

164
00:09:20,040 --> 00:09:25,270
Remember, we're building out a class and we're following that interface that you just copied down.

165
00:09:25,860 --> 00:09:28,600
So in the next video, we will solve this together.

166
00:09:28,860 --> 00:09:30,500
It's actually pretty straightforward.

167
00:09:30,510 --> 00:09:32,890
So you should be able to solve it pretty easily.

168
00:09:33,120 --> 00:09:37,860
There's just a lot of different additional edge cases you need to consider in terms of what character

169
00:09:37,860 --> 00:09:42,720
you're looking at, whether or not it's an end character, but it's a good practice for you to think

170
00:09:42,720 --> 00:09:43,210
about it.

171
00:09:43,260 --> 00:09:47,180
It's actually a really easy data structure as far as implementing it goes.

172
00:09:47,790 --> 00:09:49,200
So let's do that in the next video.