Ruby Interview with an Amazon engineer

Watch someone solve the minimum tree depth problem in an interview with an Amazon engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Minimum tree depth

Interview question

Given an unbalanced BST, determine the minimum depth of all of its leaves.

Interview Feedback

Feedback about Wily Sandwich (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

4/4

Good job solving the problem today, and a good discussion of the approaches (dfs vs bfs), and proceeded with implementing the optimal solution. With that, I rate this interview as a pass. For reference, here is the question we discussed today: https://leetcode.com/problems/minimum-depth-of-binary-tree/ We discussed the feedback at the end of the interview, and below is a brief summary: - good job brainstorming various approaches and explaining the reasoning for BFS to be the better approach - great job explaining your thought process as you code, which allows the interviewer to follow your thought process throughout - good job implementing the algorithm within the allotted time - coding speed can be a bit quicker so that you have time to run some tests and provide complexity analysis

Feedback about Hot Gyro (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

3/4

How helpful was your interviewer in guiding you to the solution(s)?

3/4

I think that there were moments where I was struggling where they felt like I could get to the answer, which was good. I'm glad I had recently revisited BFS and that that was helpful in me coming to a solution in this case.

Interview Transcript

Hot Gyro: Hello.

Wily Sandwich: Hi there.

Hot Gyro: Hi. Can you hear me?

Wily Sandwich: Yeah. Can you hear me?

Hot Gyro: Okay, great. Well, let's get started. We have an hour for our coding interview, is that correct?

Wily Sandwich: Yeah, I think so.

Hot Gyro: So I've got a couple of questions prepared. So let's get started. When you finish, we can just keep going. So let's start with the first question. Can you pick the language that you will be using for this problem?

Wily Sandwich: Sure. That would be Ruby here.

Hot Gyro: Okay. I don't know how to do block comments for Ruby. I don't know if it's like this.

Wily Sandwich: It's an octothorp, it's a hash.

Hot Gyro: Oh, yeah.

Wily Sandwich: And then I think because CoderPad, you can just highlight all of that. And then do command pound. Yep. Yep. There you go.

Hot Gyro: There you go. Yep. So here's the first question.

Wily Sandwich: So if we want the first thing that, you know, because it is a tree, the first thing that I'll just for my thought process is, let's just instantiate class. And then, it'll be nil. This will be also be nil. Okay. So, to start, this looks like a typical depth first search problem. So in order to do that, I mean, we could do... I think that we're just, you know, if you're, you're gonna want to just do a find depth... You're gonna want to do a find depth method.

Hot Gyro: Okay.

Wily Sandwich: And then that's just going to take the, whatever the root is. But let me draw this out real quick. So I have my root node. And that's three, so three is root. And then I am going to look down... can you see me highlighting?

Hot Gyro: Yep, yep.

Wily Sandwich: Okay, great. So if I see three, and then I go down to nine, I want to keep track of each of these paths, I think. So if it's a three and a nine, then I would have an array and that, you know, the length is going to be two, but I don't, I don't really care about what these values are. So I just need to, you know, the sum length is going to be two. And then here it'll be three, and then 20, and then 15. And that's sum root is three, and that I don't need to care about that anymore, because I only care about the minimal sum length. And then if I check 3, 20, and 7, that's also going to be the same thing. So if I'm trying to find the depth, the first thing that I want to do is... well, I could just check right now if my root value... If my root value is equal to, yeah, if my root is... I'm trying to think of how to do this, if I need to actually know about my root value being nil. I mean, if that's nil, then that's obviously... not that it's, but if my root.right equals nil, and my root.left equals nil, that's going to return false, maybe? Let me just not think about that base case right now. Okay. There's a recursive solution that I can do here, I know that. And I know that's going to be like trying to just try to figure out what the sum length is. So if I have three as the root and then nine. And then I just need to figure out if there is a root.left value. So basically, I start with my length is zero. And then I want to do find depth. And then I want to do something like root... passing root.right. And that I think I need to do it's not even sum, it's length is going to be... I'm going to pass in the length, I know that, and then I also need to, I think it's also find depth, root.left, and then the length there as well. Start with default, then I think I want to just do a length plus equal one. But I need, if I'm trying to find my minimum root, I need to also pass in some kind of list value, right?

Hot Gyro: What does that mean by minimum root?

Wily Sandwich: Minimal sum, sorry?

Hot Gyro: Minimum depth.

Wily Sandwich: Okay. Yeah, what does it mean by the minimum depth, it just means that when I'm traversing through my tree, it's going to be whatever is the lowest amount that the lowest length value.

Hot Gyro: Right, the shortest path to the leaf. That's what we're talking about.

Wily Sandwich: Right. Okay, so if I'm just trying to find the shortest path... Well, maybe find depth... we could... That's the shortest path. Yeah. So the shortest path, do I... Yeah, so if it's the shortest path, it is technically a sum right? So maybe? Okay... Yeah. So I don't want, the sum is always going to be I think it's going to be sum equals sum minus... it's not going to be the length. I'm gonna have this root, root.right is going to be... am I, I don't even know if I need to pass in the root.right value, I need to do root.right minus the value minus the sum. I don't even know if I need to necessarily look at that I just need to see that the root.value is equal to nil. And I can return... but I'm not, right now and not looking at like specific values. Aside from... I'm not checking what the sum value is yet. But I think the sum in depth first search is always going to be sum equals, let me... Yeah, so three and nine, that's gonna be one, and then that's gonna be three. And then if I'm doing a depth first search, I need to go recursively, back up my call stack, right? So when I go down one, and then I go down to two, and then I just go up, go back up. So it's really just looking at, I don't really need to check. Here's my big question for you... if I have this current method here, do I need a secondary method as well? Because I'm thinking that the depth first search, I don't need to do, you know, I don't need additional recursive function. Now I do think I need that with breadth first search.

Hot Gyro: Right. I think there's multiple questions here. The first one is whether you needed another helper function for that recursive call. And the answer is, you don't need it. But it all depends on your implementation. So you could get away with solving this problem in just one function, that recursively call itself fused up, like what you're doing in line 36. Just update that function name there. That's one, that's the first answer. The second part of the question is about, you know, DFS versus BFS here. And I'd like you to think about the difference a little bit more in this case, because there is a clear winner between the two.

Wily Sandwich: Right. I think it's like, obviously, depth first search, right? I mean, I think that's obviously what we're talking about. We're trying to say we're finding the minimum depth, and because, you know, we're not talking about a huge binary tree, where it's values all the way out. You know, what we're not talking about another one that keeps going ad nauseum, right? So there's not a reason to do breadth first search there.

Hot Gyro: Okay, so let me point out an example. I'm gonna comment that later on. What I'm talking about here is let's say we have a tree similar to what you're describing, but let's say the... here refers to maybe many levels that I'm not gonna, I'm just gonna skip over here. And this would be a number. And then here, I just have a number that at the end of the matter, so think of this ... being, you know, 10s of 1000s of layers there, right? Now, this is a highly, highly imbalanced tree, right? The left side is heavily, you know, very long, the right sides only one. What is the answer to this tree? What is the minimum depth to this tree?

Wily Sandwich: Well, it's two.

Hot Gyro: Right. That's right. So the depth here is two. Now, the question is when you use DFS versus BFS, which one is more optimal? Optimal in the sense that you are able to get the answer quicker, right? So time complexity is better, on average, for this particular example. And so, you, so it looks like you're saying that DFS, is that, right? Is that right?

Wily Sandwich: Well, in the case where you have like a, something with a, like a highly imbalanced tree like that, yeah, I would say breadth first search is better.

Hot Gyro: Okay. So, just I hear you just say, BFS is better. Which was better.

Wily Sandwich: Depth first search is typically better when there is lots of... when your your tree is like huge horizontally, right?

Hot Gyro: Okay, look, this is not one of those trees, right? Okay, so you're at this question I want to do, which one is better? For this example, for the example here, the one that I just drew out? Which one is better? Which approach is the better approach?

Wily Sandwich: I think it's probably breadth first search, right? Because you're, if you're able to look at both of them at the same time, and then you, you end if you're looking at three and nine, and then three and 20. And then you try to go to the next one, and there's nothing and three and 20. And then it's 15. And then you just keep on going down, then you've already stopped here. So you don't need to go any further.

Hot Gyro: That's correct. Yes. So you're looking at the first example, and I agree with you. In the second example, it's even more obvious that for a highly skewed tree like this, BFS, breadth first search, with a B like boy, is much better, because it is able to terminate the algorithm much earlier as soon as it identifies the level or the depth that does not have any children. In other words, as soon as it's able to find a leaf, it just stopped the algorithm and says, this is the shortest path. And this is the depth and this is the answer. Right. So, so yeah. So now that we kind of clear up, you know, which, for this problem, the approach which we identify the approach that's better suited, I think, and get started to kind of code that up.

Wily Sandwich: Yeah, so the best thing with breadth first search is now, I don't know if out of the box, let me see something real quick, because we're in a... Yes. Okay. So let me just see if I can do, we're gonna want a queue class here. Okay. So, you know, in all honesty, that's probably overkill for what we're trying to do. So let me just quickly create a new queue class, which would be an empty array, and then we'll have two methods and that'll pass in an item. And that will just do shift. Well, sorry, sorry, push. So in terms of that what I want to check is if my root dot value is equal to nil. I don't even know if I need to do a return 0. And then because of that, you know, I'm probably not going to want to do a recursive solution for this. I think it'll be easier just to do it with a queue. So what I would do then is this here, let's do that. And while... what I'll do is... Okay, now this is the more difficult part here with breadth first search. So by pushing in the root and I'm checking the value each time I want to go through and find sum. Now here, I can do... And then I need to check what the current level is. Getting a little bit confused here.... Current level is going to be whatever because I kind of want to... I think I need to also do a loop within this while loop. Yeah, so current loop is here. So and then the while loop. I can just do it pretty much do a for loop. But how do I do a for loop in Ruby. To, to be perfectly honest, I saw a problem like this recently, either today or yesterday. So I'm refreshing my mind about it, but I did it in JavaScript, so I'm trying to think about it like, how I would do it in Ruby. And in Ruby, the easiest way to do it, honestly, is to take when you're doing loops, you know, you typically want to do each loops, but doing it in... I just kind of really want... I honestly just need to do queue dot length... Yeah. Yeah. But I also want to do, I want to find whatever the current first node is. And trying to find what the current node is, that's going to be, I know I'm missing some key things here. Because I want to take track of the current level, the current level, I think it is going to be an array. So I want to just push into this value. The current node is going to be... current node, you know, queue dot length, I need the length right. And the current level is just going to be... Oh, the current node is going to be whatever the... I want to see... I need to keep whatever the level... I mean, whatever the level size has always be whatever the queue one is, right? So maybe I just need to do something like... We really don't care about the values here, right?

Hot Gyro: Yeah, you're right.

Wily Sandwich: I'm missing something important. So I can't just, because I'm not going to return my... Well, let's see, what is this... Okay. I don't want to return the queue. And I don't want to return the queue dot value. But what I do want to do I think I need another array here, right? Let's see what happens here. Nothing happens there because it's going to need like a result array. That's going to be what? Result dot length maybe? I need to push into this array. So maybe it's out. I'm not doing anything with that current level.

Hot Gyro: I think you have a lot of good pieces of this problem here. The level is good.

Wily Sandwich: Current level that? Yeah. Okay. Okay, gotcha. So, oh, no, if I'm... And then if I push that and then I...

Hot Gyro: Are you trying to run the code? You need to set up a tree and then call it.

Wily Sandwich: Well, that's also part of the problem. Right. So thank you for pointing that out. And then so with that we need to do a puts. Puts shortest path. Undefined method... Oh, thank you. Appreciate that. Interesting. Oh, because... well, current node dot value is undefined method value for... Oh, interesting, because... something like that. Undefined method value, nil class. Queue dot value and up to level, maybe it's just... No, because I don't know because that doesn't matter. Maybe that's... So that's giving me the longest length.

Hot Gyro: That's right.

Wily Sandwich: What am I doing to give me the longest length. If I'm pushing that... Let's just walk through it real quick. So if I'm three, the root value is not now. The root value is three. The length is gonna be one and then... So zero up to the level size minus... Well, that will just be... Yeah, I do want to continue the index up here. So three and two, okay. So if I dequeue the current node value, which is going to be three. And then I push that value into the current level. So that's only going to have one value there. And then I go to the current node to the left, which is going to be nine. And I enqueue that. And then I also enqueue the 20. And then I go to the next one. So because the queue value has increased too... Yeah. And then I go to my next value, I push in the current value, which is going to be... the last one is going to be 20. So the result length, let me just actually... Gotcha. So that's not giving me the shortest path. And I mean, it's giving me each each of the level lengths, right? So I don't really care about what the length is telling me how many levels I have. But really all I need to know... That's gonna give me each... So I'm missing something here. I'm just when I'm giving. I'm just getting how many levels are there? And what this isn't telling me is how many? Well, I have 15, 7, 9 and 20. So basically, all I have to do is see whatever is the... I kind of want to say it's got to be whatever the modulus is right? Because it's binary.

Hot Gyro: Modulus of what?

Wily Sandwich: The well, so the... Perhaps this is such a small example that that would be a difficult thing to do. If I have one. And then I have 9 and 20. And I have 15 and 7.

Hot Gyro: I think I understand what you're trying to get out. I think you're looking at the total number of nodes and then use that number as a function of the depth. Is that right?

Wily Sandwich: Correct. Yes.

Hot Gyro: But I think the assumption there is the tree has to be perfectly complete for you to have some sort of formula that can...

Wily Sandwich: Yeah, would have to be completely balanced. Right?

Hot Gyro: Right. Yeah, completely balanced. So we're not going to guarantee to have a balanced tree. But here is another way to look at this, the size of your results is three elements, or three arrays here, right within the queue. And the three arrays belong to three loops that you're doing within your while loop, that you have three, kind of, for each loops. So if you can track the number of times you are going through the for loop, then you know that that's also the number of the maximum depth. Now this problem is not looking for the maximum depth, it's looking for the minimum depth. So somewhere along inside that for loop, somewhere there, if you can terminate early and say, "Hey, I have reached my shortest step, I can exit the program." I think that might be one way of solving this problem.

Wily Sandwich: Okay, I think if I just do... Right, because if I don't have... if it is nil on either side. Well, I don't want to break, necessarily, but I do want to check... Yeah, so in this? If... right. So basically, I just need to say, hey, break if... Well, that's not where I want to break. But I don't know if I yeah, in this loop. So I don't want to do it there. Because I want... I know that this is the logic that I need. It's just like, is this, like, that's not going to be helpful for me in terms of getting the results I want. So it's not even... Maybe it's just an...

Hot Gyro: Yeah. So I think there's definitely value in checking whether you're at a leaf or not. And line 75 is really for you to check am I the leaf or not? What happens when you are at a leaf? Like, we look at this tree here. Let's say we visit nine. Like we know that, Hey, nine is a leaf. What should we do at this point?

Wily Sandwich: If nine is a leaf, so are you saying if it has a parent value?

Hot Gyro: No, on line 75 you're checking whether it's a leaf or not by you checking that child by child. So let's say at nine, we're doing this BFS, we're at 9 we see that 9 is a leaf, right and line 75 evaluates to true. What do you want to do after that line? Because if you don't check for that, what you'll be doing is you're going to check for 20 and then you check for 15 then check for 7. And then after all that's done, then you output 3 which is the depth of the entire tree, right? But you need to be decision here, when you're at 9, you're halfway through the tree, you're at 9, you're at a leaf right now. And you know that this is going to be the shortest path at nine, like, looking at the tree here. So what do you want to do when you're at nine?

Wily Sandwich: I think that's sort of the last thing you need to worry about this here. Yeah, I mean, I just want to return the results. But I don't know if I have... I guess I could just...

Hot Gyro: Okay. Okay.

Wily Sandwich: I don't know. I don't know if that's... That's obviously not it. Or it's actually yeah.

Hot Gyro: Yeah. Yeah. So your result variable is holding all the values of the nodes of every node, right. And quoting the values of the nodes at each level. And so that's, that's one way of representing the depth. Another would be just a number. The the root is at depth one, right? And then every time you go through the for loop, that's one depth, right? So now you can use something else to represent the depth and then just return that.

Wily Sandwich: Instead of the actual current node value? While result I just needed to be a number, right? So all I need to do is... that's not necessarily the result. So it's three and then it's two, but I need to do something here. That's not, I do want to return something. And I'm just trying to think of it's just, you know, breaking out of the loop, which is something that I would want to do, but I don't want to push the current level if I'm out of the loop. If current node is left is nil and current node is right is nil. I don't think... Do I need to push current node at that point? I could probably... no, because I need to queue this. And I need to figure out what the current level is. Right. Return if current node. See what is confusing me is like only three is in there because I haven't cured... But that doesn't make any sense because current nodes should be nine. So return result dot... And then it's just something like that. Well, right, it wouldn't be bad, but it's gonna be. But I understand that it's going to be whatever and then it's just current node dot value and then that should be two. Yeah.

Hot Gyro: Okay. Okay, looks like we we have something that works.

Wily Sandwich: It's not, obviously, that's not what I would want to push into that result of that array, but I want the length of the array and I want to increase the length of their array by one.

Hot Gyro: Okay. I will just do one test to confirm if this is right, I'm going to add another node to the left of the left. And this should give us three, right?

Wily Sandwich: That's the hope. We'll see.

Hot Gyro: Yeah, yeah. Let's see, if I do get three here. Yeah, we do. So that's good. I think it's gonna work. I will have to look at it a little bit more deeper. But let me give you some feedback first, and then we can do a quick update. I think you did a great job in the beginning, when we discussed the trade offs between DFS and BFS, and you were able to explain the benefit of both of both of them. And we ended up choosing the right algorithm for this particular problem. It is indeed true that BFS is a better algorithm, even though the runtime would be the same in terms of order n. But we are able to terminate early if the tree is skewed. So you did a great job explaining all that. And then you proceeded to implement the correct algorithm, which is a queue based BFS approach. I saw that as you are going through the implementation, you're able to identify the right data structures using a queue, using a variable to keep track of the level variable or a list of that while loop and all that is the right pieces to implement the BFS here. You did all that correctly. And you're able to come up with a solution that, at first glance, it seems to be correct, right? The only thing there, you're able to identify in line 75 or 77, that was great to me to be able to return as soon as you identify a leaf node, and return the level, I think there was a bit of a struggle in figuring out what the level number is, as you're traversing. But that's okay, you're able to solve that on your own. That's great. So, obviously, we didn't have enough time to do additional testing. I did one test case here. But you would actually do some more, we didn't have time to go through that. And we also didn't have time to talk about the complexity. But that's something that you would need to make sure you manage time well enough to be able to go through all that within the allocated time for that question, right. So in terms of time management, I think there's something you can improve a little bit on just getting the answer a little bit quicker, so that you can include the testing and the complexity analysis. But other than that, the problem solving part is great. The coding is done well as well, except, again, just the timing, maybe a little bit quicker in figuring out some of the little things to save yourself, like five minutes or so that would be sufficient to go through the rest of the requirements of this problem. And I think maybe the language itself can sometimes hinder your progress a little bit because of maybe the syntax. So something to worry about as well that if you are interviewing for a company that requires you to run the code, definitely pick a language that is easier for you to do that. JavaScript might be easier, even for printing out debugging messages, you can hustle off versus sometimes data structure will be easier as well. Depending on the problem as well, I think JavaScript may not have a stack or something. So you need to pick the right language for that. I think Ruby in general is a little hard because you have to come up with all these queues yourself. The data structure is available for you, you know, in Java or some other languages, and it will make your life much easier. Yeah, but other than that, you're able to solve the problem within an hour. I think that would qualify as a pass to me. But just watch out for the timing. You want to check in with the interviewer sometime how much time you're given for this problem, and then make sure that you use all the time to explain every aspect of the problem like the testing and complexity analysis.

Wily Sandwich: Gotcha. How important is space complexity, like I have a pretty good understanding of like the time complexity of this and I think that time complexity would probably be O(n) I think.

Hot Gyro: Yeah, you're right. Right and wrong in the sense that O(n) is correct. You need to also provide a reason why is it O(n) like you want to claim that at the worst case, the big O notation always talks about the worst case, you want to say that worst case scenario you are visiting every node, right? And that would be the worst case scenario, which could be a linked list. The tree could be very skewed to be a linked list, you have to visit until the end of that list, in order for you to know that that which is O(n). And then you never say I think or I guess or whatever, you don't want to show the interviewer that you are not confident about your answer. I would rather think that you can be wrong, but never try to show that you're guessing something because if you're guessing something even if you got it right, they're not gonna treat it as correct. They're gonna say that you just guessed it, because you're remembering that a BFS is an O(n) operation, right? And always use your code to help you derive the answer. If you're visiting each node once, that is clearly linear time solution. Space wise, because you're using a queue at the worst, you are storing everything again. So it will be also linear space. That's what you would do, you would give the answer and maybe a quick one liner to explain why that is. That would be a perfect solution.

Wily Sandwich: Okay, great. And then yeah, the basically. Okay, so just review, time complexity. Yeah, I guess my question is space complexity like, really... Is that really that important?

Hot Gyro: Yes, yes, it is. And also, the most important thing is get the space complexity correct based on your algorithm, and not necessarily the optimal answer. Sometimes, some questions may not be easy to implement the optimal solution. So it's okay to implement a sub optimal solution. But what is required is when you implement your solution, your time complexity has to be correct based on your choices. So you need to be able to argue that you're using either linear space or more. And generally speaking for space, it's not linear it's constant. It is rare that space is more than that. Rare, not saying that doesn't happen. But most likely, it's linear or constant. When people say logarithmic, it's usually in binary trees where the depth of the tree is O(log n). But even that is, worst case scenario, still linear if the tree is skewed. So it's really just a try 2. And you just have to look at your code to see if you're declaring any list or any data structure. Anytime you're using data structure, it's very likely it's a linear space solution.

Wily Sandwich: Okay, great.

Hot Gyro: All right. Thank you for using interviewing.io today. And I hope you have a great rest of the weekend.

Wily Sandwich: Yeah, thank you. Thank you for your all your help on this. This was great, great practice. Thank you so much.

Hot Gyro: Yup, bye.