Java Interview with a FAANG engineer.

Trie Word Search with Wildcard Matching

Interview Summary

Problem type
The Problem: Trie-Based Dictionary Word Search with Wildcard Support

Interview question
Given a dictionary of words, implement a data structure that efficiently answers whether a given search term exists in the dictionary. Start with exact matching, then extend the solution to support a dot (.) wildcard character that can match any single letter at any position, with any number of dots, similar to a simplified regular expression. The extension was originally framed as counting how many words match the pattern, then simplified for time to returning whether any word matches.

Interview Feedback

Feedback about Digital Tornado (the interviewee)
Advance this person to the next round?
No
How were their technical skills?
3/4
How was their problem solving ability?
3/4
What about their communication ability?
2/4

I would spend more time asking questions about problem scope. Not asking about the size of the input dictionary is probably reasonable here (because any conceivable dictionary should probably fit on memory for a modern PC) but you will get dinged for it in real interviews. When using Java especially, it would be helpful to briefly touch on the classes/interfaces you are setting up. We had some confusion about whether methods were meant to live inside the class or be 'top level' utilities to run the code. You made a method static without ever saying why. Overall, I would expect someone at your level to be able to more clearly communicate your coding changes as you apply them without slowing you down much. Your reasons for using Node[256] were sound, but you could have explained it preemptively to get some extra points. The biggest issues were:

Feedback about Ubiquitous Donut (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4

Interview Transcript

Ubiquitous Donut: Hey, can you hear me all right?
Digital Tornado: Uh, yeah, I can hear you. Can you hear me?
Ubiquitous Donut: Yeah, great. Uh, thanks for joining me today. Uh, I'm gonna be doing— this is a, like, algorithms and data structure interview. Just want to make sure we have the same expectations about that.
Digital Tornado: Yes.
Ubiquitous Donut: Okay, great. Um, so the The profile said that you're an experienced engineer, that you've got like 8 to 10 years of experience. Is that correct?
Digital Tornado: Uh, yes.
Ubiquitous Donut: Cool. Um, without, you know, getting too into personal details, uh, you want to share just like a few sentences about the type of work that you've been doing so I can kind of calibrate the questions that I should put more emphasis on during the interview?
Digital Tornado: Oh, yeah, so I do like infrastructure, like kernel kind of work, so like distributed systems, operating systems kind of stuff. I currently work on kernel networking within the Linux kernel, and I mean, like starting to look around a little bit, you know, just to, you know, like see explore the market and see what's available.
Ubiquitous Donut: Yeah, for sure. Okay, that's great. I have a similar level of experience as you do, so this should go pretty well, hopefully. Oh, okay, cool. So the problem that we're going to be dealing with today is about searching for words in the dictionary. I'm hoping that with your level of experience, we'll be able to get through the kind of basic implementation and then also get into some of the, like, harder extensions for it. Um, so let me, let me grab some stuff here. And are you going to be using Java for your implementation?
Digital Tornado: Yes.
Ubiquitous Donut: Okay, I might need you to help me understand how some of the libraries or standard library stuff work because I'm pretty rusty on that. But what we're going to do today is we're going to take a dictionary, and what we want to be able to do to start with is just to find a way to confirm, given a search term, whether or not it exists in the dictionary.
Digital Tornado: Oh, okay.
Ubiquitous Donut: Pretty basic.
Digital Tornado: Oh, okay. So you have like search terms, like something like this. And yeah, you would match— you would just— it's just true or false, right, as to whether the term, or any one of these words in the dictionary is essentially some subword of the target, right?
Ubiquitous Donut: So I think that you've actually made an even harder version of the problem. To start out very simply, we're just doing exact matches.
Digital Tornado: Oh, exact matches. Oh, okay, interesting.
Ubiquitous Donut: Okay.
Digital Tornado: Yeah, sure. If it's just an exact match, then— so it's just a HashMap, right? Like you would take— you construct a HashMap with your dictionary at the beginning where each of these words gets— or a HashSet rather, right? Which underlying is a HashMap. And then you would match your target with the hashtag, right? And it would, yeah, that would return true or false for you.
Ubiquitous Donut: Yeah, that's one way of doing it. And that's great while the size of your dictionary is very small, right? But let's say that we were going to do like every word in the English language plus maybe a couple of other languages too. Let's pretend that we're working in an environment where the amount of memory that we're using was kind of a concern. So you're totally right that you can use something like a HashSet to do this very simply. But with those added constraints, do you think there are some other ways we could think about the problem?
Digital Tornado: Yeah, so like a word tree. So you construct a tree. with your entire dictionary. And each letter is basically a node along the tree. And you, so like cat would be like, you know, first, the first from the root, the first, you know, you take this, you take C if it exists, right? And then you take A and then you take T. Until you hit like, so I mean, you would have like something like this, right? Where, so I mean, this, This kind of depends on like what kind of symbols we have available, but a character is like— a character is 200— there are 256 characters, so you could do it this way where like you essentially use a map. But yeah, but basically you construct a tree with your dictionary using this node, right? And the node will give information on whether you're currently at a word or like, you know, and what the next available letters are. And you would, yeah, I mean, you would essentially like look for your target this way, right?
Ubiquitous Donut: Right.
Digital Tornado: So, yeah.
Ubiquitous Donut: And what would be the advantage over this compared to the HashMap if we were looking to really save on the memory that we were using?
Digital Tornado: Yeah, so you don't have the duplication, right? So like with a HashMap, every word has mapped to a different, like is a different entry within the HashMap. Whereas here it's, if these words contain each other or overlap in some way, that doesn't use extra memory, right? Or that uses very minimal extra memory. So that would, yeah, I mean, you're not, you don't literally have as many nodes as you have words. So yeah, whereas the hash map is like the space is like O of the number of words that, like, the number— the SAS dictionary.
Ubiquitous Donut: Okay, great. Um, yeah, I, I think this is a good place to start. Why don't you go ahead and implement this, um, this implementation and we'll take it from there.
Digital Tornado: Okay, yeah, sounds good. So, um, yeah, so I can—
Ubiquitous Donut: And, and also we can assume that They're, you know, English alphabet symbols that will fit in characters. There's no like Unicode nonsense going on.
Digital Tornado: OK, so, um, yeah, so, uh, so it's like that. Something like this. So I mean, like, I guess, like, Oh yeah, so we'll have like a class representing the tree where we construct the tree from the, from the node class. Um. Okay, and then we give it a list. So for each string word, okay, so for each For each word, right? So let's go ahead and do it.
Ubiquitous Donut: Uh-huh.
Digital Tornado: Uh, we're just initializing a tree, uh, to, uh, to hold all our words or to hold our dictionary that we're going to search through.
Ubiquitous Donut: Right, it makes sense to me. I'm not interrupting you just so that you can finish the Java boilerplate. Digital Tornado: Yeah, of course. Then, yeah, so if— by the way, this is a Okay. To note it, right? That's 2 and inch. Okay, so. It's not this. And then Yeah, so whether or not it's a word is—
Ubiquitous Donut: Would you mind refreshing me on what the object.is_null here is doing?
Digital Tornado: Oh, it's just a null check. I mean, it's easier— I could just do an equivalence check for null, but typically, typically it's— I mean, I typically like to write it this way because it's like harder to make mistakes with it because like the typical way— the other way you can do this is like, you know, this is apparently easy to get wrong this way, like if you flip it. So, but yeah, it's really just this.
Ubiquitous Donut: Because in Java, when you declare that new array of length 256, all the values are null. Yes.
Digital Tornado: Yeah, so it's going to be null initially, so you have to make sure it's not null if you're going to take this entry.
Ubiquitous Donut: Um, okay.
Digital Tornado: Yeah, so, uh, but yeah, we're just constructing the tree here, um, and making sure all the nodes exist. Um, so if it doesn't exist, uh, just, uh, Create a new node and take that node, and this will initialize the the words in the dictionary into the tree. So yeah, so here search. Dictionary. So, um, yeah, so here, okay, a tree dictionary, right? So initialize it. Now we're going to say, um, Oh, excuse me, this is Boolean. Yeah, so here we'll just Right, um, just convert this to an inch. Uh, we say like, okay. So initialize it like this, the root, right, or the stock root. Class WorkTree. Oh, uh, WorkTree stock root. Okay, and then a Yeah, so this is the root, and then you're going to, uh, zoom in. All right, so if your current is null for whatever reason, just return False. If not, then equals, you know, current.x_index, and then you return All right, so you really just return that it's both, you just return that it's both not null and is a word.

Ubiquitous Donut: Correct.
Digital Tornado: Yeah, so here you just say like find the word in dictionary. Yeah, so finds. Mm-hmm. Okay. Yeah, so this will— this basically just traverses the tree, the word tree that you constructed initially, and we'll just find the— just, it goes to the node, or it searches down the word tree. And it will, you just assert that the node that you end up on is both non-null and is a word, so has that flag set. But yeah, so this was—
Ubiquitous Donut: I think that makes sense conceptually. I've got a few test cases that we can use to actually run it and make sure that it's working as intended. So I'm going to put them up at the top. by the original dictionary. And it would be great if you could do whatever you need to do in Java to actually run those 5 cases and see if the results match.
Digital Tornado: Yeah, of course, sounds good. So yeah, the fastest way we'll do it is just actually run it. So, Did it not have something? Root, root. Okay.

Ubiquitous Donut: I'm, I'm a little bit confused about why we have both a constructor for this word tree class as well as a, uh, a method there in the class. That also constructs the word tree, is that meant to be outside of the class?
Digital Tornado: Yeah, it's meant to be outside of class too. Okay. Yeah, so, um, uh, yeah, so right here. Static cost is static. Hmm, it's interesting. What doesn't it like here? Oh no, I think this is not supposed to have this, is it? Yeah, boolean error. Okay, static cost is static cost is, and then, uh, oh, I think you're missing a bracket. I think, yeah, it's missing a bracket, right? So Yeah, okay, cool. So method— That's an extra one. Yeah, there's an extra one here. Okay, excellent. So then I think we can just, uh, Boolean this, um. I'm sorry, I couldn't hear through the audio.
Ubiquitous Donut: I think for these test cases, since we only have a couple of them, it's probably fine to just print out the Boolean result and we can just make sure that it's true, true, false, false, false.
Digital Tornado: OK, yeah, sounds good. Um, uh, yeah.

Ubiquitous Donut: Could we not do this?
Digital Tornado: Yeah, I thought— are you— there's some— is there something like this? Yeah, is there? Um, okay, how many words are there? 8, right? Yeah, so 8 words. Maybe. I'm not sure if there's— it may or may— there probably is. Yeah, there are some. I can't remember off the top of my head at the moment. Let's see here. Cardcare@barbear. Dictionary and the target is a— okay, so— okay, that's— we will fix the efficiency of this in a little bit because it's recreating the tree every time.
Ubiquitous Donut: Um, of course, I, I don't mind that.
Digital Tornado: Um, dog CA cars. All right, let's try it. Oh, okay, something's wrong. So our tree Yeah, I said okay. Uh, let me see, it's stuck somewhere. Um, let me see, is there— what do we do here? Let's get here first. Okay, so, um, Okay, C-A-T, yes, and then R, and then C-A-R-D. Oh, so D, okay, that's correct. E, B-A-G, and then next one should be R. Okay, yeah, R, R, and then E. Okay, and then apple, right? Okay.

Ubiquitous Donut: So Does this match what you're expecting to see when you're going through the process of constructing the trie?
Digital Tornado: Yeah, this is what I'm expecting to see, right? Because I'm printing out when it constructs the new node. So it should be just when it's taking a— it should be when it's taking the—
Ubiquitous Donut: Yeah, when it's like diverging to a new branch, right?
Digital Tornado: Yes, exactly right, which looks correct so far. So let's, um, let's just print out a bit more. Okay, okay, so Okay, so I expect this to look a certain way too. Let's see.
Ubiquitous Donut: Okay.

Digital Tornado: False, false, yeah. True, true, true, yeah. Okay, okay, I see. So then apple, it should all be false until the last one. Okay, true. Okay, excellent. So then I think it's not, it's not here. So let's look at find_word. So equals index not exists. The first one that's incorrect is cat, right? So it's saying cat is not a word.
Ubiquitous Donut: To make sure I'm following along correctly, when we, when we created tree of words, we were able to verify that the is_word was set correctly for the letters that we were expecting, right?
Digital Tornado: Yes. So yeah, so this was correct. And then We're looking at the find word right now to make sure that the— yeah, actually, because for that reason it's not finding that the current equals current.next, right? And The cat_t is false. And, uh, yeah, because t is the next index that you're taking.
Ubiquitous Donut: So what I think might help is to remove all the other words from the dictionary and focus on a very simple case where there's only one word.
Digital Tornado: Okay, yeah, so yeah, yeah, so we're just looking at the first one, which is the Uh, the cat. So, um, I wonder if maybe there's a better way to write this to like avoid this problem. Uh, let me see. So, C-A-T. See. The current.is_word, right? Maybe this is always null. Is it? Oh, I'm not sure. Yeah, just kind of comment the other ones out for now.
Ubiquitous Donut: So I think you have to move this is_word after you reassign to current, right? Because on your first iteration, current is the root. And then we look at the first letter, C, and the index will be 0 because it's, it's the first letter in the word, right? Um, but then you check the current is word, but current is still the root at that point.
Digital Tornado: So, yeah.

Ubiquitous Donut: So you're kind of one behind where the actual pointer for the iteration through the tree is. Digital Tornado: Yeah, I noticed that. Um, let me see. cat true, current is not equal to null. Oh, but, uh, current is not equal to null, right, at the end? cat. Current's not equal to null. So then this is false. This means it's the— oh yeah, so then it's the is word. Oh, did we set this incorrectly? Hmm. Yeah, we're at the correct node. Uh, did we set this? Let me see. False, false, true. It took t, right? Current subindex dot next subindex equals So next, right? Let's see. Return true, else return false. current.next subindex equals null, right? Current It should never be true, right? Like, uh, see, yeah, it should never be true. But then at the end of this, right? Yeah, exactly. At the end of this, it should always be— it should always be true. Uh, yeah, so this— Oh, hey, there we go. At the end of this, it should always be true. It's not. Okay, I think that's where it is. So current equals current.next. Uh, so you create it if it doesn't exist, right?
Ubiquitous Donut: Um, yeah.
Digital Tornado: Oh, did I— oh shoot, this is a constructor here. Okay. Okay, that's kind of— yeah, it's the constructor there. Okay, okay, I think this should be correct now. Yeah, that's kind of, uh, it's unfortunate.
Ubiquitous Donut: Um, true after every word, which is what you'd expect.
Digital Tornado: Yeah, that, that's what you expect, right? And then like, yeah, yeah.

Ubiquitous Donut: when it's searching that it's finding the is_word true at the leaf nodes.
Digital Tornado: Yeah, so true, true. I think this is— don't clear this. Let's see. Yeah, okay, there we go. Yeah, that's unfortunate, but yeah, okay.
Ubiquitous Donut: Okay, I'm actually gonna add one One additional word to your dictionary, because I think there may still be an issue with this.
Digital Tornado: OK, let's try it.
Ubiquitous Donut: Oh, and then I gotta add the test case as well. Right, so we expect the first one to be true now because we've added the word cat. I'm searching for the word cat.
Digital Tornado: Oh yeah, there is an issue with it. There is an issue with it, yes. So you need to, at the end of this, you have to say like, yeah, because I think if If you have cats initially, uh, the cats gets overwritten, right?
Ubiquitous Donut: Yeah, because if you, you have a longer extension of a word, you're only setting it, uh, if you're adding a new node. But if you do cats first and then cat, cat is shorter and it's a substring. Or prefix, I guess. And in that case, you never add a new node, so you never set is_true. Okay, can you— so I think this is a good place for us to stop the first portion of this. Now that we've implemented and we've got it running, could you tell me a bit about the space and time runtime complexity for this?
Digital Tornado: Mm-hmm. Yeah, so I think space complexity is still worst case O, right? Because they can all just not— or excuse me, so it's O of like— okay, so yeah, I mean, they can— the worst case is still O, right? Because you can just have words that don't overlap at all. And you have to create— it's O of the number of letters in the number of words, the space complexity, right? 'Cause that's how many nodes you're gonna need. Yeah, and the time complexity will be like O of the length of the target, 'cause that's, you know, you search through the target in the trie to get to the target word.
Ubiquitous Donut: Right, and you've implemented it not using recursion, so there's no, uh, like stack to keep track of.
Digital Tornado: Yes.

Ubiquitous Donut: Although even if there were, the size of the stack would also be, uh, growing at the same rate as the length of the word that you're searching for, because you'd have one stack frame for each, um, letter if you were doing it recursively. So that It doesn't really matter either. Um, and can you tell me why are we not using like a precise node? Affects the, uh, like what, what are the benefits or drawbacks for using that for the space and time complexity?
Digital Tornado: Oh yeah, of course. So the precise node, you do allocate a specific amount of space, um, to So you implement, you allocate a specific amount of space at the beginning just for this node and most of these entries are gonna be empty or, okay, so a lot of these entries will be empty. So here, I mean, if you want to, so it's actually, it's a constant times the number of letters times the number of, because the node size is constant. If you use like a HashSet, You will, uh, you know, um, that should save you on space because like the HashSet cannot be smaller in size than the, uh, um, than this, this array.
Ubiquitous Donut: I just use the array here because it's like, it's, um, it's just a little like, uh, easier to, uh, so it's using the array as a, uh, as a HashMap. So I just like, uh, I just, I personally find it a little cleaner to like just to implement it this way. But yeah, it's like it does use extra space, like it costs a lot of extra space.
Ubiquitous Donut: And I think that that's like a very good academic answer. Also, like thinking about the reality of using Java, like the overhead to allocate a new HashSet is probably bigger than an array of 256 pointers. So even if you were going to do that, like, it's probably more space to use the hash set than it is to use the array of nodes.
Digital Tornado: Yeah, a hash set is an abstraction on like something else that it's doing. So I don't know how much that preallocates, but It's, yeah, it's just kind of a— this might still get you better performance and better space in practice, basically.

Ubiquitous Donut: Probably, because you can just do pointer arithmetic to jump directly to the letter that you're interested in. So I actually agree with you that this is, if you really want to get into the weeds, this is probably the best way to implement it.
Ubiquitous Donut: Um, okay, so, so that's great. Um, let's think about, since we've got about 10 or 15 more minutes, um, making this problem a little bit more interesting, a little bit more challenging.
I'm going to presume that you know what a regular expression is. Digital Tornado: Okay, yes.
Ubiquitous Donut: Um, you know, regular expressions, actually implementing them is, you know, very, very complicated. But what I'd like us to do is support like one part of that syntax where we can do a search for— what's a good example? Like search for CAR NOT. Right, so in a regular expression, the dot syntax represents any character. So in this case, it would match against 2 words in our dictionary. It would match against cars and card, right? Because in both cases, C-A-R needs to be exact match, and then there's a single character that comes afterwards that can be anything.
Digital Tornado: Oh.
Ubiquitous Donut: And of course, Before we were asking, does this word exist? That doesn't really like match the new way of saying it. I guess one way that you could say is like, does any word matching this exist? But what I'd actually like to know is, uh, like, like how many words match this, and it should return 2. There's 2 words, card and care. Digital Tornado: Oh.

Ubiquitous Donut: Card, care. Oh no, it's only 2. I'm sorry, I'm getting confused. Because this word is not— the only words that start with 3 letters and then have something afterwards Um, is card and care. Does that make sense?
Digital Tornado: Yes. Okay.
Ubiquitous Donut: And this dot could be, uh, in any position, um, and we could have more than one.
Digital Tornado: Oh, okay. Yeah, that's fine.
Ubiquitous Donut: Um, we could do that, um, which actually would still only match 2 but would not match Because the second dot wouldn't have any characters to match car.
Digital Tornado: Yeah, yeah, I think I see where this is going. So the way we would do this is just recursion. You have a dot character, right? And that means basically you search along all the indices within— at this position, right? So what I would do is like basically I would have my— I would reimplement the find_word to iterate if it's a concrete character and to recurse on all the indices that are non-null if the index— if the character at the current index is a dot.
Ubiquitous Donut: Okay.
Digital Tornado: Yeah.

Ubiquitous Donut: I think that that is a good place to get started. Why don't you go ahead and give that a try, and we'll see if we can finish it in the time that we have left.
Digital Tornado: Okay, sounds good. Yeah, string word. So I would write it this way then. So like int index.
Ubiquitous Donut: Yes, sir.
Digital Tornado: That's our helper. Um, let's start root.
Ubiquitous Donut: Yes, sir. Yes, sir. Digital Tornado: It's the end of the word, return. Uh, if word.character index is a So if it's not equal to null, Oh, then, um, for the, uh, Uh, current.next. Uh, is it current.next? Oh, excuse me.

Ubiquitous Donut: Oh, we didn't add any.
Digital Tornado: Oh, we didn't add any. Yeah. So what's the next one? Uh, ca.do— oh, oh, um, is it still returning true or false, or are you adding 1? I guess it's—
Ubiquitous Donut: Uh, the idea was to return the number of matches. But just looking at the clock here, let's just have it if it finds any matches.
Digital Tornado: OK. I mean, I think it's like a one-line change to get the total, but that's OK. So let's just try ca.. Maybe like .ca, which I think should be false.
Ubiquitous Donut: Yeah.
Digital Tornado: I'm going to add a few as well.
Ubiquitous Donut: Okay, okay, there we go. That's fine. Reset this.
Ubiquitous Donut: Um, I'm gonna run it one more time. Oops, I'm gonna clear it and run it one more time, make sure my last one got in there.
Digital Tornado: Oh, there's this one.

Ubiquitous Donut: Okay, so I think that final one is problematic, but we don't really have time to, to go through the debugging of it. But this should not have matched anything because there are no 5-letter words that end with a D. So likely that has something to do with either the seed length or how you're using the root node. So that might be just something that would be good to think about afterwards to see what you might have to tweak to get that one to work.
Digital Tornado: Okay, I see. Yeah, no worries. Well, yeah, thanks a lot for taking the time out to speak with me today.
Ubiquitous Donut: Yeah, for sure. I hope you found it useful, and I was taking notes during it, so you'll get some feedback on, on what you can improve on.
Digital Tornado: Mm-hmm.
Ubiquitous Donut: I think, like, it's very clear that you, like, know how to do this stuff. I'm not sure at what point you are in your job searching progress yet, but I think that the new things that gonna make these go more smoothly for you is a couple of tweaks from like the communication side of it, of, uh, what you offer up before you start coding. And then also when you're doing the programming, I'm just practicing being a little bit more verbose.
Digital Tornado: Okay, yeah, thanks. Yeah, yeah, thanks a lot.
Ubiquitous Donut: All right, have a great day. I'll see you later.
Digital Tornado: Yeah, you too. All right, bye.