Python Interview with a Microsoft engineer

Watch someone solve the sneak to exit grid with guards and obstacles problem in an interview with a Microsoft engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Sneak to Exit Grid with Guards and Obstacles

Interview question

Write a function: `public isPassable(board: string[]): boolean;` that, given an array `board` consisting of N strings denoting rows of the array, returns `true` if is it possible for the player to sneak from their current location to the bottom - right cell of the board undetected, and`false` otherwise.

Interview Feedback

Feedback about Hot Elephant (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Strengths and what went well: On the problem solving part, I liked that you took the time to parse the task and come up with an example early to validate your thinking. Always use an example even if you know the solution initially, it will help you slow down and spot any edge cases. You broke down problems into phases which showed clarity in your thinking. You chose to do the recursion for DFS and was able to explain how it works in the code very quickly. On the coding part this went above my expectations. You have experience in Python and was able to code the whole task (which is large) in 19min. You even had time to check your solution at the end. I loved that you cared about code structure even under time pressure, this shows actual dedication to the craft of coding. For areas for improvement, nothing major: - During coding, ask interviewer whether to validate the input. It shows real-world project experience - Practice estimation a bit. Perhaps your O(N^3) was a one-time mistake, just make sure that is not a pattern. My tip here would be to run through an example to verify. In your case you would quickly see that the complexity is O(N^2) Good luck with your interviews!

Feedback about Stateless 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

1/4

Interview Transcript

Stateless Donut: Hello.

Hot Elephant: Hi there.

Stateless Donut: Hey, can you hear me?

Hot Elephant: Yes, perfectly. Can you hear me?

Stateless Donut: Yes, I can hear you. Alright, how are you doing?

Hot Elephant: Good, good. How's everything going?

Stateless Donut: Pretty good. So, the app is telling me that you are interviewing for Microsoft as an intermediate engineer.

Hot Elephant: Yeah, that's correct.

Stateless Donut: And do you have an interview coming up soon? Or you're just starting out?

Hot Elephant: Yeah, I do have an on site virtual on site on Wednesday, for Microsoft, and I also have a virtual on site for Yelp on Monday. So I believe this practice will be great for both

Stateless Donut: Have you interviewed with Microsoft before?

Hot Elephant: Yeah, I have.

Stateless Donut: Okay, okay and, and for what level are you targeting?

Hot Elephant: So for this level, currently, I'm going for Level Two software developer, okay.

Stateless Donut: Okay. Cool, okay. Okay. So, since you interviewed with Microsoft, you know, that there are actually four different interviews and for today, like we are assessing basically problem solving and coding, which is part of the excellence interview on others, you will you will be asked a system design and another thing. And also with I don't know if you're aware, but for every interview, there is this kind of tech part either tech excellence or system design or tech expertise as I said, but also there is a part of the behavioural question every interviewer says different things. So, but most of the weight is on the technical side and the other the other things are mostly you know, if you have some if you have some red flags or things like that, but so, okay for this interview today, I have a have a problem, I will paste it in in in the site here, we will discuss solving the problem initially and then we will move to coding Okay, so I pasted it can you see it?

Hot Elephant: Yeah, got it yeah. So, we're given to begin a two dimensional board of n by m, n rows by m columns. Each field can either be a dot, which is empty and obstacle just a I mean x and player one a guard so, I guess play a one a that's the start position and then guard one of four types looking at the left looking at the right up now, the guards can see everything in a straight line in the direction in which they are facing as far as the first obstacle X or any other guard or the edge of the board as far as the first obstacle or the edge of the board Okay, I see. Player can move from the current field to any other empty field with a shared edge but cannot move on to fields containing obstacles or guards. Okay, so you want to write a function is passable that given an array board consisting of N strings denoting rows returns true if it's possible for the player to sneak from the current location to the bottom right cell of the board undetected and false otherwise, okay. So while some rights so that's the last index of the grid all right. Okay so, so it's a it's a 2d array and usually to traverse through that, it tends to be sort of a, it tends to be brute force, but I guess we don't need to visit every cell, we just need to start from where the player is. And wait, so I noticed that we're just given the board. So we need to search for the player A and then once you find the player, then we can find the exit. Is that, is that a right assumption?

Stateless Donut: That's correct, you don't know where the player is until you find find it in the board.

Hot Elephant: Okay, I see. So in so you do need to do a brute force approach for that just to find the player itself. And I guess once you find that player we could do I guess a depth first search with some constraints, where the constraints would be where the guards are looking, as well as the obstacle. So you cannot go into the path of it can't go into the line of sight of where the guard is looking. You also cannot go through an obstacle, but you could go around it right so let's see what else am I thinking. So yeah, there's there's no other like way to do this quite efficiently. Because, so, to find the So, for example, to find the player itself that can be on N squared, because he needs to visit every index right? So I'll just type that

Stateless Donut: When you say efficiently just want to check if like there are no obstacles or whatever what is the actually you need to have the obstacles like but if you know if you knew where the player was what will be the complexity of finding the upper sorry bottom right corner

Hot Elephant: Of the bottom right corner

Stateless Donut: Finding the path path from player to the bottom right corner you mentioned depth first search right

Hot Elephant: because there is a possibility depending on where the guards are, that could make things quite complex, like the player it could cause a player to maybe traverse through almost every index until it finds the exits. So that in itself could be even n squared

Stateless Donut: And if there were no guards?

Hot Elephant: If there are no guards at all, In this case, if there were no guards, so so no guards are no obstacles aswell?

Stateless Donut: You have obstacles you have obstacles but you don't

Hot Elephant: You have obstacles but no guards? I mean, worst case it can be like at worst case, it could be O of N squared as well.

Stateless Donut: Yep, that's right okay. Okay, so how do we how do we proceed forward? You said depth first search but how do we deal with the guards?

Hot Elephant: Yeah, so how do we deal with it guards is. Okay, so let me just type out a grid for example just to make this easy. Player starts, you have a guard over here looking okay and then. And also just to ask, it's just to ask about the guards. So, it can have up to four guards right. Is it wrong to

Stateless Donut: No no, arbitrary many guards with arbitrary types

Hot Elephant: Oh I see so we can have multiple, like at least something like this right?

Stateless Donut: Yes.

Hot Elephant: Okay I see okay, so we start here so okay, we found we found a so I guess the algorithm how are we going to traverse let's say, right, left, down up, right, so first of all is going to go to the right and then it's going to realise that this is the third set needs to go back here to the left, it's out of bounds there's quite a couple of base cases where you want it to stop recursing so and it's going to go down but it needs to figure out that this is a safe path right so. There's a possibility so I believe we can maybe traverse through the entire thing to see which indices are true traversable.

Stateless Donut: Okay, how do we do that?

Hot Elephant: Okay, so So for example, we go here. So let's say we traverse to each index, so we find this arrow here. Or we know that okay, if this is pointing in this direction, then we want to traverse linearly in the direction it's pointing to. So it's going to go like this, this index indices right. So you'll add it until you meet a guard or it is a boundary and one more question is if we have something like for example, if we have something like. Let's add up. So does it stop when it meets this arrow here? That gives this index traversable?

Stateless Donut: So the text says the guard can see everything in a straight line in the direction in which they are facing as far as the first obstacle where obstacle is, or any other guard.

Hot Elephant: Okay, got it. Okay, good. So Okay. So it would just add everything until it meets a guard a boundary or a guard boundary or another or x, right. And then we add that to maybe we can add that to a set. So a hash set, holds all non traversable indices. Okay, so then

Stateless Donut: Set to hold all non-traversable indices?

Hot Elephant: So it'll be the set will be would look something like we'd have tuples. So, for example, this is 0001 so it'll have this and then 01 and so on. And then we go to this one here, and then we add this into C and we keep going. We ignore a and then. So yeah, so we just that's the algorithm, we're just going to keep adding. And depending on which direction we find, we're going to traverse in that direction until it stops there.

Stateless Donut: Okay what's the complexity of doing that?

Hot Elephant: So the complexity? So it needs to be O of n squared, because you're going to need to find every single arrow and then and then traversing linearly, that'll be O of n. So we'll have n cubed pretty much right? So let's so we have different phases of this. So we have let's say phase one. This one is to find non traversable indices and within that phase, we can just find the guard at the starting point. The starting point is to is to find the. End, the space will be O of n squared at worst case. It's find the exit. This might be, if we go recursively. Um so so, am I making this just make sense to you?

Stateless Donut: This makes sense. Before moving to coding, additional thing that we didn't discuss is how are we performing the depth first search? Describe the algorithm.

Hot Elephant: Yeah, for sure. So, and this is for the first phase. So the first depth first search we're going to

Stateless Donut: sorry, isn't that for the second phase?

Hot Elephant: Oh, yeah. That's right. Yeah, the second phase differences. So with that we're going to do recursively. That's number one. Number two. We should start looking at the base cases as to why all right. So

Stateless Donut: Why recursively?

Hot Elephant: Why recursively? Oh It can be done either recursively or iteratively but recursively, It's I guess it's a much simpler Implementation. Usually. Yeah.

Stateless Donut: What's the drawback? What would be the drawback?

Hot Elephant: Yeah, the draw. Yeah, the drawback for that would be the space because once you as you do each function call it gets pushed onto the call stack. And since we have, it's a grid, it can be at worse, of of n squared, where visits like each indice. So for a very, very large, very large grid, it would not be performant. Whereas the iterative it would be better on the space.

Stateless Donut: Okay. Apart from not being performant, it's for very, or very large grids. It might not even be possible, because some languages just give you a cap on number of calls. Yes.

Hot Elephant: Yeah. Like a stack Overflow prevent.

Stateless Donut: Yes.

Hot Elephant: Yeah. So it's, that'll be an issue. So I believe it depends on the system and what the constraints would be. To go with either recursion or iterative for example. And yeah.

Stateless Donut: Okay. Anything else on the on on here before we move to coding?

Hot Elephant: Well, I guess for the DFS, I'll just like to define like the base cases and all that. But other than that, they're nothing much.

Stateless Donut: What do you mean, sorry, base cases. And haven't you? Haven't you define the complexity already?

Hot Elephant: Yeah, no, I mean, the the base case of the recursive function the so like,

Stateless Donut: Ah okay, base case okay. I thought you said best case.

Hot Elephant: Oh haha no. Yeah. So, yeah, so for example, these case, recursion is if and I just realised that we can actually also add these indices within set as well. And also the x. So because we're finding all non traversable. So So you just say if row column in on traverse, let's call that the set for now. If not in there then we re-, is in that set then we return false example. Also, if it's out of bounds, so if or r is less than zero or c is less than zero or r is greater than E length of the grid size. So board length word, greater than equal to or c greater than or equal to itself board and we return we don't want to recurse in that direction any longer. Else recursive case. You want to build up down left right so let's do right so the indices so r,c with this, c plus one. Right and then, then also one key thing is that we don't want to traverse in the same direction that we were in so we may need we may need to have a another, could either do in another set or we can use the same sets actually. The non traverse sets, okay just just for simplicity I'll just use another sets and then I could look at maybe merging them later. Does that make sense to you?

Stateless Donut: That makes sense.

Hot Elephant: Yeah, okay. So we have another set called visited we add r, c we say or r,c in visited. Visited at r,c result is equal to

Stateless Donut: When do you return true?

Hot Elephant: Ah yeah so that's what I do you have to return true because that is the final base case yeah. So if it's this here so if r, c and the c is let's say for now roll blanks. And then within the function itself, once we find that true, then that'll be the end of the programme and then else return false. So does this make sense the depth first search?

Stateless Donut: Yes, apart from one thing that stands out what is the visited set scope? Like is that something that you did as empty and then pass the function or?

Hot Elephant: Oh, yeah, so, so how I plan to do the scope is that I will be putting in this function within the main function. so that the visited would be accessible. The non traverse will be accessible as well.

Stateless Donut: Okay okay. Reason why I'm asking is that I assume that's the case. How would backtracking work? Like if one path does not give you a result? You need to go back and unvisit?

Hot Elephant: Yeah. So yeah I'm glad you said that so so that's what I was thinking about if that needed to be done so we can remove right here then so then we can backtrack and then see if we have the results. Yeah. Yeah, and yeah, just also I code in python as well so that's preference.

Stateless Donut: Sorry what was that?

Hot Elephant: Oh I was saying that I code in Python as well.

Stateless Donut: Oh oh well yeah whatever language you're more proficient at and so let's move to coding we have another 20 minutes till the end.

Hot Elephant: Okay, got it. Sweet. So let's do this. So, we have no need for this is passable and we have a board full board. Okay so is passable board so lets do phase one so let's define the sets non traverse. Empty sets and then we have another one called visited and then wanna define a row length, row length is length board, column length is the board of the first array. Every thing, if equals to any of these, the for our row in range of row for column in range. If board row do something if it equals any of these it does the previous thing I'm just going to fill that in after if it equals to the A then we found the starting position. So lets see start is equal to c for now so let's use this zero is gonna start one is equal to row column if we found x then let's say this just say, so to move linearly it could perhaps do

Stateless Donut: Maybe you can just write the case for one and then we can skip the other three and then finish the rest.

Hot Elephant: Okay got it I was thinking of just maybe doing a pass say get path for example get have row and column. Path goes, it's going up. So if its left move in the direction of left Okay, so to move left you have to decrement the column so then the row stays constant so we do for we do while c is greater than zero or not board, r, c, yeah, from this board RC is equal to dot. And we say controverse add r, c. C minus one. So, so does that make sense for the left case?

Stateless Donut: Yep that makes sense.

Hot Elephant: Yeah, so it will keep going so, as long as it's greater than or equal to zero then yeah, then it'll be different for everything else.

Stateless Donut: And you would have that function get paths which is actually called get like left paths and you'll have the three different for the up right and down right.

Hot Elephant: Yeah, and exactly yeah. And how I would do this function is that like I wouldn't have to write four different while loops I'll just have like certain variables to handle each case. Like there'll be maybe a third argument for each direction for example and it would do something depending on the direction so we're going to do df, sorry get path. So at that point we should have all of the non traversable and then move on to phase two which is finding the exits. So, we have the start, which we updated down here. So, let's call it recursive function find exit the more appropriate name so find this copied down here incorrectly so, this function is defined. I think just to separate this out better I would like to. Function, functions here and then here with actual computation this should be tabbed, based to recall I mean we could just do return findexits start 0, start 1. And this should evaluate to true or false given right.

Stateless Donut: Okay, yep

Hot Elephant: Alright and depending on how much time do you have like three minutes?

Stateless Donut: Yeah, just let's just wrap up the find exits. I think your, oh is the find exit done? Okay.

Hot Elephant: Yeah, I just copied and paste from what I did up here and yeah.

Stateless Donut: Just read through it,

Hot Elephant: Then okay. Row Column R C Isn't this or it's out of bounds or it isn't visited return false. If this equals to c and Yeah. To the exit the exit that's true. And then else it just add this and then we traverse right. Sorry, yeah, right, up, left, right, down, left up and then we remove that. Backtracking the return results and then so phase one iterates through each and every thing. If we hit with this character, or right up or down, as what to call this function, row column with with this character, like a simple way is just to collapse all of this into one big if we just do an R and then we input the character. This character heres that not equals input left and then yeah, and then depending on that the direction this function should be able to know if the increment all the way up or decrement all the way down and then

Stateless Donut: I think we're at time, but this is pretty good on the as I said only one, one of the four cases we should cover and it looks good. Okay? I can give you feedback now. Okay. In short, I would advanced you to the I will give you a hire. And just to give you now the more verbose feedback of looking at my notes. So initially you read the task patiently what worried me that you were assuming that N squared is a brute force. But I'm glad that you didn't go into rabbit hole of trying to find something that's not possible to do. What is good is that you use an example early to verify your thinking and to try to spot any issues. When we talked about how the guards can see us, you were able to find quickly the solution. Set a hash set is good. It works, there are alternatives but I don't expect that as you know, a bar for hire any any solution is okay, for example, just sharing an idea, you could have modified the original matrix like you added access to the not cannot visited set you could actually just add x's in the matrix itself, which would allow you to use less memory, but that's okay. Finding those non traversable indices is actually not n cubed. I did not want to go into that rabbit hole you because I wanted to give you enough time for coding precisely because that that was not critical. For the for the decision, it could play a role if coding went really bad. But But I wanted to give you more time for coding and I'm glad I did. I love that you broke the problem into phases. It gives good clarity and understanding from your side and helped me visualise the solution as well as visualise how you're taking on the recursive versus iterative discussion that we had, I would have expected that you bring the pros and cons. Without me hinting especially in some, you know, medium to senior positions, but it's okay, you were able to explain pretty well. The pros and cons. I liked how you wrote the recursion into base and recursive case, it seems like you have experienced with writing a recursive code, which shows a lot of people have the recursion in their head. But when it's time to write it on paper, things get messy. But that's not the case with you. You I had to give you one hint about not visiting already visited nodes, but you quickly I think you had it in the back of your head or something like that. Remember, you must remember anyways, so that didn't worry me. So overall problem solving went well. Coding went amazing I mean better than problem solving. Just to like I would give you a hire for problem solving. But coding is above the bar what I expect like you were able to code this thing in 19 minutes, you have experience in Python. And it shows this went really smoothly. One tip for you during the interview, ask your interviewer whether you should validate the input arguments or not because like the for if this was a public function, you will probably validate the input arguments and usually the discussion is assumed that everything is correct. But you should ask the question Is it shows that you're thinking about about everything. And I liked that you I liked that you also thought about the code structure even if we didn't have a lot of times so you actually went in and broke it down to function declarations and phases. So that was that that really amazed me that you actually thinking about that as well, in addition to solving the problem, so yeah, that's in summary, as I said, I would advanced you. Coding I think is going very well. If you want to practice more practice more problem solving and come up with a solution, and then don't code it because you already have it. Very good. So so maybe I would focus more on problem solving, if you just want to be more sure about covering as many questions as possible.

Hot Elephant: Okay. Oh, yeah. Thank you. Thank you very much. And it's actually a great session. And

Stateless Donut: Do you have any have any other questions about the interview or my take on it?

Hot Elephant: Let me think, um lets see, I know you're quite informative. And everything like is very great. Well, detailed feedback. So yeah.

Stateless Donut: Okay, this is actually my second interview on the platform. So if you have any feedback for me how to improve just you know, leave it leave it after the session, because it's actually my first day using this platform. So anything that can be different.

Hot Elephant: Okay, got it. Definitely will.

Stateless Donut: Okay. I wish you all the luck in your interviews next week. I I'm very pretty confident that you will that you will get the job.

Hot Elephant: Thank you so much. Yeah, for the confidence I needed.

Stateless Donut: All right.

Hot Elephant: Yeah. All right thank you. You have a good rest of the day.

Stateless Donut: Yeah, you too. Bye.

Hot Elephant: Bye.