Tries Solution

[00:00:00]
>> Let's build some trees. So we know trees.test.js. And the first thing we're gonna do here is under the create tree, we're gonna create this new node with an empty string, right? Cuz remember I was telling you the root node needs to be an empty string. And then we're just gonna say for let i equals zero, i is less than words, dot length words being all the words that I'm getting back from the test here.

[00:00:35]
There'll be the city names. I plus plus and when I say const word equal words I and then we're just gonna say root.add word.to lowercase. We're gonna keep everything in lowercase here so we don't get too caught up on what's lowercase and what's not. Okay. So this is all we're gonna do for create tree, we're just basically going to put all of the logic here into the node.

[00:01:15]
Okay, here in the root node, let's make a constructor. This is gonna take in a string. I'm gonna say this children is an empty array. This dot terminus is what I call that, but you could call it whatever you want. Basically what I'm saying is like, am I on a valid word right now, right?

[00:01:42]
So, if I'm searching for Sandy. Sandy is going to be valid like a valid term, so, this will be true for that. And it will also have children, that's what I'm trying to illustrate there. This value is going to be equal to a string of zero, right? So the first letter is going to be of the string is gonna be its value.

[00:02:10]
So again, we're kind of trying to build B and then I'm gonna cut pass the string Austin to another node, and then the string stun and then t. Right, so basically this node is going to build itself with all of its children. And then I say here if string.length.

[00:02:37]
Is greater than one, so if it's more than just a character then I need to say this .children.push new node. Right, so we're gonna recursively create new nodes of string substring. One, basically what I'm saying here is, if you pass me Boston, I'm gonna make the value B.

[00:03:04]
And then I'm gonna create a new node in my children of oston. All right, cool. Else this dot terminus equals true Cool, all right. Okay, then we're gonna create another one here called add string. I wanna say const value equals string, zero, constant next equals string, dot substring one and then we're just gonna do a four.

[00:04:18]
Let i = 0, I is less than this, but children dot length I plus plus const child equals this dot children I. We're just kind of looking here for where we're gonna put our new string here whenever we called add. All right so cons child equal this dot children, then we're gonna say, if child's dot value, triple equals value.

[00:05:04]
Then inside of here we're gonna say if next is the particular next substring that we're looking for. Then we're gonna say child that add next. Otherwise else child dot terminus equals true, right? Cuz when we're adding something new either we have more to add or we've reached the end, in which case we're going to say cool.

[00:05:35]
This is a complete string right here. Yeah, and I got too many curly braces here. Okay, and then once we've found that here, we're gonna say return. Okay, and then inside of that. Instead of add. So here. So, outside of that for loop thumps, so for loop This return should be inside of this one.

[00:06:28]
Yep, okay, so line 38 should be here on 37. It should be inside of this if value here. Yep, okay, cool. I was getting confused there for a second. Then down here, we're just gonna say this.children.push, new node string. Okay, cool. So just kind of to work backwards through this or work forwards through it rather.

[00:07:00]
Whenever we're trying to add a new string, we're trying to get to the point at the end of this where we can just concatenate holistically a whole new node to it, right? So again, going back to here. We're gonna go if we're trying to add. I don't know.

[00:07:22]
Bolton, right, which is another city, we would start at the node we go to B, we'd go to o and then we'd see that there's no l here, at which points would say cool add lton here, right? So what this is doing is this is finding. It goes until the end until it runs out of places to go.

[00:07:40]
And then it says, cool, I found that place, add the rest of the new string. Unless, let's say we had a city for some reason called Bossed right, it would find here like, okay, this is the end and then it would just mark t as a terminus. And if called self good, everything's good to go.

[00:08:00]
So that's what happens here. Yep, that's what happens here in add. Okay, so let's write complete, so we're gonna say let completions, cuz we wanna find all of them. If you ask for San, we wanna get San Diego, San Francisco, all of those, so that's why that's an array.

[00:08:26]
And then we're gonna say, For let I equal 0. I is less than this dot children dot length i plus plus and when I say const child equals this dot children. I lm not gonna say completions Equals completions.concat(child). And we're gonna write a second method here called _complete.

[00:09:13]
This one's going to be like the externally facing that people are going to call this API. But we're gonna write our own complete internally called _complete with string empty string and array, and then we're gonna write a recursive method. That's actually going to recursively call complete on all of the children to make sure that we get all of the various different possible completions.

[00:09:41]
So underscore complete here, we're just gonna write that above. And it's gonna take in the search string, so the one the string that we're building, okay? So search we're gonna take in built which we've stuffed we've already built so far. And then we're also going to take in, they already made suggestions, right, because you might get multiple suggestions for completions whatever you wanna call it.

[00:10:09]
So we're gonna say if suggestions.length is less than or equal to 3, and sorry, the suggestions rather. We're only gonna start autocompleting if they've typed three things in, right? I'm sure you've noticed that on Twitter you have to type like three things and if you're looking for something or otherwise won't complete it.

[00:10:35]
That's what that's doing or search and search 0 is not equal to this dot value. So this is saying, hey, you called complete. This is not a match with the particular element I'm on. So let's say I was searching for BO, and I was on the A child is a K.

[00:11:03]
This doesn't match, so I'm not gonna do anything here, I'm just gonna return right away. In either one of these cases, what we just wanna do is we just wanna return the suggestions. Okay. So if this terminus if we found something that is a complete thing, then we're just gonna say suggestions.

[00:11:33]
You know what I was, the suggestions here is the completions. I'm sorry, remember what the exact code I wrote here [LAUGH] So the suggestions here is all the ones that we have found so far. We're only gonna suggest to up to three at a time right? If someone starts typing San and you suggest them 700 cities named San they're just gonna get overwhelmed.

[00:11:55]
So in this particular case, we're just going to suggest them the top three. So suggestions dot push and then hear what we're gonna say it was gonna put built Built, And this star value. So built so far like so if we're searching for Boston, right? This is going to find built, which will get to bosto, and it's gonna find N as the next one being the terminus, right?

[00:12:32]
In which case, this will push into the suggestions Boston. If you feel like this is more clear, you can also do. In fact let's just put it that way, built plus this dot value, that might be a bit clear. It's just string concatenation, I was doing it with a template string before, okay?

[00:12:58]
Then under that we're gonna say this dot children. And then yeah, let's just do it this way for let I equals zero. i is less than this dot children dot length. I plus plus, and we're just gonna say child. Complete, sorry, child dot underscore complete. Where we say const child is assigned this.children i, like that.

[00:13:38]
Child.complete, search.substring one so everything from the first character, so you cut out the 0th element of this. So again, if we're searching and we typed b, we'll cut this one out and then we'll pass that one on, right. So that's what that's doing. Built plus this dot value and suggestions.

[00:14:15]
And, you can say suggestions equal here if you want to. It doesn't really matter, because we're operating directly with on suggestions we say, push here, right? But if you want, you can say suggestions equals child like that. And then at the very bottom here, we're gonna say return suggestions.

[00:14:46]
All right. So I think that should be it. Make sure that my stuff works here. One failed skimmer that path finding madness log maze. Okay, they're, there, let's try that again. So let's pop into why our test is failing. Completions is undefined, that seems like it could be a problem.

[00:15:36]
It's because I don't return them. Start with that. Return completions All right, so this one complete is still undefined. Not sure what I did here, all right, one more time. There we go, and does that is passing now, okay? So this is how you basically do type ahead like this.

[00:16:30]
I don't know if this was invented at Twitter, but certainly Twitter's one made it popular. Of everything that I've showed you today, trees are actually one of the more recent innovations in computer science for dealing with type ahead. Again, it's still depth first traversal on the tree, right, which is something from the 50's, 60's, 70's, probably even before that.

[00:16:49]
But using it as like a type of head kind of guests UI trick. That's more more of one of the recent innovations here. All right, any questions about trees?
>> So to add more order to say words, you would add weight to them, right. That's how we would solve the problem.

[00:17:13]
>> Yeah, so let's say one of the words was more important than the others, right? Like let's say you want to suggest, based on population, right, that would be like a good indication you can suggest. Boston before bountiful, right? In this particular case, the way that we did it here, you would just add Boston first, right?

[00:17:30]
And that would make it come up first. So you could do it that way. The other thing you could do is you could put exactly what you said which is like a priority or a weight or something like that. So you'd have to do all of the completions and then you'd have to kinda sorted out by which one had a higher priority.

[00:17:45]
Or actually probably a better way of doing that is, every time you added something new, you would just make sure that it would be reordered so that the higher priority ones end up being higher, right? Cuz the advantage of this tree is that if you go down here to the suggestions, this part right here.

[00:18:03]
This actually quits after three times, right? So, it's actually quite fast, so, it can do completions really, really quick. And if I have to go do all of the completions every single time, every time that I type B, it's just going to slow to a crawl right? Before it does all of those completions.

[00:18:20]
So that's why I would be inclined to say is that you should build the data structure in such a way that the higher priority ones come up first.