# Java Interview with a Microsoft engineer

### Interview Summary

Problem type

Word transformation search

Interview question

Given a grid of characters and a list of words, return a list of all words that can be formed from the given grid. The output should be in the form of a list containing: starting cell, word, direction. You can move in all 8 directions about a cell but once you start moving in a particular direction, you must stick to it.

### Interview Feedback

Feedback about Concomitant Coyote (the interviewee)

Advance this person to the next round?
No
How were their technical skills?
2/4
How was their problem solving ability?
3/4
4/4
1/4

Feedback about The Legendary Avenger (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
4/4
1/4

### Interview Transcript

The Legendary Avenger: Alright what about now? I tried to refresh it.
Concomitant Coyote: Yes, now it's fine.
The Legendary Avenger: Awesome. Yeah, I hope you're doing well.
Concomitant Coyote: I'm good, thank you. How about you?
The Legendary Avenger: I'm okay, it's quite late for me, but should be good. Alright, so I'll just get straight to it. So here's the problem I would like you to solve today. And just so you know, this is a problem I was recently asked by Tiktok. And obviously, as engineers, we always want to share all of this. So it's a pretty nice problem at least that's what I thought about it. And the whole idea is you're given a grid, and this grid contains a list, it's a list of letters. And you're allowed, and you're allowed to move in all the Von Neumann directions. So from a you can go to another A, you can go to D but here's the catch. If you start moving in a particular direction, you have to stick to it. So if you're going down, going down, you're going left to stick to going left if you're going right stick to going right and you're also given a list of words a dictionary set essentially and your job essentially is to return all list of words that can be formed from from the given grid and the output format should be as follows. So it should be starting at point so you can you can return it in you know a tupple or a list and so it should be p one p two to identify the cells points are the cell that you starting with the word as well as the direction. As for the direction. So this is what I would prefer you do so for the direction you can prefer, you know, assume you assume you're on the 00 cell. So if you're on the 00 cell, if you're to move right, then you would obviously be going zero to one, right, you're not one zero to one, one to zero, like you'll be holding the y constant and move to the right. If you're to move left, it's the opposite, right? Negative one to zero. Make sense?
Concomitant Coyote: Okay.
The Legendary Avenger: Yeah so you know, if your diagonal, obviously, if you're going up diagonals, it's negative one, negative one. And if you're moving down diagonal, then it's one one. If you're moving from current cell to left, so you I think you get the gist of it, right?
Concomitant Coyote: Yeah.
The Legendary Avenger: Yeah, so I will need a set of three, three outputs for all words. So for each of the words, you will give me a cell the word that's the word that corresponds to the output as well as the direction and you can make the output a list of lists containing all the words as well as the starting points as well as the direction that you want to go and the direction should be in this form. All right. Does that make sense?
Concomitant Coyote: Yes. So you said that, a few clarification that. So when you say so if this is the AC case of the first line say back, so that's my one direction. So it is going to right. And then we can change the direction after that. And then the output would be
The Legendary Avenger: If you if we say we had another word, let's say Backy here, like that, we had another word. Let you know just randomise this. So if we had the word backy in this, then I'll still expect both the word Backy to be input. In fact, if we had if we had yob here, so we will, I would expect both back backy and yob as part of the output.
Concomitant Coyote: So why would we go yob because but we change the direction now right? So we can say after we find the word, then we can change direction.
The Legendary Avenger: Yeah, so after we change there, after we find the word, we can change direction, that's not an issue. So you know, for yob we obviously have a different starting point in light of the word like considering the word yob, as an entity, it has a different starting point as well as a different direction. So it's totally okay to change direction once you found the word.
Concomitant Coyote: Okay and so how will the output be? So if I start so the P one is the start of the word and P two is the end of the word.
The Legendary Avenger: No, P one is the starting coordinates. So if for Backy, for instance, I'll give you an output format for Backy. So for Backy it will be p1 01, word is backy right? And the direction is, let's see and the direction here will be? What's the direction for that?
Concomitant Coyote: So the direction would be we're going toward right that will be zero comma one.
The Legendary Avenger: Yeah, so we only changing the y coordinate and not the x coordinate. Is that right? Or I actually it'll be one zero, because which, which
Concomitant Coyote: we are changing no we are x is constant and we are changing our y's.
The Legendary Avenger: But the case because you're coming from B to A,
Concomitant Coyote: Oh because it's a directional graph. Yeah so x is a one but why one comma zero, because y is it not moving? Okay, one comma zero, then?
The Legendary Avenger: Well, yeah, yep. So the direction will be one zero, because you can imagine if we were to hold this constant, then we are still in the same index. Index. Actually, you might be right, we still in the same index X, and we'll be incrementing. This with 01 02? You actually right? We Yeah, it's totally okay. We can call this 01 Here.
Concomitant Coyote: Yeah I mean it depends if we look at it as a graph than it is one zero, because x counted in a matrix, it goes 01.
The Legendary Avenger: I agree. Yeah. All right. Yep. You're right. So yeah, we have a we have a basis for directionality to so that's fair. Does the question makes sense?
Concomitant Coyote: I think I'm trying to still, so let's try the next one. So, so let's try the B O Y. So if it's that one, then we will say but then so how would the output here would be will it so coordinate start is now 012345. So is it zero comma five?
The Legendary Avenger: Which one? That's the word yob?
Concomitant Coyote: And then the yeah, yob now direction became we're going downward. Just continue
The Legendary Avenger: So that's y changes right.
Concomitant Coyote: So the y gets change. And you know x changes too right? The x changes and y doesn't change right.
The Legendary Avenger: I think it's x is the same y is, y is changing. So I mean, yeah, technically speaking, graphically speaking
Concomitant Coyote: Graphically yeah our x y so our y is going downwards. So if that's the logic, then it becomes zero comma minus one.
The Legendary Avenger: But in this case we, let's think of it graphically. So we will be incrementing the we will be incrementing the Y I guess, right?
Concomitant Coyote: So one, so if y is it a zero then one, two, minus two minus one
The Legendary Avenger: Yeah I don't. I wouldn't, I wouldn't. Don't worry about the magnitude. We can worry about that later. Just worry about the direction. So it should be?
Concomitant Coyote: The answer is only one.
The Legendary Avenger: Yeah, also the other question is you know I wouldn't write it as negative because, you know, technically the coordinates will be increasing. And, you know, I acknowledge that yeah, you're right. You're right. If we were, if you were to think of it graphically, it will obviously be decreasing. But, you know, think of the, okay, let's, let's actually reword this, let's call this the transformation. So that, to the starting coordinate, so think of it as the transformation to the starting coordinate. So whatever you'll be doing on the current co-ord on the current cell, or the current coordinate that you're on, so if you are on this on here, what will you do to keep going? You will increment, right?
Concomitant Coyote: I'll implement then it will be just plus 1.
The Legendary Avenger: Exactly, so think of it as a transformation yeah.
Concomitant Coyote: And then not to just plus one because it goes to two. So do I go plus two, or just plus one, plus one?
The Legendary Avenger: Yeah, just don't worry about the magnitude. So so long as yeah, so long as you just give the starting cell. So in this case, you actually, if we were to say, if we were to output back, because he also have back, it will actually have the same output as this, you know, but maybe the extension could entail, you know, determining the what do you call it, the extension can take an intel determining the magnitude, but for now, only worry about the start and the direction you're going.
Concomitant Coyote: Yeah but I'm just like, so here, we said, the so X is, this zero is x, and this is y. So when we go down, so my x incremented right? Then why would y get incremented? If this is zero comma one, it should be one comma zero then Right? Because my, I'm going zero through first row, and then second row, but my y remains the same. Because the matrix is like 012, and 012345 right?
The Legendary Avenger: Right, so let's think through it again, what's the coordinate of B in this in this grid here?
Concomitant Coyote: The co-ordinate for B. That is zero comma one.
The Legendary Avenger: Right? And then what's the coordinate for A?
Concomitant Coyote: That is, zero comma two? Yeah, that's zero comma three, zero comma fours.
The Legendary Avenger: So which one are we holding constant?
Concomitant Coyote: We holding zero? Yeah. So in y. Then the Y is zero, comma, what? 012345 so zero comma five. And then O is one comma five. And B is two comma five.
The Legendary Avenger: So we'll be incrementing. This on here,
Concomitant Coyote: then it becomes one here thats I was asking.
The Legendary Avenger: That's correct. Yeah. So this one actually indicates moving down, right?
Concomitant Coyote: Yeah.
The Legendary Avenger: Yeah, then you're right. Yeah, that's, that's exactly it. So think of it as the transformation to the to the starting coordinates to find the word.
Concomitant Coyote: Okay, so I, and is there a start, or I can start anywhere,
The Legendary Avenger: You can start anywhere.
Concomitant Coyote: But yeah I mean. So I just have to print, there's no like, move all eight directions about the cell. But once you start moving in a particular direction you may, you have to stick to it.
The Legendary Avenger: So the gist of it is, you know, I don't want to do a word search, you know, like normally the you can go your like y or you go left to decide to go up. But you know, that obviously introduces complexities. So I just want you to think of it simply if you start moving to the right, you keep moving to the right. So if we were to B and we want to find back, we'll keep going. We'll keep going. Once we find the word, we can log it, but we keep going. And backy
Concomitant Coyote: So once we find the y then I change my direction, right? Then I
The Legendary Avenger: At that point if you want to change, if you want to change at that point, so long as let's say, you know, in that case, you still doing the word search, if you want to find the YOB one. You can change directions. Yes, but keep in mind, that's a different word right?
Concomitant Coyote: Okay.
The Legendary Avenger: Yeah. So think of how you will return yob actually do you have the M here. Think how you will return yob while changing direction, you know, despite having gone through the backy one, so that's kind of up to you to figure out what will work well in order to remember that you've seen yob. Does that makes sense?
Concomitant Coyote: I think so. There is no pie. So okay, not all the words are there. Is a set of dictionary, so in the given grid. So start from a and I've just given the list of words a, okay a doesn't belong. Okay I need to see if the first string first.
The Legendary Avenger: Maybe one one hint I can give you try and think how you can leverage the starting characters or you know the position of all starting characters and determine if you want to start doing the search. Right? So think of a brute force approach, if you were to if you were to scan the whole list and it and decide when or scan the whole grid and decide when you want to start searching for a word, because you have a finite set of directions right. So imagine if you if you have to scan the whole grid and then you know, you want to determine okay, do I start searching for all these words? How would you know that?
Concomitant Coyote: Yeah, first I may have to check. What word because a doesn't like a is not the start of any word. So probably from the list of word find out what words can I say likely was the first letter basically, as you point like, we know that it could be a B, or it could be a P, or it could be an E or it could be a Y. So now, so once I find a letter, then I can so I have to choose one direction they're just list of words right. So not this
The Legendary Avenger: One more hint, you can think of, can you think of any data structure that has one directionality and involves storing words.
Concomitant Coyote: So I'm thinking like, trie helps us to store words. So that can tell me, like, you know, for a dictionary, what could be the letters which can come together, like for example, B E D. So you can go to B E d and B, E. And we can put a star like it will tell if there's an end of word or not. So probably we I can store these words in a trie. So this will help me to go character by character. This field yeah, that's two for the list. So once I know the character then one is go in, like you said, don't go in all four directions like if I reach B, I can, so my directions is basically I can go to a or I can go to o but you said I can go diagonally also right? So I can go to diagonally.
The Legendary Avenger: Yeah you can also go diagonally, a is up so here's the thing, if you're let's say on let's see,
Concomitant Coyote: So the goal is to find maximum words or?
The Legendary Avenger: Yes so for any words, so let's say we let's say we had boy here, I can find boy so I can find yob by going Y O B but I can also find boy by going B O Y. So in that case, I will basically do the opposite of Y O B and say here it will be or one of the list or one of the list outputs will be here it's 1,2,3,4,5. Five.
Concomitant Coyote: Then I can go in a direction right? So if I so as soon as I reach b I know that b is the start of my letter. Then I can go in all directions where it goes and then check one by one and mark them as visited like then I go if I start going to first I can, so 8 directions right? Like usually, so if I go on my right side, so I can start with A, and I check in try that if a is there, and then again recursively visually if I start calling and then from a then it goes to C, K, then go recursively. Yeah, so if I, so if I hit a word in the trie, I can return true. If it doesn't match, I can return probably something negative or false. And then, so when I return true, but how will I know that, what word did I go to? When I, before returning, maybe I can store these values in there in the results I need, then I also need to know the direction which I went to keep going, Oh, wait, we also have this thing. So, if I go right, I have to still go keep on going, right? So,
The Legendary Avenger: Exactly and that's to simplify your life because, you know, you can imagine, if you were to go in all directions, then that will
Concomitant Coyote: Yeah yeah yeah so then I don't think we need to go recursively, we know these are the eight options. So once I go straight, I can just keep going straight, and find that if that value is there in my trie. If it's there, then I add the value. So I know that I went in the right direction. And I found something, it goes to the other all of these. And then once I'm done with the word, I mean that the location, then I go to the next one. So I can do this. I mean, I can traverse in all of the values. Does that make sense?
The Legendary Avenger: Yeah one thing I can call out just to make your life a bit easier. You thought right about, you know, knowing which word you saw. So how can you maybe, or maybe, you know, we call it a prefix tree? Can you maybe keep track of the letters you're seeing and build the word. And then as soon as you find an end word, you know, just, you know, you will already have a history of the word you have coming so far. And so when you hit a true, you can just create, you know, create an output format for that value. Does that make sense?
Concomitant Coyote: Yes, so I can keep the word that yeah, I can keep the word I see. I'm just...Yeah, yeah. Yeah, that makes sense. So that then I know that this was the word it went to.
The Legendary Avenger: Because you'll be building the words on the fly as you navigate the trie and you won't need to do any tracking again, to build the word again. It's extra memory, yes, but may save you a lot. But if you want to, like, you know, I'm assuming that if you don't want to do that, if you want to save for memory an alternative is, when you're building your trie, you can keep up or you can keep a reference of the parent. And so in that case, you can always navigate back up and restore your word. Does that make sense?
Concomitant Coyote: Yeah. No, wait. Sorry. Go ahead.
The Legendary Avenger: Yeah, obviously, that that entails having to build a more complex trie structure. Normally people use, you know, a bunch of what you call it, usually use a bunch of lists to just not worry about it. But if you're going to actually make the entries nodes with reference to the exact parent, then you have to worry assuming that let's say there are multiple, the multiple what do you call it, the multiple entries to the parent, let's say like, we have multiple directions for B, so you have to know which exact B you are going towards. That that might be problematic. So just you know, keep them you know, for now, I wouldn't give you any memory restrictions. I think you have a general gist of it. So you just use a trie and then navigate it as you go through the grid. That's the general idea, right?
Concomitant Coyote: Yeah.
The Legendary Avenger: Yeah, so you're gonna try coding that out? Because you kinda you know, you're kind of pressed on time, but I want you to at least take an attempt at that. I know it's a hard problem. So don't worry if we don't solve it. They said it was asked by TikTok and you know, they always push you for the harder ones. But I'm glad that so far you've seen the general direction you should be going with this.
Concomitant Coyote: I'm just wondering. If I have to create a whole trie right? I don't think we have never written a trie, let's see.
The Legendary Avenger: If I have to be honest with you, yeah, the whole idea is to try and see how you build a trie and then customise it suit your needs. So it's actually a trie building problem in disguise.
Concomitant Coyote: Okay so, let's see. So what all do we need in a trie in, we would need. Give me a minute, okay, let me just try to write it on my paper and see.
The Legendary Avenger: Alternatively, if you find this a bit harder to implement, I can give you another quick pointer for an easier approach that I kind of proposed later on, although I didn't have the time to build it. Because, honestly, this is a very customised trie. So try and think about what if you because you know, you already know the length of the word of the words. So if you, if you like, kept track of the starting words, plus the length of the words, as you navigate the grid, if you just did the, you know, what you call it, think of it as a flower. So if you if you find a starting word, just flower out in all directions, and see if any of the words or if the words you're looking for is in the list of words you're generating, so flowering at any given point, up to the maximum direction of the length of the words based off of the starts. Does that make sense?
Concomitant Coyote: So basically, you're saying if I know that back is four and backy is five, so when I am in the c, if I go on my left direction, whatever direction I pick, so I know that the four characters so I pick I go till the fourth character
The Legendary Avenger: in all directions.
Concomitant Coyote: If that is that word, is that the word then the direction and that's the way to go.
The Legendary Avenger: Exactly yeah, that's, that's honestly, that's the approach I told my interview about later on. And they were like, Oh, they did not think about it. Because it's much more efficient. You don't have to save too much.
Concomitant Coyote: Yeah when word comes and breaking of word comes everybody thinks is a trie.
The Legendary Avenger: Exactly like honest, this is a thing I'll you know, I will call it out. My interviewer was from China. And I know, you know, when you're, when you're doing, you know, interviews with Chinese companies, they tend to be very exact about optimal solutions. And so his approach was only a trie. I personally work at Microsoft. So I feel like he respected my stance enough. And so when I told him okay, but this was literally after we've done the interview, and so I feel like it kind of impressed him because I told him how about we just flower out from all starting points, it's more efficient, we don't have to save anything else. We don't have to do you know, multiple what do you call it, multiple scans through the through the array because let's say if I log B and point out back and the size and backy and the size then once that once I'm at b i can do you know the same fan out and cover all bases with B? Right? So just for you know, it's back. If it's five, you know, it's backy. In fact, I can even do extra pre processing in case I have words that kind of compose each other. So if it's back and backy I can literally just try and find backy and I'll know I also have word I also have back.
Concomitant Coyote: But that's what kind of trie also does right?
The Legendary Avenger: Exactly like I can do that kind of pre processing if I want but at the end my final will not involve searching for a trie word like it will it will only involve what you call it, it will only involve doing a length search in this case.
Concomitant Coyote: Makes sense.
The Legendary Avenger: So can you think of a way to find it out how will you find it out if you do it without building a trie?
Concomitant Coyote: Yeah, so that's what you said right? So if I as soon as I reach a we can still know what the letters of a start. And but will it be efficient to, I mean if there's 100 of 100 words, and if we start putting all the letters so we basically have a list which says that these are the start of the letters. And then we have another list which says that that's the maximum length it can go to. So basically we're saying that b can go max is four, five, and three and two, actually, right, so my b will go like the maximum that can take is I have a four letter word, there's a three letter word, there's a two letter word and there is a five letter word and the same goes to I, B and then we have E and then we have Y. We have something like this. So it can tell us how long at least we have to fan out. Y is three. And then so when I reach A, I know that here A doesn't, doesn't belong. So if I go to E then I know that okay, B can fan out so now let's start fanning out from here down side, I mean with the constraints. So
The Legendary Avenger: Yep so in that case you have the direction too
Concomitant Coyote: Yeah, so either direction. So I know that I can fan so if I start from here. So I fan out all these values. So basically, it becomes BACK, BAC, B A, and this BACY and then I can check if they are there. And then I can add them whichever is present. Maybe make it a set kind of a thing.
The Legendary Avenger: I already have the list of words right? So you can certify that and save your life there.
Concomitant Coyote: Yeah, I have this is a list of words, I can make a set of words.
The Legendary Avenger: Infact, let me let me make it simple so that you don't worry about that. Let's make it a set of words. So let's assume it will be.
Concomitant Coyote: Yeah, we can just do it does it contain you should know that this is it okay, this words are there and then so this is one direction then we go to this direction and of course there's a limit. Yeah, we can do that. And then now again so A won't be there C we don't need to take K and then we reach Y which is there and then we can't fan out here no sight no diagnose back we can try so when we go down so we know you already got that three. Should we yeah, I mean there could be o or B also right this way so yeah, we can do all the then we go all the elements one by one right?
The Legendary Avenger: Yeah, yeah, I validated that. Yeah, you can you can go you can go through the grid assume for now that the grid is small enough that you don't have to worry about looping through it. Like that's not an issue. Obviously, as you scale we can always optimise for that but for now, it's at least I can see you already have the data structures and algorithm knowledge. So we can you know, at least practice for the coding part right.
Concomitant Coyote: So now I need to return is a list of what are a coordinate and the word a string and another kind of coordinate, direction coordinates. So if I need to so let's go from class I can make. So we can have probably a tupple right for this. Or pairs which is Integer comma. So my input is...yeah word coming and then ther'll be a set. You need to check the directions before that I need to use the words. Okay so I have a list now and then I'm gonna have a map and then a list. We'll check if word, grid of i comma j if there in a HashMap. I do something else which is. Then now I can make it move left direction, move left. Move left means if I'm at zero I need to go zero comma then the value I'll have there. I need to plus my I, no I have to plus my J. Now I have 4, 3, 5 to go to my direction so I can go length step and j plus the length and index. So if I am a one and my length is four. Okay I minus one. Four so It'd be minus one, then minus one index and check if index is less than length.
The Legendary Avenger: Sorry I might have to interrupt you we have about about 10 minutes and I wanted to at least make sure we go through the feedback and then if you have any questions or anything I can do that so that way like maybe conclude for the next two minutes so 48 my time so we can stop at 50. Is that okay?
Concomitant Coyote: Okay.
The Legendary Avenger: All right sounds good.
Concomitant Coyote: I still have to read one by one probably I should take this words. But what I'm not checking back and backy have any length so it doesn't matter.
The Legendary Avenger: All right. Unfortunately I have to end it here, it's totally fine. All right. Yeah. I know, it was a hard question. So don't beat yourself up about it. And, you know, it's one of those challenge yourself questions. You know, there are a lot of good approaches to approach it. But overall, before I give you my feedback, I think it will also be logged as part of the transcript. But how do you feel like you did?
Concomitant Coyote: Um, I mean, I think the trie solution I came up with is I could I can, I could have started with it. But I think the second approach you gave I liked it most. But if you didn't have given, I probably would have started with the trie and gone from there. I think I asked enough question to understand the problem, because usually I get this seat, I have got this feedback in past that you should ask lots of requirements and make sure that you understand the what all how output should be coming. So I think I did that. But yeah, I think I could have put more effort in thinking and come up with that solution. I mean, yeah, and I think I should speed up my coding, writing skills.