Data Structures: Solve 'Contacts' Using Tries

Key Takeaways

Hi, I'm Gail Lock McDow, author of Crack and Coding Interview. Today I want to talk about the contacts problem. So in this problem, we are asked to implement a very very simple contact list. And the contacts list will need to be two different need to do two things. It will need to first of all add things to it. But then it will need to given a string figure out how many contacts start with that string. So, of course, one way we could do this is we could just store this in a giant list or something like that, maybe a sorted list, and walk through and for for any given string, just walk through that whole list and see do ask each string, do you start with this substring, do you start with this, do you start with it? But that'll get pretty inefficient. This is the kind of problem though that a try is perfect for. So, all we need to do essentially is just build a try for ourselves. So store all of these people into a try and then when we get a string just walk to that try and say and then when walk through that try with that substring and then we get to that substring say okay how many children do you have so that's the basic implication and that's what we have to do. Now one little optimization is you know one thing we could do is when we get some substring find that node and then walk through all of its children and count how many there are. But even easier actually is just count let each node in the try actually store how many children it has. It's just you know that's actually a very easy thing to keep track of as we go and it'll make our code actually a lot more efficient. Also shorter to write as it turns out. So we'll go ahead and take that approach. So I've already started us off here with the basic outline of how the tri will work. I've used here I've you know just created a node class not not I don't need right for this problem an overall try class um so I've just created a node class and it will store each child and by the way in this charact this problem we only have the characters a a toz lowercase it's very very simple so what I've done is I've created a simple array that has 26 slots for each possible letter. Of course, if there is no next contact that starts with that letter, then it's going to be null. Um, you could also, if you wanted to, use a hashmap instead. And that actually has some benefits. It takes up more memory, but it's more flexible if you need to change this, change certain things about it. So, if you found this problem really overwhelming, here's a good place to stop and retype this code yourself. And now that I've outlined the basic stuff, see if you can get the rest of it. But I'll go ahead and start writing this. So get node is going to need to get it's going to going to just get the node that's at that value. So um one function that I bet will be useful for me and this can actually be static is given a given a character return the the index in that array because I think both getting and setting will need that. So that's going to be done. It's, you know, it's actually very simple. It can actually just be done like this. Um, but it'll be a little bit easier for me to do it that way. Now, get node is just going to return children of the char index. And for set node not too dissimilar get the char index of C and set that equal to node. All right. So what AD will do as add is our next function. And what AD will do, and we can actually add this, give ourselves a little um initial method, but what AD will do is we'll walk through recursively, and it'll pull off the next charact pull off each character of an S walking through it. And then once we get to the end, uh the end of S, it'll insert a node there, or it'll insert, actually, it'll insert nodes as we go along as necessary. So, and again, we're going to start off with the very first character of S. So, if I'm at the end, if index is at the end of S, then I'm done. Nothing to do. Otherwise, pull off the current character of s at of index and then uh I'll call this char code actually. And then I'll do get char index here of current. Oops, spelled that wrong. Okay, now I'm going to say, hey, check if this even exists. So, check if there is a child for this character. Um, so I'm going to do get node of char code. Actually, I guess I just can just call current here. Now, if child is null, then I need to create that child. So if so then uh set node of current, new node and actually I want to get the value here. So child is going to be new node child and then go and recurse call child.add of s comma index + one. Now the other one other thing I have to do here is I have to track how many characters how I need to know how many there are and let me hold off on that and go down to this find method. Now let's turn to how find count works. So what find count is going to do is it's going to also operate recursively and it's going to walk through the nodes for each character of S traversing this tree for each character of S. And then if there's no next child with the right character, then I return zero because that string that substring actually can't be found. Or if I get to the end of S, then I return the current count. So this is going to require me to actually keep the current count in each node. So I need to have this size variable here. So I'm going to keep the size of each node. Now what's going to happen is as I every single time I call add on a string a string actually gets something actually gets added beneath that. So every single time add gets called I just have to increment the size. Then on this find count what I say is if I'm at the end of S then return the size otherwise go to my next node. So I have to first of all get my next node. So node node at equals get node of s.chart at of index. If the child is null, return zero because there's actually nothing with that substring. Then otherwise recurse and do find count of x comma index + one. Okay, so that's how I implement this. Now let's run this and see how we did. All right, it's looking good. So that's this is a really really simplistic implementation of a try. We could if we wanted to do a hashmap instead of a simple character array, but for this problem because of the simplicity of it, a character array is sufficient. So it's, you know, it seems like this really overwhelming thing to, oh my god, I have to implement a try. But ultimately, it's really not that bad. Just think very clearly what does implementing a try really mean. In this case, it just means we need to have these, you know, this ads method. um this find count and we need to do some basic getting setting operations. It's really not that bad in the end. So keep keep tries in mind as a really really useful data structure for interview questions. What I've seen is a lot of times when you see a problem where that's framed at where there's some sort of validation against some other input, that's where you often end up using a try. So keep that in mind as you do future problems. Good luck.