interviewing.io

JavaScript Interview with an Amazon engineer

Watch someone solve the max product of stream 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

Max product of stream

Interview question

1) Given a stream of numbers, find the max product until the given value generated by the stream. 2) Given a binary tree, return a list of all of its boundary nodes in counterclockwise order.

Interview Feedback

Feedback about Phantom Mammoth (the interviewee)

Advance this person to the next round?
Thumbs down
How were their technical skills?
3/4
How was their problem solving ability?
2/4
What about their communication ability?
3/4
Saying no to problem 1 and 2 as the candidate needed lot of hints. Provided feedback during interview

Feedback about Rocket Samurai (the interviewer)

Would you want to work with this person?
Thumbs up
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
N/A

Interview Transcript

Phantom Mammoth: Yeah, I have a meeting now for like an hour or 45 minutes, but then I can go downstairs. Yeah, I think it'll be okay. Okay, thanks. Hello?
Rocket Samurai: Hello.
Phantom Mammoth: Hey, great to meet you. I was just told by some people that are here doing some renovations on the house and there's going to be some noise.
Rocket Samurai: Okay.
Phantom Mammoth: I didn't realize that before. But I apologize in advance. Hopefully it won't be too much of a blocker.
Rocket Samurai: Oh, that's fine, it's not a real interview. And you're the one practicing. So as long as you hear the problem and solve it. Okay, so, yeah, can you please briefly tell me about like your current situation and what you're hoping to get out of this mock interview?
Phantom Mammoth: Sure, yeah. I have an interview coming up in like a week at Facebook for developer evangelists job on the Oculus team. And I haven't done like, I haven't coded that much the last year. So, and I definitely haven't done like algorithm and data structure stuff in a while. So I'm gonna try to get my skills back. And yeah, be ready.
Rocket Samurai: Sounds good. Okay, so let's jump into problems. And we can solve like, two to five problems, depending on the speed. And then based on that, I will give you feedback. And I can give you feedback after each problem or towards the end, whichever works better for you. So which one works better?
Phantom Mammoth: I would say...
Rocket Samurai: Yeah, let's do it like this. For the first problem, I will give you the feedback right after it. And then you based on the feedback, you will basically accommodate that feedback, if you want to in the next problems. So that, yeah, and get some coverage there. And then if I see any overarching feedback, I'll give you that towards the end.
Phantom Mammoth: That sounds good.
Rocket Samurai: Okay. So should we start with like something medium or hard? Easy?
Phantom Mammoth: Let's do an easy to medium one.
Rocket Samurai: Okay. Let's say we have like a stream of numbers, like this. For each dot represents a stream. And at any given point D, we would get an API request saying, get the highest product of three numbers, right? So we're supposed to take the current status of the stream up to this point in time and return them answers. And, yeah, I think that's pretty much it. And the stream is basically like ever growing, so it will keep growing. And then suddenly, someone will ask for another API request, and so on.
Phantom Mammoth: Okay, great. So let's see. So basically, whenever this function is called, we look for the three numbers that are most recent in the stream and multiply them?
Rocket Samurai: Three numbers which are highest, right? We want the highest highest product of the numbers in this stream. Yeah.
Phantom Mammoth: Oh, of any three numbers in the stream. Okay. Cool. So I'm gonna do JavaScript, just because that's what I'm most recently using and familiar with.
Rocket Samurai: But before you write anything, so what what are you thinking? Like, how can you solve this?
Phantom Mammoth: Sure. So yeah, I'm thinking, basically, have a... we're getting basically a stream or an array of numbers, and we're going to want to go through and find the three largest. So we would have maybe a hash table of like... Let's see. Yeah, like the hash table with three keys representing like, you know, the first second, third highest numbers, and then the values and then every time we we have a number we just just check those three current highest values. And if you know if it's higher than the third, we substitute out of the third, it's higher than the second, we substitute out the second. And if it's higher than the first we substitute out the first.
Rocket Samurai: But then you also have to update. If let's say, the incoming number replaces the first, then you also have to checkout out the two and three and replace two with one and three with two.
Phantom Mammoth: Yes, good point. Yeah.
Rocket Samurai: Okay. So that Yeah, so that can be done with like, three variables, right? So first highest, second highest, third highest. And what happens if there is like a requirement that it can be k? Where k could be like, thousand, ten thousand, whatever?
Phantom Mammoth: I see. Yes. Well, I guess in that case, yes, we wouldn't want three variables, we would want like a hash map, or hash table with all of the variables up to k.
Rocket Samurai: I see. But then what will be like the time complexity to figure out the highest product? And to maintain the stream to track these numbers?
Phantom Mammoth: Yeah, it would be kn.
Rocket Samurai: kn... what is k and what is n? So k is this k, and then what is n?
Phantom Mammoth: n would be the numbers in the stream.
Rocket Samurai: Okay. So, for each number, you're saying you'll do O(k) operation against the old data structures. So you have a hashmap. So you'll do a lookup in the hashmap. It will compare that number with all thousand numbers, and all the k numbers, right?
Phantom Mammoth: Yeah.
Rocket Samurai: Okay. So can you like, think of like improving that? Look up all that O(nk) to maybe reduce it to O(n log k) or something?
Phantom Mammoth: Yeah, let's see.
Rocket Samurai: Because k can be large, as well as n is also large and can be like billion or something.
Phantom Mammoth: Well, I guess what we can do is... get highest product of any, let's say 10 numbers. We can just keep... Yeah, interesting. I am not sure how you would, if there's a new number coming in and you're checking against highest product of any, let's say 100 numbers or five numbers? Like, I'm having trouble thinking of how you wouldn't have to check that incoming number against those numbers to know if you should substitute it somewhere.
Rocket Samurai: Oh, you're saying like, you're not able to come up with a way where you can think of a way to like, ignore comparing with every possible angle in the k numbers?
Phantom Mammoth: Maybe you can compare it just against the the minimum and the maximum number. And then, if it's in it's somewhere within that... Oh, yeah, maybe then you would just boot the minimum number off the product. So just like yeah, basically just reput, add the the new number into the k number array, and...
Rocket Samurai: So in that is enough to maintain like, sort of like a sorted array, right? Because if you just have like minimum and maximum, then that minimum and maximum can be disrupted. As soon as like the new number comes in, you will have to find a new minimum now. And then put that to the front. And to find a new minimum, you will have to go through all the numbers again.
Phantom Mammoth: That's a good point. Yeah. Okay, so that's not optimal. Um, let's see.
Rocket Samurai: So in that like approach, there is this angle that you keep the array always sorted, right? So you have like a sorted array of k numbers, right? So to maintain this array sorted, all you have to do is for the new number, you have to insert it in the right place in this array. And to find that position, it is O(log k) time, right? Because it is sorted.
Phantom Mammoth: Yes. But to keep it sorted would be a whole nother thing, right?
Rocket Samurai: Yeah. So you will find that position. But then once you find that position, you have to shift numbers around, right? That takes again like O(k) time. Yeah. There is like one data structure. Yeah. Which maintains a certain structure, which is going to give you like the minimum or the maximum. Hmm?
Phantom Mammoth: Would it be a tree?
Rocket Samurai: Sort of? Yeah. Have you heard of like heap?
Phantom Mammoth: I've heard of it. Yeah. I don't know if I'd ever implemented a heap.
Rocket Samurai: No, but have you like used it, like priority queue?
Phantom Mammoth: I don't think so.
Rocket Samurai: Okay. So yeah, this this question is basically around the data structure. So heap is basically like, you have like min heap, or max heap. And min heap will basically give you access to the minimum element in constant time. And to maintain the shape, it takes a O(log k) time, right? Where k is the size of the heap. And it is sort of like a tree, where you have like the topmost element, let's say like one, and if it is a min heap, all the children of that node are going to be smaller than the node itself, smaller or at least equal. So this will be like minus one, this will be minus two, and minus two's, children will be smaller than minus two, and so on. And you maintain the heap in this fashion, and then you do some operations on it whenever you insert new number and remove numbers, and all of those operations are O(log k). So yeah, so maybe you can look up into this data structure later. Like, I think like okay, so let me tell you one thing that... you can still do it, I think, if I tell you what, what the heap is supposed to do an operations on it, and maybe you can figure out how to solve this question. Is that okay, or should I switch the question?
Phantom Mammoth: No, that sounds good.
Rocket Samurai: Yeah. Okay. So let's say like, you have access to a heap, right? And you have operations, which are, let's say, like peak, which will give you like the minimum element in constant time. So we are using min heap in this case. And heap.pull will basically evict out the element. heap.insert will add a new element into the array. Both of these are O(log k). So this one is O(log k). Okay, from just using these three access patterns on the data structure, you should be able to solve it. So let's see, if you can figure this out.
Phantom Mammoth: We would still need to be able to, to go iterate through every element to be able to multiply them all together, right?
Rocket Samurai: Oh, yeah. Yeah. So but you can do that. I mean, let's say, yeah, so let's say that is a heap.getArray or something. It gives you all the elements that's in the heap.
Phantom Mammoth: Okay, cool. And then later, I'll just have to look at how to actually implement a heap, but that's cool.
Rocket Samurai: Yeah. I mean, yeah. And the interview, you don't have to, like, if somebody asks you this question, all you have to do is, yeah, care about this data structure not implemented, unless they ask you to.
Phantom Mammoth: That's great. Okay. Okay.
Rocket Samurai: So just to reiterate, right. So never jump into like coding before you specify the approach right? Otherwise, the interviewer is not clear what you're implementing. So make sure you communicate the approach which you are going to code before you actually code.
Phantom Mammoth: Okay, so I'm going to take a stream of numbers, and then create a heap, and then create a heap with that stream. So let's just say you can pass in the numbers into the heap, and and it organizes them based on what we want, I guess, min heap. And then what I'm going to do is...
Rocket Samurai: We don't want to pass the whole stream into the heap, we only want to pass in new numbers, and then maintain the size of the heap to k numbers. Otherwise, you won't be... if you are making the whole thing in the heap, that is unnecessary. And then that also increases the lookup time to O(log n).
Phantom Mammoth: Yeah. So we'll just create a heap. And then we'll iterate through all the numbers in the stream. And then we'll add if the current element that we're looking at is greater than the min element, we'll, we'll add it, can be a list of 10 numbers, and then we'll get the array and then multiply all the elements together. Or actually, no, we don't want to do that yet. We don't need to multiply yet. All we need to do is go through and create... go through the numbers one by one and then get the minimum element. And if the element value is... if there aren't yet k elements, we'll add the number, but once we hit k, then we'll check and we'll only add it if the number is greater than the minimum value in the heap.
Rocket Samurai: Number is greater than the min... Yeah, exactly. So you want to evict out like the smallest numbers and maintain the largest numbers.
Phantom Mammoth: Yeah.
Rocket Samurai: Okay. So I have given you this callback function, right. So whenever they tell you about like stream or something, basically, you have like a callback or like a generator, which gives you that new number, right? So you can have like something like next, which gives you that number and call this callback, something like this. So let's say you have access to this function, each new number on the stream, you're receiving it on this callback, so you can listen to it and maintain your heap here. And then when somebody asks you for get highest product, you use that to return the highest product.
Phantom Mammoth: Okay. So in that case, we'll define the heap outside of the callback. So it's still in scope. And what we'll do, and we'll know, let's say, yeah, this is outside. So we already know what k is from outside of the callback.
Rocket Samurai: Okay.
Phantom Mammoth: So what we'll do is if... Is there a method on the heap for a number of elements?
Rocket Samurai: Number of elements. Oh, you mean like the size of the heap? Yeah. Yeah. heap.size, or number of elements.
Phantom Mammoth: Yes, heap.size is less than k. And we'll just add a number. Otherwise, we'll check and we'll say... If the number is greater than heap.peek, just the minimum number. And what we'll want to do is... so heap.pull, it evicts out the minimum element?
Rocket Samurai: Yes, yeah. Peek gives you access to the minimum element without pulling it out.
Phantom Mammoth: So what we want to do is get rid of that minimum element because now we have another number that's bigger in the amount of k and then we'll do heap.insert. And actually, we can make this cleaner by moving...Really we can just say if heap.size is less than k and number... I'm just gonna leave it the way it was. I think I was clear.
Rocket Samurai: Yeah.
Phantom Mammoth: No. Okay. And then once we go... So this is the call that number received? And then do we want to return the get highest product of any k numbers in here? Or is that just the user will call that function at any time. And only if this heap we're keeping track of has k elements, then we return the product?
Rocket Samurai: So you're maintaining that heap. Okay, yeah, so looks good. And then there is that get product, right? So in the good product section, you just have to return your product.
Phantom Mammoth: Yeah, yeah, the user will call that separately, basically.
Rocket Samurai: Yeah, that is called separately.
Phantom Mammoth: Okay. So basically, like, we have our heap, they call get product of whatever k numbers. We'll check again, and we'll say we will only return the product if there's k elements. Otherwise, it's like a, it's not a valid call, right? Okay. So if heap.size is greater than or equal to, but it could be equal to k. And what we'll do is we'll convert the heap into... we will go through every element. Yeah, product equals product num. And after that, return num, otherwise, if the heap, if there aren't k elements yet, and the user calls get product, we could just, I guess, return negative one or something?
Rocket Samurai: Yeah, you can return like a negative one. That's fine.
Phantom Mammoth: Okay. So let me just, let's say we have two equals two, then x is three. Three times two is six. Yeah, that should do it.
Rocket Samurai: And can you like improve the time complexity for the get product part where it goes from O(k) to O(1)?
Phantom Mammoth: So we want to... Yeah, we would just want to multiply all the numbers together at once. But we would still need to go through every number and to... you still have to decompose that operation into a bunch of multiplications, right? Because you're multiplying all the numbers together.
Rocket Samurai: So is there a way to like, maintain that product as soon as you receive a new number instead of like calculating it after the fact. Oh, I see, yeah, we can do it. We can do it in our callback. Well, no, that wouldn't work because this is happening asynchronously. And if the user... we don't know when the user is going to call get product. It could happen at any point, right?
Phantom Mammoth: Yes. Any point. Yeah.
Rocket Samurai: So if it's happening at any point, and we're getting our numbers from this API at any point, then at the moment that we get it, we need to know I guess we can still keep the product up to date somehow in the callback. We would just have to... I guess, we would just have to subtract... Well, wouldn't we have to subtract our current, like the number that we're going to get rid of the minimum number from the current product?
Phantom Mammoth: Yeah, well, that that wouldn't be subtract, that will be divide because we are multiplying it. So we will have to divide it. If we are adding, it will subtract it, but in this case, we are multiplying things.
Rocket Samurai: Okay. So then we would just do cards equal... then in here, just return product.
Phantom Mammoth: Okay, and what about like? Okay, so for the initial one, you're saying, if the heap size is good, otherwise minus one.
Rocket Samurai: Okay, looks good. So what is like the overall time and space complexity for this?
Phantom Mammoth: Well, every time we get a number... well, I guess because number received is happening asynchronously, it's just happening at any point. So when we call get product, it's just O(1), because we already have the product because we've just been keeping track of it over time. And in terms of space, it would be O(k), because the heap has to keep track of every single element.
Rocket Samurai: Okay, so for each call of number received. The time complexity will be O(log k), right?
Phantom Mammoth: Oh, every call received? Yeah. Yeah, I thought you were talking about the getProduct call.
Rocket Samurai: Oh, yeah.getProduct will be constant, because you're already maintaining the product. Okay. And then overall, for n numbers, how much will it be to maintain the heap?
Phantom Mammoth: It would be log(k), right?
Rocket Samurai: For n numbers in the stream?
Phantom Mammoth: O(n log k).
Rocket Samurai: Okay. Yeah. Okay, so yeah, so let's jump into feedback quickly. And then we can move on to the next one. So here for this question, about any question I guess, like, so make sure to ask about the input types, input range. So in this case, like, you can ask questions, like will the stream contains zero, will the stream contain negative numbers? And then there's one more thing which you have to be very aware of, right? Whenever you are multiplying large numbers, or a lot of numbers, will the product go out of range, out of bounds of the datatype, depending on the language, right? So for Python, it may not go out of range. But I don't know about JavaScript, but in but in Java it usually goes out of range, right? So keep in mind that thing. And then once you have asked about like the types and everything, make sure to ask clarifying questions around the question. So in this case, I think for stream, you were assuming that it is going to be an array or something, right? So make sure if you have any like implicit assumptions, make sure to bring them out so that the the assumptions don't match the interviews, what the interviewer has in mind, they can correct you, right? So in this case, stream is like a generator, sort of. That's why we have this callback. So make sure to ask clarifying questions or clear out any assumptions. And then always specify your approach as clearly as possible to the interviewer before you jump into coding. And when you're specifying this approach, you can use like some sort of pseudocode or some English, you can write that down in the notepad if you want, or on the whiteboard. That is okay. And then once you have, like, written down the solution, make sure to pick a simple example and walk through the code so that you can catch any obvious errors. And this way, you're also eyeballing the code as well, right? So you sort of like become a debugger, step through your code using a simple example. And this way, you also help your interviewer understand your code as well. And then think about edge cases, unit test after you're done coding. So you can think about like, what kind of edge cases will you want to test. So for this case, you can test with like zero with negative numbers, if the interviewer tells you that they are possible, right? Otherwise, you will test it, this kind of solution with like, if the stream size is less than k, or if the stream is really big, and the stream has the highest numbers are really large numbers, which can go out of bounds and cause overflow errors. So you can bring that those up. And always like talking about time and space complexity, you can also like volunteer to talk about them, the interviewer does not necessarily have to ask you for it. And if you volunteer to give out that information, it just shows that you're confident, and you know about these things, right?
Phantom Mammoth: About the stream flowing, is that like you're saying, I should just ask about like, can the stream overflow? Kind of?
Rocket Samurai: No, no. So it's not about stream overflowing, stream will not overflow, right? So stream is just a generator, which will just give you new numbers, but your product, the variable product, can overflow when you're multiplying numbers to it, right? Because let's say if you have like a number, which is like, like 2 billion or something, and then you have another number, which is also 2 billion, then you're probably like overflow, and it will give you a negative or like some answer, which is probably not as expected, right? So make sure to bring up those things. Yeah, basically shows that you're paying attention to detail and yeah.
Phantom Mammoth: Cool. Okay, that makes sense. Thank you.
Rocket Samurai: Yeah, no problem. So let's move on to the next question. Are you comfortable with trees?
Phantom Mammoth: No, but I want to get comfortable, so let's do it.
Rocket Samurai: Okay. Or I can also give you like a because recursion problem as well.
Phantom Mammoth: Let's do tree okay.
Rocket Samurai: This is... Yeah, and try to use the feedback which I gave from the previous problem, whichever you think you want to use in other interviews that you're using this one. So that you get some practice on that. This is a binary tree, right? And output is looking for like this A B D H I J K L M N O G N C, right. So this is the out. It basically starts at the root node, goes around the root node in anti clockwise fashion, picking only those nodes which fall on the boundary. So anti clockwise from route A B D H. So all of these are on boundary in an anti clockwise order. I J K L M N O G N C.
Phantom Mammoth: Okay. So you're basically saying like, given an input of a binary tree, return a flattened counterclockwise array of the numbers, or the characters, that are... okay.
Rocket Samurai: On the boundary.
Phantom Mammoth: On the boundary, yeah. Okay, so we're taking in a binary tree as input and we will output an array. Okay, so what we'll want to do is start at the root node and then continue to choose the right leaf in the relative direction, if we were facing down. Or like I guess facing up from the root, yeah, like, it's kind of weird but down from the root. This is a leaf, but a real tree with the leaves will be on top. So let's just yet let's just say down from the root, continuing to move right, to pick the minimum most value, or choosing the right node until we get to a leaf. And then once we get to a leaf, then we want to go back up to the parent and then go to the left. Left being, I guess it would be left relative to the parent facing down. But really, it's the right from if we're looking at it, like kind of if this was on a flat plane, and we were above on the z axis looking down at an XY plane. So we would go right, then we would go back up to the parent, and then we would ignore e because it's not in the boundary. And then go to the left. Interesting. Okay, so what would be the best way to do this? So I guess once we go all the way down to the leaf, once we get to the first leaf, now we'd have to basically keep track, like maybe have a flag or something that say we've like, hit the bottom right most, or left most boundary. And so now all of the the non leaf nodes that we visit, we ignore, we don't add to the array until we get to the rightmost node of the entire tree. And then the parent nodes of that one, we start adding. That seems like maybe I'm making it trickier than it needs to be. But it seems like a pretty, like you would need a lot of different like conditionals and flags and things like that.
Rocket Samurai: But so I think like you're thinking about it in terms of like doing the collecting all the nodes in one traversals, right?
Phantom Mammoth: Yeah.
Rocket Samurai: So what if you could do like multiple traversals?
Phantom Mammoth: Ah interesting. Yeah, okay. So maybe what we want is traverse all of the leftmost nodes till we get to a leaf, and then traverse all the rightmost nodes, and then just add all the leaves. So we would want to do like, yeah, we would want to do different way of searching for each traversal, like that. Does that make sense? Or does that sound like it's on the right track?
Rocket Samurai: Yeah, yeah, definitely. So how will you... Like, if you want to focus only on the left? Left boundaries? ABDH, how will you collect that?
Phantom Mammoth: Yeah, so we would just continue to, you know, we would just continue to visit the left node of the current parent until we until we reached a leaf until there was no next left node.
Rocket Samurai: Okay. And what about the bottom?
Phantom Mammoth: The bottom? Yeah, for the leaf nodes, we would, I guess once we got to H, we would then know that we were at the bottom layer. So we would then visit, we would go up to the parent, which is D and then visit the right node and then go up to the parent which is B and then visit E and then visit the left and right.
Rocket Samurai: Is this traversal like a continuation from the previous one, which was the left, or is this a different reversal? Yeah, you're right. I guess we could start over, I was trying to be do a shortcut, but that probably makes it more complicated. So yeah, then we start over at A, then we would just go left, and then left again to D and then right to I, and then start again at A... Well, no, then we would just want to pop back up to B, because otherwise you have to start back at A every time to get the leaves.
Phantom Mammoth: Oh, yeah, yeah, so what I'm hinting at is like, you can do one traversal and get all the leaves, just the leaves, right? So the way you can do it is like you can do whichever DFS you want, in order, post order, pre order, right? It doesn't matter. As long as the left comes before the right, right? So as long as you do left traversal first before you do the right. Yeah. Do you follow?
Rocket Samurai: Yeah, yeah.
Phantom Mammoth: Okay, so what that look like, so let's say we start at root A, and then what happens? Then we go to the left to B. And then we go to the left to D. And then the left to H,
Rocket Samurai: And that is a leaf node, so you collect it. Okay, and then then you go back to D.
Phantom Mammoth: Then back to D. So then we would have to go, right.
Rocket Samurai: Because you are recursing on D .
Phantom Mammoth: Yeah. Yeah. And then we go back up, and then we have to go to the right. And then go to the right, and then the left to get to J, and then back up and then to the right.
Rocket Samurai: Okay, so you know how to traverse the tree, basically, you're doing in order, or not in order, but like pre order traversal. And then you're collecting all the leaf nodes. So how do you know if it is a leaf node or not? When to collect this leaf node?
Phantom Mammoth: Yep. Yep. When the left and the right are null, it's a leaf node.
Rocket Samurai: Okay. So this way, you'll be able to collect the left. And what about the right side? Is there any difference to the right side from the left side? Or is it the same?
Phantom Mammoth: It's the same.
Rocket Samurai: It's the same? I mean, on the left side you go left, on the right you'll go right. But the order will change as well, right? So let's say you collected A B D H for the left, and then H I J K L M N O for the bottom, right? So this one is L on that bottom. Then you have right, which should be in reverse order, which is G N C. And you don't want to include A because it is already included in the left. And here, in the bottom side, you don't want to include H, because we have already included in the left. And here, you're excluding O because you'll ideally have O in the bottom, but you're excluding it, because you have already included that in the bottom side.
Phantom Mammoth: Yeah, I'm realizing I think, would you be down? Because I know we only have like, another few minutes or whatever. Would you be okay with coding it out and talking through it? I think for the amount of time we have left, that'll be more helpful than... I just don't think I'll be able to do this in the time we have. And I think it'll be helpful to watch you and hear you and then I can use that to reimplement it on my own.
Rocket Samurai: Okay, yeah, sure. So, we have three boundaries, right? So this one can call get left boundary, right? And then you will pass the root, right? So the get left boundary will collect everything but the leaf node, because we want to ignore the leaf because we consider leaf as part of the bottom boundary, right? So we collect ABD from the side, and then we'll have the right boundary boundary. Then you have... this will collect all the bottom nodes and then we get... this will collect all the right nodes. And then get bottom. We have these three things. And this will return you a list. I'm just sort of like pseudo coding, but you'll get the idea and then once we have this list, even for left boundary because we don't want to collect the root twice, on the left as well as the right, so what we can do is we can do root.left so that we ignore the root on the left and on the right. And then we collect the root here itself with root.value is equal to root. And in the end, let's call it, or let's put this in a list so that it's easy to add it later on. And then we return all of this up ended. And, okay, so now let's do the individual pieces. So we'll do get left boundary. So here, once we come here, what we'll do is, first we'll check for the existence of the root node. If it exists, then we'll do... If it doesn't exist actually, then we can eliminate recursing further, so we just immediately... my keyboard, double prints everything sometimes. So if there is no root, then we return right, because the root is null. And that can happen when you're recursing on the leaf nodes, right? Otherwise, you know that that is a root. And in that case, you'll just collect that root. So create a list here. Right, so you have added that particular node to your list, and you'll return that list. But before that, you also have to recurse. So you... there is an edge case on the left side. I don't know if you noticed, but let's say like if there is no left for parent node, right, so what happens in this case, you will go from A to B to E to I, right? So it will go like in a zigzag fashion. So if there is a left node, you take that, which is your first priority on the left. But if there is no left, and the right node automatically becomes your boundary, right? So that's why we go from B to E, and then E back to I, because there is a left node, we don't take J because that is a left node, which is I. So that is the edge case we want to take care of. So that's why like always think about edge cases. If you're not able to find the edge case, it's fine. The interviewer can give you that feedback, or like hint. But always try to think about edge cases. So here, what do you want to do is you want to check if the root has a... so before we even add anything to our list, we'll check if the root has a left. If the route has a left, then you do this part. And if the root has a left, you take left, you take, it goes on the left side. Else you can blindly recurse on the right side. Basically, like you're choosing which side to recurse on for this condition for in this block, and then you're returning your list. So this takes care of the left side. And the right is going to be similar, except that the right will be doing this recursive part post recursion. That way you're recursing and then adding your current node. So that way you'll get the list in reverse order, you will get instead of C N G, you'll get G N C right, because we want it in a reverse order. If you look at the output here on line number 10. So if you do that for the right part, there you do a post order recursion sort of then it reverses the order. So I will not go into the right side because it is very similar to this. Let's go into the bottom one.
Phantom Mammoth: On line 23 when you're defining lists, if you're doing recursion, does that list become empty every time? Like, how is the list?
Rocket Samurai: Oh, yeah. Yeah, so what you can do is because we are returning lists, right, so on each recursion, you want to make sure either you pass that list into the input function so that each recursion adds it to the same list. Or whenever you are getting that list back, you can say return list, you can do like an extended or something. Good catch. So, you can do that. And then we define the return list, right. And then we do a list dot extend, and I think like extend probably returns the list too. So, we just return that and then we have the bottom side. The bottom is also similar, but a different kind of recursion. So here we just recurse on the left or the right and here recurse on both sides, the left and the right. So you take the root node and then anything we check for present root. If it is not present, then return an empty list. If it is not present, then and if it is present, then what you do is you check if child or something, should be a simple function, that if the current root is a child, then you create a list and add that to it. Can we do the same thing? Collect the list? Okay. And then the list plus this one. Right. So here...
Phantom Mammoth: You'd recurse on root.dot?
Rocket Samurai: Oh, yeah. That's basically the thing, besides collecting answers from both and adding it to the final list with the initial list.
Phantom Mammoth: Cool. Okay, that's really helpful. So just to make sure I understand for get right. Basically the same as the left except instead of pre order, we do post or so it would be if root dot right, and then return list equals get right boundary. Is that right? Is that is that the only difference?
Rocket Samurai: Yeah, I mean, you can still do the same thing and reverse the whole thing in the end, or you can do it like, recurse first and then collect the node. Yeah. So if it has the right node, you're going to the right side, if it doesn't, you're going to the left side, and then you're adding stuff to the overall like the current node to the overall list here. Right. So like this thing, which we did here, just that. Yeah, so be added. But before you add this stuff, you will basically do return list.add root.value, then you return the return list. Do you follow? Because here we are adding all the nodes, which come after the current node to the return list, right? So we get that answer. And then we are adding our current node after we have gotten the answer for the all nodes below that, yeah. So this way, we don't have to, I mean, you can still do it the same way as the left. Only thing is that you will have to when you get the answer, you will have to do a reverse on that answer. But if you do it this way, which we currently, then we don't have to do anything.
Phantom Mammoth: Cool. Okay. Yeah. That makes sense. So that's called post order traversal.
Rocket Samurai: I just made it up. But yeah, but it's basically like, you're doing it post the recursive call. Instead of like collecting it before the recursive call, you're collecting it after the recursive call, because you're doing that recursive call that gives you all the answers, and then you're adding your current answer to that.
Phantom Mammoth: Yeah, that totally makes sense. Wonderful. Okay, cool. I really appreciate that.
Rocket Samurai: Yeah, no problem. We have three minutes. So let's see. So for this question, again, you forgot to ask clarifying questions, right? So make sure you ask clarifying questions about the input. Like what kind of tree is it? Is it binary tree? Is it a binary search tree? Does it have any, like special rules on the tree? Or is it just like, simple binary tree without any rules. So in this case, it is simple binary tree, there are no rules, but like the tree can literally be just this, or it can be like they be A B C. And then you'll have this B to the right, and then B to the right, you can have duplicates all of that. So make sure you ask all like the sanity check questions when you asked about the type of input range of input, the type of like the tree and stuff. And then once you have those, again, the same thing, make sure you clarify your approach before coding. Yeah, and talk about time space, think about edge cases. Eyeball the code. Yeah, that's pretty much it. And if you know of like multiple approaches, like let's say like, you know how to traverse this tree in one traversal, also specify that and then say like, I would want to call it this way, approach one or approach two, because I think approach one is simpler to code or approach one has better time complexity, approach one has better space complexity or something. So come up with a trade off of what you want to do. One approach or the other. If you know of multiple approaches.
Phantom Mammoth: Great. Thank you so much Rocket Samurai.
Rocket Samurai: Yeah. Okay. So yeah, unless you have any questions for me, I will sign off.
Phantom Mammoth: Yeah, no, that's awesome. I really appreciate the help and hope you have a great rest of your day.
Rocket Samurai: You too. Yeah, all the best. Bye bye.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.