Java Interview with an Amazon engineer

Watch someone solve the boundary traversal binary tree 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

Boundary Traversal Binary Tree

Interview question

Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root.

Interview Feedback

Feedback about Colossal Typhoon (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

- make sure to eyeball a function for any obvious errors before running it - provide any other approaches to the problem and their tradeoffs (in the beginning or the end) - volunteer for unit tests, space and time complexity

Feedback about Rocket Samurai (the interviewer)

Would you want to work with this person?

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

Interviewer was helpful in guiding me to the solution, and giving me hints when I needed it, also gave good advice and appreciated his mentorhsip

Interview Transcript

Rocket Samurai: Hello.

Colossal Typhoon: Hello.

Rocket Samurai: Yeah, can you hear me?

Colossal Typhoon: Yeah, can you hear me?

Rocket Samurai: Yeah.

Colossal Typhoon: Great.

Rocket Samurai: This is for algorithms, right?

Colossal Typhoon: Yup.

Rocket Samurai: So do you want to do like two problems or one problem?

Colossal Typhoon: Let's try two problems.

Rocket Samurai: Okay. So one will be easy and like medium maybe and another one like medium to hard. Does that sound good?

Colossal Typhoon: Yeah, that sounds good.

Rocket Samurai: Okay, so I'll give you the harder one first so that we have enough time to do the easy one, even if you don't do the easy one, it's fine. You can at least walk me through it. Give some pseudo code, sounds good?

Colossal Typhoon: Yep, sounds good.

Rocket Samurai: Cool. So, I don't know if you have heard of this problem. If you have heard of it, then maybe we can do a different one. So you have the rod cutting problem, where you are given a rod of a certain length and then you're given prices for different lengths, find like the best possible way to cut the rod and sell it.

Colossal Typhoon: Yeah, I mean, I definitely. I watch the knapsack, I guess it's similar, basically the same problem, right?

Rocket Samurai: Yeah similar, yeah. So we want to try it or do you want to try a different problem?

Colossal Typhoon: Let's try a different problem.

Rocket Samurai: Okay. So, another problem would be... Basically you're given a binary tree and then you're supposed to find like a boundary traversal, so in anticlockwise or clockwise direction. So you wouldn't print the inner nodes, you would just print the outer nodes.

Colossal Typhoon: Okay, um, can we go through an example, just to make sure it's clear?

Rocket Samurai: Yeah, sure. So, let's say this is a tree and then in this tree... In this tree you would print basically everything, like the order I would expect is if we go in anticlockwise direction: 1, 3, 4, 5, 6, 7, 2, yeah.

Colossal Typhoon: Okay.

Rocket Samurai: So I went from...

Colossal Typhoon: 1 to 3 to 4, so it's counterclockwise, it's printing, okay. And I guess, let me see how it would work for like, I guess a bigger tree, maybe like.

Rocket Samurai: Yeah, if you had a bigger tree... Then only the nodes on the boundary will be printed.

Colossal Typhoon: So the inside doesn't have to be printed, just outside.

Rocket Samurai: Yeah.

Colossal Typhoon: Alright. Printing the left side of the tree would just be going all the way to the left, but then you would have to print all the nodes on the bottom. I guess the lead nodes. What's the best way to try to do that. I mean, if we did bfs, I guess you could just put the last level, but what if a node is missing, a node would you print the one above it? Like... How would that work? Can hear me?

Rocket Samurai: Sorry, yeah I was muted. So you can think of it like a rubber band which goes around the tree and anything that band touches would be that would be what you print, right? So your question I think was if there is no leaves here and this is the lead node, do we want to print this leaf node, right? Yes, so in this case yeah, we would print that.

Colossal Typhoon: Okay. Not really sure of anything.

Rocket Samurai: Even when you are thinking, you can think out loud, so that I can get in about your thinking, and maybe I can get you on the right track.

Colossal Typhoon: Well I definitely want to traverse the left side of the tree, so I think something like DFS would be useful, you're just calling the left node all the way down, so that will give me the first part of the tree. If I want to get the bottom leaf nodes, that would be the next part.

Rocket Samurai: So how will you get the leaf nodes?

Colossal Typhoon: Right, so I guess that's the problem I'm maybe stuck on thinking. Hmm... I guess my initial thought would be executing BFS to print the entire level. But since six is not in that level, it would still need to be printed, so I think that's not a good way to do it.

Rocket Samurai: Okay, but what other ways can you traverse a tree?

Colossal Typhoon: Ah, so I was thinking a BFS or DFS.

Rocket Samurai: So how are you thinking about like printing the left side, bottom, right side? Like we want to print all the sides, right? So let's try to think how would you print it.

Colossal Typhoon: I was thinking about recursion, just calling like root.left recursively, to print that.

Rocket Samurai: Okay.

Colossal Typhoon: And then, you know, getting to the bottom. I think once there's no more root left, you would need to get the leaf nodes from there.

Rocket Samurai: Once you reach the bottom?

Colossal Typhoon: Yeah, once I reach like seven. I'm thinking, how do I get eight, nine, six and eleven, twelve.

Rocket Samurai: So you're thinking of like first printing one, three, four, seven using recursion right? And then once you reach the bottom, you want to switch gears and like move horizontally somehow?

Colossal Typhoon: Right. And I guess the problem I am getting is... or maybe it would be easier if I just print an entire level, but I think because I also have the six, like I would have to somehow know to print all the leaf nodes basically. So I'm wondering if any like tree traversals, like pre-order, in-order, or post-order would be useful here. I'm just super used to trying to get leaf nodes, I don't think that really helps.

Rocket Samurai: You want to print the leaf nodes in a certain order, either left to right or right to left and how you get to the lead node doesn't matter, either you do DFS or maybe BFS or maybe pre order, in order, whatever right? You can ignore all of the nodes except the leaf nodes because you only care about the leaf nodes.

Colossal Typhoon: Right. So, I guess I could recurse the tree and whenever I see a lead node is a lead node, I could print that I guess. Doing another traversal of the tree, starting from the root I suppose.

Rocket Samurai: Oh, you're thinking in order traversal?

Colossal Typhoon: Yeah, because I want to go left to right I guess. So, I guess I'll print it if there is a leaf node if there's no like left or right? And I'll go out of that. So, I think the lead node is that way. And if we're printing the right side, I would have to be going root.right all the way to the right. So twelve and then seven and then two and then one. Well, I guess you know, I wouldn't want to print one. But I would call that on the right side. So it seems like I would separate the solution to like maybe three parts: printing the left side of the tree, the lead nodes of the tree, and that the right nodes of the tree.

Rocket Samurai: Sounds like a good idea.

Colossal Typhoon: Okay. Should I begin coding.

Rocket Samurai: What about coding?

Colossal Typhoon: Oh should I just try to code out a solution now?

Rocket Samurai: Yeah, I think we are clear on what strategy we are using for each side.

Colossal Typhoon: Okay cool. I guess the code could just be pseudo code, does it have to be runnable as well?

Rocket Samurai: I mean ideally should be runnable, sometimes like some interviewers would like you to run the program, it depends on the companies.

Colossal Typhoon: Okay. Yeah, I should make it as runnable as possible. How do I want the output to look like? Do I want to be like an array or maybe like a string that can just print out.

Rocket Samurai: Either one.

Colossal Typhoon: Okay.

Rocket Samurai: I mean, you would ideally like store into a collection and then print it out.

Colossal Typhoon: I'll just use a list. Just say let's have a checklist. Maybe I'll just make a helper function to call the left and the right side. I don't want to do it in order first actually.

Rocket Samurai: What is the current for?

Colossal Typhoon: I guess I want to add three, I want to add four, and then add seven. So I guess I could add it iteratively, like going down the recursion stack, and just return that. Or I could just add their node value and then kind of sum it up on the way back. I'm thinking which way would be best but... I mean, I guess I don't even need current. If I wanted to keep it like maybe a little cleaner, I could just leave our current. Maybe I can go from zero to here, like this would have to be first, right? So like maybe set... And I could just call left side. I could set the value to be first. So there's testing at this part of the code. Go all the way down to seven. It was entered as seven so far, and we returned upwards to four. Four will set itself to be the first part of the answer, so before and then three. I think it works properly. Okay, so that's the left side of the tree. So I would want to call this first. So this should give me: one, three, four, and seven. Next I would need to look at lead nodes. I guess I could traverse it in any order like you mentioned and just look if it's a leaf node, and if it is, then I can add it to the array. I think the only caveat I would have to look for is the duplicate of the bottom left. So I need to keep it for that when I do.

Rocket Samurai: Since you are done with the left side, do you want to test it quickly so that we are done with left side and we can move on to others?

Colossal Typhoon: Sure. Should I write actual runnable code? I think I need to make a tree that...

Rocket Samurai: Yeah. I think I could see a bug in the left side code, so that's why I want do it.

Colossal Typhoon: Oh yeah, gotcha. Let me create a tree first. Oh yeah, I guess there's no... I don't check if it's null, so I guess...

Rocket Samurai: You're setting the value at the 0 index because you want that roots value to be included.

Colossal Typhoon: Yeah, I want the root value to be included I guess first. So I want to append it to the beginning of the answer.

Rocket Samurai: But you can't directly set it, you have to like prepend it, like you have to pre-append it sort of. Like add that value at the first position and slide all the other ones to the right, Because otherwise you'll overwrite zero.

Colossal Typhoon: Right. I guess I could just add it and then maybe it might be in the wrong order actually, maybe reverse it that way back. Okay. This tree is very simple, so should I make it like a harder tree, because I think it's really hard to tell. So this tree should look like...

Rocket Samurai: The answer should be one two, four, eight.

Colossal Typhoon: Yeah, so it's in reverse order, so I guess I could just reverse it.

Rocket Samurai: So like ideally if you had a function which gave you when you asked for the left side, it gave you everything on the left side, right? Including the root or without the root. So that is up to you. So you have to like I guess fix like what you want out of your left side, and then you can do the main however you want. So like what is your expected output out of this function here? Left side.

Colossal Typhoon: I guess right now it's expected I think... I want to not include the root. I'm adding the root I guess in the beginning and then I just want the left side without the root. So right now, it's in reverse order because I'm just appending it here.

Rocket Samurai: Before this it was like you were adding root to the end of the left side, so that would mean the root was out of order and if you reverse the whole thing, and that would be something else. But okay, now it makes sense. If you're adding the root.

Colossal Typhoon: Yeah, before I think I was maybe really wrong about it. I was trying to reverse the left side of the this part. and not the root itself, but I think that code was kind of just too convoluted. So, I think I'll just go back to doing this. So, I think... Okay.

Rocket Samurai: And do you still see any bug in left side? Because I can give you like one example, right? So let's say if that tree was like... So let's say one is root and then that root has a left right which is three and that root has a right side which is four, so this is right. This is left and that is the root and this right side has a number which is five left. So in this scenario where your root has a left side, and that's left side has a right side and that right side. Has a left side. So you're always going left, right? So you would just stop here.

Colossal Typhoon: So, I guess this will look like I guess one, three, and then with 4 beyond 3's right or one's right?

Rocket Samurai: And then 5 is on the left of root.

Colossal Typhoon: Yeah, so I guess in this case it would just have one in there, you just have three and the left side would be returned here, right?

Rocket Samurai: But because we want to print the boundary we have to capture one three four five as well.

Colossal Typhoon: So the expected output should be one, three, five, four, is that correct?

Rocket Samurai: Oh no, expected output would be one, three, four, five because we go along the boundary, so boundary of this tree is... if you tie a tight rope around this, right, which bends around the corners you'll capture one, three, four, five.

Colossal Typhoon: Oh, I see, okay. In this case, yeah, then this code is definitely doesn't capture that. So if I'm still going with the whole left side thing, I believe no thing at the right side thing. I think if there's no left and then there's a right and I mean, that would be included technically in in the left side, yeah. Okay.

Rocket Samurai: Just to clarify, by left we mean everything which is on the left side of the tree.

Colossal Typhoon: Okay, so I think I need to also like do... I guess basically first I need to go left and if there's no left then I would go right, and then I were trying to recursively do the same thing. So I would add the root first and then... Start at the left and I could to right? So this would go all the way left and left here would be null, so this would return null and then it would look to the right which would be four, go to add four, and then it'll look to the left of that so add five. So I think this should give the proper output. I guess we could um...

Rocket Samurai: But here you're printing the whole tree, right? This would print the whole tree. So you're adding left and right to everything.

Colossal Typhoon: For this example, we will want that though, right?

Rocket Samurai: I mean in the function we only want to print things which fall on the left boundary, but here like you're adding left and if there is a right you're adding that as well, right?

Colossal Typhoon: Oh I see. Yeah, yeah. I only want to add the right if there's no left, right?

Rocket Samurai: Yes, yes.

Colossal Typhoon: Okay. Okay, so now here I would look at three. I would add three. If three is not null. I mean the left of three is not null, which it is, it won't do this part or just look to the right and the right would add four and it's four, the left is not null, and it will add five.

Rocket Samurai: Okay, can you run that through the test?

Colossal Typhoon: Yeah, maybe add your example into the test case. Okay, so this one puts one, three, four, five, that looks correct. I think... I mean, if we do the rest of the code, we would need to make sure that doesn't get run. Well, I guess the right side wouldn't get run because there's no right in this. So I mean, I guess in the rest of the code we add the leaf nodes and then the right side of the tree. So the right side of the tree, there's no right for the root, so I guess that wouldn't add anything to it, but I guess it would add an extra five, right? So that's like a duplicate we need to like, make sure is taken care of.

Rocket Samurai: Oh are you talking about just about left side or are you talking about like the code as a whole, like print counterclockwise?

Colossal Typhoon: The code as a whole. I was talking about the things that we haven't implemented yet, like printing the leaf nodes, printing the right side of the tree. I just see it is the correct input and output for left side, but I think for leaf nodes because it would print... technically it should print five, right? That would be the expected value, so that'll be different.

Rocket Samurai: There's an overlap in here, yeah.

Colossal Typhoon: I guess maybe a brute force way just to make sure. I mean will the values in the tree be unique?

Rocket Samurai: No.

Colossal Typhoon: Okay, so in that case, basically the last element should be not printed or we could do the first element and the leaf node is not printed, so that would start for the bottom left, right?

Rocket Samurai: Yeah, makes sense. I mean, you can either remove it from the left side or the lead nodes, yeah.

Colossal Typhoon: Should I try to implement the leaf node code now?

Rocket Samurai: Yeah, okay.

Colossal Typhoon: So. Here, I want to just... I guess I can DFS and if there's any leaf node, I want to add it to the answer.

Rocket Samurai: Okay, so in what order would it print the elements of the... what order would the leaf nodes be printed in?

Colossal Typhoon: I guess I want to go left to right so in this example, it would just be five and then there's nothing else after it, but maybe if you look at the bottoms example, it should be seven, eight, nine, six, eleven, twelve.

Rocket Samurai: Sounds good, yeah.

Colossal Typhoon: Yeah. So basically you want to keep going left. This is a bunch of leaf nodes that I want to add to the answer. Otherwise, I'm gonna go left and right. Should all the way left to seven. There's no left so that's seven. Then it will go up to four. Which we go right. Okay. I wonder...

Rocket Samurai: So here you're adding root to the answer if it is a child, right? If it is if it is a leaf node, you're adding it to the answer. And then you basically like get all the notes from the left and then to the answer get all the nodes from the right, add them to the answer. So this thing maintains all auto generated data that it is going from left to right. Yeah, looks good to me.

Colossal Typhoon: So there's a duplicate that we talked about. I guess to get rid of it, I could just remove the last node of the left side or I can remove the first node of the get lead nodes.

Rocket Samurai: That you can do it in the main, you can remove one of them.

Colossal Typhoon: Maybe I can remove the last element. I don't want to initialize it, it'll make it cleaner, but I think here I might just have to. Yeah, so maybe... With the last element of the left side and I did the leaf nodes here, so onto the right side of the tree, I expect it to be pretty much similar to the left side. So I get I guess I could change a few things. Okay and I want to call this on the right side of the tree. So pretty much this. So here if I go in the right side of the tree, I think there would be another duplicate on the bottom right, which is the last element. So I want to do the same thing, I want to delete up here so I guess... Okay, so there is... so I guess nothing was returned on the right side here, because there is no right yeah. So here I guess I mean it returns a null, which is fine, so I mean to check... I have a check here that size is at least one, then I could remove it, otherwise I don't. Maybe I could just make a helper message to do all that. Return this.

Rocket Samurai: So when here then can you like write like a better example, so that we cover all the three cases?

Colossal Typhoon: Yeah, so let me do this. That looks okay to me. Let me just make sure it's runnable. Okay, so this looks okay for this example. Let me calculate the one that we had down here. I think that was a good example. Okay, so I see one bug with the right side, it should be the reversed order, so it should be bottom up. Okay. Alright, so I guess here we can keep the same order, but I can reverse it on the way back before I edit.

Rocket Samurai: I think that is a simple issue and we'll fix it. So would you mind telling me the time complexity and space complexity?

Colossal Typhoon: So I guess we have to go through the left side of the array, so that's traversing the height of the tree. So possibly that's O(n), you know depending on if it's an unbalanced tree, possibly like a list. So O(n) for that. I'll start to traverse the leaf nodes, which is the same, so it's basically traversing it three times, so like three events. So just O(n) time and space-wise, what we had to at least keep the array list of how many elements are in the array at least, so it's O(n) as well.

Rocket Samurai: Okay, so what factors the space depends on?

Colossal Typhoon: I guess it depends on like the height of the tree and the amount of elements we're adding. So it should pretty much add... Well, I guess if it's a really wide tree... It wouldn't have to add the elements in the middle, but I think it's bounded by the amount of elements of the tree in general.

Rocket Samurai: So, space-wise you're doing a DFS in all cases, right? For the bottom, left, right you're doing.... Yeah, so DFS, that would depend on height of the tree and if it is a linear, like a long tree, with no adjacent edges or something, then that will be O(n) as well. But on average, it will be like the height of the tree, O(log n) maybe, if it is a balanced binary. Yeah, so mostly... so do you think like if we traverse the tree for the bottom case, so can we do that in any other do you have this stick with one particular order of reversal?

Colossal Typhoon: Well I guess you want to traverse it counter clockwise, you want to do it from left to right. Or if you did it right to left, you would need to reverse it at the end.

Rocket Samurai: Yeah, so I guess the question I meant to ask is if you did pre-order traversal, or in order traversal, or post order, does it matter?

Colossal Typhoon: Okay, um. I guess not because it's just... I mean typically it's all like left, right like before, like there's always before right? So, I guess it doesn't really matter.

Rocket Samurai: Okay. Yeah, I guess. You solved it pretty well. Do you need any feedback?

Colossal Typhoon: Um, yeah, I mean, I guess this question was definitely harder than I... Like I guess I had to work through it. Just typically, this would just be the first part of a two-part question, right? I guess part 2 would be harder?

Rocket Samurai: Yeah, that depends on if you solve it really quick and the interviewer has time for like another question, they would ask you another one. But even if you just did it for the whole interview... This should be doable in like 45 minutes. Usually like first round of interview in the phone screens and if there is online test, usually it's 45 minutes or 50 minutes something like that. So you should you should be able to do it with test cases passing and everything, right? If there is more time, then maybe they'll throw in another one like a smaller another question and then probably dive deeper into it. Yeah.

Colossal Typhoon: Yeah, oh no, I mean yeah, I'd love some feedback and also the only other question I have was like, maybe my pacing, like so it's kind of related to that. Was I good on pacing and like what are your thoughts?

Rocket Samurai: What do you mean by pacing?

Colossal Typhoon: I guess I just expected to solve it a little faster because you mentioned there'll be a second part and I just felt... I just thought I was a little slow.

Rocket Samurai: I mean yeah, I guess like I think you were pretty good. Only thing is like if it was a real interview I would just ask you for like the bottom part and left part, that's it. Because the right part is symmetrical, so you don't really have to do much, but yeah, I think you would have done first and second part pretty quickly if you didn't have to write like all these cases and whatnot. But yeah, this question is good enough for like one interview round I think, and if like if there is time they'll ask a second one. But usually there's not much time. But yeah, you should try like, you should always try to solve questions faster so you can solve more questions, because if you have like a candidate who also called the same question in the same amount of time and for you and the other guy or both of you did one question, so they would always be if you had done two questions then you would have a bigger advantage or at least if you like gave them like a high level overview of the solution, even though if you did not finish the second question, right, you still have some advantages. So other than that I would say like if you volunteer for like whenever you are done solving your problem, you should like try to volunteer about space complexity and time complexity because that is like the standard for every interview and I've had like two people when I was interviewing they told me like you should just give these information a bit to the interviewer so they don't have to ask for it and this kind of shows that you are on top of your game.

Colossal Typhoon: And thought about it I guess, yeah.

Rocket Samurai: And anything else? Other than that, yeah, your naming and everything was pretty good, and you solved it. Yeah, you should also volunteer to ask for whether you need to write units, right? Sometimes they ask you about it, might as well just ask and most of them ask you to do two or three cases.

Colossal Typhoon: Yeah, I mean, I definitely would've want to test it more, but it's just like kind of a pain with the trees yeah.

Rocket Samurai: Yeah, any other questions you have for me?

Colossal Typhoon: Yeah, I guess that's it. I don't I don't have anything else specifically.

Rocket Samurai: Okay, then how are you preparing for like system design?

Colossal Typhoon: I've done maybe like one system design interview, but I don't know, do you have any recommendations?

Rocket Samurai: Yeah, so I'll just write it down here. Grokking the Systems Interview. Maybe you've heard of it?

Colossal Typhoon: Yeah, is that the one on educated.io?

Rocket Samurai: Yeah, and there's a good book called Designing Data Intensive Applications, so this one gives you an in-depth... basically it's a comprehensive guide of building distributed systems, so this one I found really useful to talk about in interviews at a high level and there's like a lot of buzzwords in there and you can throw them in the interviews and people get impressed. It's a really nice book.

Colossal Typhoon: Yeah, I've been spending most of my time on like data structures and algorithms. Do you... How much time did you spend on system design? Or how much time do you think I should expect to spend?

Rocket Samurai: So let's say you have like eight hours in a day studying for interviews right? When I had eight hours, I would spend like five hours just coding, focusing on like coding problems and then the other 30 or 40 percent on system design because like that is also a big factor when it comes to all the big tech companies. And then there are a lot of YouTube channels as well, where you can like get a feeling of what kind of questions they ask, what kind of things they discussed, yeah.

Colossal Typhoon: Yeah, I've been watching some of those for system design, but I think it's hard to practice system time because I mean, there's LeetCode for coding, but system design is kind of just... You just do mocks, I guess there's no other way.

Rocket Samurai: Yeah you either do mocks or you find a friend who you can do mocks with.

Colossal Typhoon: Yeah, yeah.

Rocket Samurai: But in the Grokking the System Design Interview, they usually like specify like the whole pattern, like you talk about estimation, you talk about system design at a high level, then you talk about partitioning strategies for database.

Colossal Typhoon: I just need to do more of that.

Rocket Samurai: Okay, nice talking to you.

Colossal Typhoon: Thank you, appreciate it, good talking to you.

Rocket Samurai: Bye.

Colossal Typhoon: Alright, bye bye.