Python Interview with an Amazon engineer

Watch someone solve the extract leaves from 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

Extract leaves from tree

Interview question

1) Given a tree, extract all of the leaves layer by layer 2) Given a list of tuples representing a start and end time, determine how many meeting rooms are needed to schedule all of the meetings

Interview Feedback

Feedback about Epic Gargoyle (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?

3/4

Saying yes cuz of speed of solving problems, coding, thinking out loud, time/space analysis action items provided during the interview - reduced point for comm cuz candidate didnot ask many questions and wasnt proactive above time,space and tests - reduced point for problem solving cuz needed hints for problem 1 - reduced tech skill point cuz the approach used sorting for problem which increased the overall time, and I had to mention this to the interview to fix it. If you called it out on your own, then that is better

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

No

Interview Transcript

Epic Gargoyle: Hello.

Rocket Samurai: Hello. Can you hear me?

Epic Gargoyle: Yes.

Rocket Samurai: Hi. So yeah, can you please briefly tell me about your current situation? How can I help you in this month?

Epic Gargoyle: Oh, yeah, sure, um, I'm going to have a virtual site with Amazon in, like, probably another 10 days. So probably, as far as I know, like, usually we will have one or two algorithm questions in a coding round. Probably also with some, like background introduction and behavior questions. So it could help me to, like, have a very standard around mock interview for virtual onsite, something like that, if either to have behavioral questions and algorithm questions that will apply.

Rocket Samurai: Okay, yeah. So, anything, so if we just do algo questions, we can probably do two. And if we do like behavioral then maybe we'll not have enough time for two.

Epic Gargoyle: To do the other interviews, usually do interviews, usually, at the earlier questions first, or after the?

Rocket Samurai: Interviews usually usually have one or two behavioral questions and then algorithm.

Epic Gargoyle: I see I see. I mean, either way, we can start with our coding first. And if we have time, we do a behavioral question. Does that make sense?

Rocket Samurai: Okay, sounds good. So and what resources have you been using to prepare for these interviews?

Epic Gargoyle: Resources? Just get some practice on LeetCode.

Rocket Samurai: Okay. There's also this thing which might be useful, actually be useful to be aware of different patterns in coding problems. So like to pointers, sliding window to heaps? Topological sort, all of that. So yeah, all of that you can find the like modified binary search. So it's good to be aware of like, what, what patterns are out there and do a couple of examples of each pattern

Epic Gargoyle: That is very useful. Thanks.

Rocket Samurai: Yeah. Because otherwise, if you're not aware of a pattern, and they give you the pattern, then it becomes hard to like, come up with that technique on the spot. So it's cool. So if you click on drawing mode on the top left, yeah, sure. Let's say given this binary tree... Okay, so this is a binary tree, and the output we expect is on line number one in coderpad. It's going to be a list of lists. And what we do is we look at this tree figured out what are the leaves in this tree, right, so the leaves 6 5 4. So we put 7 6 5 4 in the output. And then let's say like, once we extract these leaves, now the tree is left with one, two, and three. So in this tree, In one, two, and three, we'll have the leaves three and two. So, we put three and set of leaves in the output and then the only tree that is left is one. So we take because one is only the if it is also one is the only node in this tree, so it is also a leaf. So we put one in the output. So this is the output.

Epic Gargoyle: I see it seems like we need to collect the leaves in reverse order for each level in the correct question here? So what if we have a tree like this 5 6 7. So basically here is actually an empty node. So the shell we returned. So the first level of our output is as should be like 7 6 5.

Rocket Samurai: Exactly, so 7 6 5 2 because two is a leaf five is a leaf six is a leaf seven is a leaf.

Epic Gargoyle: I can hear like to actually have just have one child have the right child.

Rocket Samurai: Here, right? Yeah, so two is not a leaf. Yeah. So it'll be 567 and then you'll have two and three and then one.

Epic Gargoyle: I see and if we don't have the five here, if we don't have the five here.

Rocket Samurai: Then it'll be 267 there will be.

Epic Gargoyle: I see I see. Okay. Cool. Yeah I first thought about this question seven. Yeah, we can use the recursion to go to traverse down to the bottom level of the tree. And we can tell you know these digits at least by see if it had if it had any left or right children and if not we will do the we will collect this. We will put it into the our final result so, like things we are going to track everything in reverse order. So, we can always go to the right hand side first and then to the left hand side and if we see... if we see the character the right hand set the current node is that they can... Yeah, so, if we see like a node has any hidden children then we will leave it to the next level otherwise we will put it into the final output so that they make sense?

Rocket Samurai: So, you use and you do a DFS and then you check whether the node has the any children if not you'll put it in the final output. Yep, yep. And so, how do you know if you see we need to collect all the nodes basically it's number.

Epic Gargoyle: We can check if it is a child node first, if it is then first of all we will put 7654 into the into the output okay. And we have returned that connecting we can return a connecting status from the recursion function so that we can know for example like for three they didn't have any on our second how something like how should we build this recursion. Yeah, and when we do the return, I think after we have collected the other we have collected a certain node, we can return on now that into it. So that that after six and seven are collected into the into the outputs, we will have no children for the node three, then we can do it in... therefore another round poking out. I think about this or even the output is really in reverse the order? Is it okay for us to just collect everything in order and then reverse the order in the output for everything, because if we just traverse all the nodes level by level, then we can easily get the output...

Rocket Samurai: But will that work for the last example, which is 123? And four and five, four and five are children of 345?

Epic Gargoyle: Children? Three? Yeah, that shouldn't be a problem. Because if it's like that, the output would be because we are collecting everything level by level, then okay, okay, that is level by level then two wouldn't be in the right in the right level. Two is actually to level four and five. Okay, let's still go for the way that's to the recursion to the bottom.

Rocket Samurai: Let me let me know if you need any hints or you can keep thinking yeah.

Epic Gargoyle: I see. Okay, so here, we do the recursion all the way down to the, to the bottom. And if you leave child, put it into the result. And after that we should mark all this will be ideal to mark all these as null values so that we can have a new level of leaves. And the hope and when you find a way tomorrow to return the status and put them into the right level of output.

Rocket Samurai: You know, that's a good observation that each node needs to go into its right level. Right. So what information can you pass back when you come out of recursion to the nodes so that it goes into the right level?

Epic Gargoyle: Yeah, yeah. Like we need to find a right return status to make sure that output to find the right output level, right? Does anyone know?

Rocket Samurai: If you knew the level of each node, right? Let's say let's say like you knew that this was level X. This was level X, this was level X and so on. And this was level Y this was level Z, right? And if you knew this information, you can easily put them in the right level in the output. But you don't know that yet. So how can you know that when you're doing your recursion?

Epic Gargoyle: Let me think this can be related to the depth, but that only happens when this is like a balanced tree. Because otherwise there will be no child for this.

Rocket Samurai: Not necessarily true, right? So let's say let's say you have some node A which has a child B and a child C? Right? So, let's say level of be able to see the example. ABC.

Epic Gargoyle: Yes,I have a second one on,

Rocket Samurai: Zoom out. If you zoom out.

Epic Gargoyle: Yes, I can.

Rocket Samurai: So let's say like ABC is our tree, where is the root node of C and B? And B is, let's say like a sub tree, right? This is a sub tree. And this is a sub tree. And say like, the level of this is X, level of this is Y what do you think will be the level of A?

Epic Gargoyle: Let me think about it. It should be...

Rocket Samurai: When they turn it around. I just put like a concrete number here. So let's say X is equal to 20, Y is equal to 25. Right? So the level information for B is 20. And for C is 25. So what do you think will be the level of A.

Epic Gargoyle: This should be? Because we will first collected the level 20? And then we will go for level 25? And then we go for a is that going to be like 26? Or something?

Rocket Samurai: Exactly, yeah. So it'll be 26. Because you want to pick the deeper tree as your level for the parent. And because parents level is always going to be one more than the children, right? And you want to pick the max of the children so that you are at least one more than both the children.

Epic Gargoyle: Okay, actually...

Rocket Samurai: So how can you use this sort of technique to come up with level information for all the nodes. And if you have the level information for all the nodes, then you can easily populate them, put them in the right level in the output.

Epic Gargoyle: Shall we use like a hash table to use the level number as the key and the nodes so that the node as a result that devalues the piece of nodes? And when we do, and we have formatted formatted output based on the hash table. In an array.

Rocket Samurai: Makes sense. Yeah. But how will the recursion work? How will you compute those levels? At each node?

Epic Gargoyle: Add to the second... editor beginning for the first level, I will put that level as zero and after that in a second, because if it just goes zero, then this will be a one this will be one. But this actually will be true. But actually we are collecting this part together. If there is no for f5.

Rocket Samurai: So yeah, like again, look at this example, try this one. So what did we because we know the level, we know the level of children before we knew the level of parent, right? Because if you do your leveling from the top, then your leaves can be a different level. But we want the leaves to be at the same level.

Epic Gargoyle: Yes, so probably after we we have after we have hidden a leaf, then we can return the level as zero. And in each one of the the parent, we will take the max between the the left and the right. And the plus one that is the parent level. And we can based on this parent level to put it into the right. Replacing the hash table.

Rocket Samurai: Make sense. Yeah. So can you explain the whole? Let's start from the beginning right. So you are at you're looking at the root what happens next?

Epic Gargoyle: Yeah. So since we are doing the collector, all the nodes in reverse order, then we will go for that right hand side first. And we will have depth first search all the way down to the leaves. And then we've the way we've to tell if a node is a leaf to see if it had any leaves or children. If it doesn't, then we will return the level of it. If it's a leaf at the very beginning, it's actually zero otherwise and ended the level of their parent nodes would become. Yeah. So, like the jump off condition for this recursion should be like, if the node is actually no value, then we will return zero. And after that we will see the left and the right we will take the max between the left and the right and as one as a parent level. So it can be put into the reified right placing in hash table.

Rocket Samurai: Makes sense? Yeah. And so what will be the tracing of recursion, right? So, you go from 1233 to seven, and then what happens next?

Epic Gargoyle: Seven will be... Yeah, we will assess one level down below seven, and we will see nothing, which means seven is actually seven is actually underneath we will collect it. Yeah, we will collect it. This one and this one here, we will collect it into the into the hash table. And we will return the actual number of seven. And we will see if the right hand side and the left hand side level are the same. Because if they are the same, then it means both of their both children of the parents will be collected at the same time and the parent will be ready to be collected. Otherwise, we need to go for...

Rocket Samurai: No, but why do you care about both be the same? Because as long as you know the level, you can just collect that node.

Epic Gargoyle: Yes, that's correct. That's correct. Yes, that's correct.

Rocket Samurai: So you go from three to seven. And you see that seven is a leaf, so you put it in output level zero, and then you go from three to six. And then you see that six is also a leaf. So you put six in the output, right? And you pass that information back to the parent. And now you are in the parent, right? Because you're done with the children. So where do you think three will go?

Epic Gargoyle: Three, we'll go for it, we'll go for level one.

Rocket Samurai: To level one.

Epic Gargoyle: And now, parent level is determined by taking the max of the children across one. Yep.

Rocket Samurai: Exactly. Yeah. So now you're done with three, right? What do you think happen happens next.

Epic Gargoyle: If you haven't it will go it will go for node two and we will also see the the level of it the the level number is actually zero. So two will be put together with seven and six. And then we will go from one which has the level number as true because we are taking the magnitude of zero and one and plus one.

Rocket Samurai: Perfect. So what will be the time and space complexity for this?

Epic Gargoyle: For the time complexity? It will be the number of nodes of the whole tree it seems we are we are going to traverse every single node in this tree. And for the space complexity, if we have counting the stack s, that that will be the depth of this tree.

Rocket Samurai: And what will that be in terms of the number of nodes?

Epic Gargoyle: If it's a balanced tree, then it's actually log n, if n is the total number of the nodes if it's a balanced tree, but that's like the, the ideal scenario. In a worst case, this tree will be looks like a linked list. Like everything's we got all the way down to one side that in the worst scenario the space complexity will be the number of knows which is O(n).

Rocket Samurai: Okay, make sense. So you can start coding and then we can move on to the problem.

Epic Gargoyle: Oh yeah, sure. Shall we close this window or okay?

Rocket Samurai: Okay, you can close it if you want. You can because it will call that.

Epic Gargoyle: Okay. I'm going to use Python to do the coding, the typing because okay okay we'll call this function collect and we will really treat the root on this tree into it and if we'll handle some corner cases like the trees actually announced value and we will just directly return empty list without reducer. Yep and we'll have hash table array for collecting everything okay cool. And? Okay so here we are going to the recursion function. Which means a tree just goes for it go for it right hand side first. To the hash table for to the collection. Okay returned to level here using the shirt write out the tree no structure?

Rocket Samurai: No.

Epic Gargoyle: Okay, cool. So, yeah, if you're here we initialize the hash table to to the collection and we use a recursion function to to go all the way down to the bottom level of the tree. And you can know these actually are now value we will read negative one and okay and for each every one of the nodes, we will always go to the right hand side first and checked the right hand side left side level and the left hand side level and the current node level will be the maximum between the right and left plus one can explain this based on our previous example. So, at the very beginning, we will traverse all the way down to seven children. And since he doesn't have anything, so, both sides will return negative one. So, and then the the level of of node seven would be zero and it will it will be put into the hash table to record to record it. And after that, we will go for node eight as the Node seven this also has a level in our zero they also go for the same list of the level zero and therefore, the no three in tech pitch will have level in our s one for the note one you have the level two. So when we when we want to generate the final output, we will sort the hash table based on based on these key so that we can always return the lowest level first and all the way up to the top level.

Rocket Samurai: Make sense. So what will be the time complexity? Overall time complexity for this code?

Epic Gargoyle: Using the recursion I create a time complexity would be number of number of nodes. But for since we are going to sort the hash table by the level to amortize the one we're having oh let's say I gave you the worst case the time can be sort of worst. Worst case it can be a number of levels can be a number of nodes that will become O(n log n).

Rocket Samurai: Can we make it faster because we want like linear right? So what can we do to avoid sorting?

Epic Gargoyle: Can we use? I say can we use heap to maintain the order?

Rocket Samurai: What do you mean? Anything of our effect we can use? Maybe think about like the return return value of.

Epic Gargoyle: Something like what if we initialize the table exercise at least. But we wouldn't know how many. It's like the thought in my mind at this moment is we initialize the result as as a list and each every time we saw things we do it from the bottom to the top. We can always append an answer level to this results. Level. If we want to do that, then we can write it as... We always put to the append...

Rocket Samurai: You can also do something here because let's say like if you look at the return type for BFS collect... What do you think will be the final return type here finally return value here?

Epic Gargoyle: It'll be... it will be the it will be the none the level of the root it will be the level of the rule so that we can know the total so that we can know the total so...

Rocket Samurai: Yeah yeah so you know the smallest level which is zero and the max level which is the root and then you can easily populate it and you can also do this strategy you explained on line number 43 right because you're doing bottom up you can always add new levels to your list whenever you see that that level doesn't exist.

Epic Gargoyle: It is it is and here then we need to to append here but I think that's it can be it sometimes it is better to reserve all the space needed at the end of the day. So here but since we are not sure how many values in each level so actually I think it's fine to use append yeah if we use append here then it should be...

Rocket Samurai: Okay, so we can do some changes here like if current level is equal to the current level is actually and here we need to have the new he's gonna have to do level for the okay... so yeah, so since we always seen the real we will always see the lower level number first so we can see when we look at the level zero there is actually nothing in the results yet. So it's usually like the current level number equals the length of the result and it's normally we will initialize a new list for the current levels to store all of the values and then at the end of the day return all the values.

Epic Gargoyle: Sounds good. And what are like the different test cases you will test this solution with you don't have to write the test cases you just have to describe them.

Rocket Samurai: First of all, we I will try it out test the empty one empty scenario which is cycling now value as as incurred somewhere input and the second one would be to have a balanced tree I've had a full balanced tree and then a tree with some parents only have one child we have one child and after that, it will be the worst case that the tree looks like looks like a running face.

Epic Gargoyle: What about the case which we discussed right where the leaves were different levels. That is that some of the leaves were at different levels in the sense like...

Rocket Samurai: I think that can be covered by the case that a tree with some parents only have one child. Because for example here if we don't have four, then is no, no true. And we have one child. That is like the scenario three, which makes the thing that we want.

Epic Gargoyle: We want something that to six and seven are at the same level.

Rocket Samurai: Yeah. Okay. And then the one is, like, a different level.

Epic Gargoyle: And, yeah, and there's also like few more you can test, which is single node, that'll be like the smallest tree, right? And then the biggest possible check for like, any memory issues, like some big as possible. So that is something you can ask them. What is the maximum possible size of the tree? Yeah. Okay. Looks good. So, for for the next question. Yeah. So do you want to do behavior? Or do you want to do coding?

Rocket Samurai: I think we can do a coding. Yeah. I think we can do coding. Okay.

Epic Gargoyle: Good. So that's. Okay, so for this one, let's do a copy this example. So let's say you're given... you're given a bunch of meetings, right. And you want to find out the number of room that is required to hold those meetings. So let's say like the meetings in this case is a list. So each meeting is composed of start time and end time. Right? So this is meeting one, this is meeting two, this is meeting three. So we have three meetings, and each of them have start time and end time. And they're not necessarily sorted or anything in this example, it is sorted by start time, but it is not necessarily so. So we want to find out what is the minimum number of meeting rooms. So here, the minimum number of meeting rooms needed is two, because... Because 114 And two, five, they overlap. And if they overlap, then you need at least two meeting rooms to hold them. They're happening at the same time. So yeah, so that is the problem.

Rocket Samurai: I see, I see, I think this is a nice example to show the meeting arrangements, because meetings happened like, I will use this flash to, to represent the star and at the end of the meeting. So meaning sometimes organized like this. So in this example, then, we can see that our beginning, we need one meeting room, but after a while, the second meeting happens, so that we need two, and then three rooms, and then the first meeting ended, then we go back to the two meeting rooms required. And then the second meeting ends as well as this one meeting room. And the first meetings start true. And here is one of their own the meeting finished at zero. So the max requirement for the meeting room, in my example, would be three, right. So in this case, we... Yeah, in this case, I think we can store all the given meetings based on their start time. And then we can work through all the meetings to put all the start and end time in sorted order. In thinking in order is using the example here, that will be the times will become 124579. And when we do this, when we save them, we also save them as a tuple with an indicator to see if it's actually a start of a meeting or the end of a meeting. It's a start with the meeting. We actually need one more meeting room to essentially start before it's actually the end of the meeting. We can connect it one time you This weekend and then available and then after we traverse all the times we have in this ordered list we can have the number of new rooms required in any timestamp and we can pick the maximum.

Epic Gargoyle: So you basically broke this into like events you have start event started, start and then start and an end event and then start and so on. Okay, makes sense. So let's do another problem.

Rocket Samurai: For this one oh yeah, to get that feedback later, but for now, as they are given this array so you have this array and you're given a window size and we want to find output which is max of the first window right. So max the first window is three and then we take max of the second window so that is for the maximum apparently not which is five six and seven and so on. So we want to find the max of each window from left to right and you're given array and the window size.

Epic Gargoyle: Okay let me think about it.

Rocket Samurai: And we'll stop in around like five minutes for feedback.

Epic Gargoyle: Yes, yeah sure. Thinking we can, is the first thought come to my mind is actually we can always maintain a sorted list for our window which here is like 123 And when we move to the container, nothing sorted is here. And so that we can always take the last value is always is always the the largest. And then when we to when we move to the next number, we can do a binary we can we can do a binary search for the value that we should remove and the value that we should insert. Yeah, so this can and we can do the binary search.

Rocket Samurai: But how do you maintain the sorted list?

Epic Gargoyle: Yeah, it's good. If we do the binary search... We can use the log key and use a lot of your time to find the number to be removed or the place to insert but that will related to some extension on the list some size size changing because we need to move on every numbers behind a certain number remove it remove something. So this case should be...

Rocket Samurai: So look like it will become why like the overall time complexity will become NW which is the same as like...

Epic Gargoyle: Actually... Yeah, because we need to resize the terrain... Yeah to maintain like a place for the values before before behind the remove valuing things or value. Thinking there any other ways today okay for us to do waiting time dynamic programming way...

Rocket Samurai: Sure, but you can also you can also do without dynamic programming like two approaches without DP.

Epic Gargoyle: Yeah it's kind of tricky to to to design.

Rocket Samurai: There are like two approaches the two approaches one of them is O(n log w). One of them is O(n) and both of them don't use dynamic programming, just data structures

Epic Gargoyle: Shall we maintain your heat for this? How we remove the value or we remove the value?

Rocket Samurai: That's a good idea. Can you expand on that?

Epic Gargoyle: Yeah, probably we can do this a cycle we can have a hash table to store the values like the TS values and here's the value and the know the value of known in the next give and when we maintain the max heap, the top that the top node... always contains contains a max value and when we do the debate, we can use a hash table to quickly find the node that we should delete. So in every node is can have two attributes one is the value and a one if it's deleted. So in each of the move in each move will remove mark the node actually removed updated as true and insert a new node in your node and keep assessing the top so when you say marking.

Rocket Samurai: Does that mean that node will still stay in the heap but it is just marked as removed?

Epic Gargoyle: Yeah, it will. It will stay in the heap but if it's being see in the top of the heap then we will because when we do the same thing if we see something see and know that you've seen it it will just pop it and see the next the next one the next the next maximum.

Rocket Samurai: Oh I see okay, but it makes sense. So in that way by even market why not just right away remove it?

Epic Gargoyle: Because I think like I think in C++, I know there is like a order I ordered a dictionary that can do the remove the removing directly but in Python I don't think the heap the default heaps structure support the remove directly. Yeah, yeah, we can use the ordered map to do that. That is for sure. We can just directly remove it.

Rocket Samurai: Okay, look good. So let's stop here. So, overall, I think the interview went good. Especially like the last two problems, you had good intuition, I think the second problem you must have seen it before, because you very quickly solved it right? So, whenever if you have seen the, maybe take some time to ask more questions, right? So in this case, you want to because you already know the problem, so you can ask more questions around like, what is the range of the values of any question given to you try to ask more questions in general, right? So like, what is the range of these meeting times? Can they be can there be negative times? And what is considered as overlap? Right? If, if, let's say, end time and start time of something, is the same? Is that considered an overlap? Or is that not considered an overlap? Right? So these questions are important to ask. That is what interviewers look for, because they want to see, are you gathering the requirements? Are you asking the right questions, before you even begin to solve the problem. And especially like, if you know the problem, then try to be a little slower, you don't want to rush quickly, because that will tell the interviewer that you already know the problem. And then that doesn't tell them anything about that will not tell them anything about problem solving skills, we want to slow down a little bit, try to organically move towards... Whenever you know, a problem, try to come up with a naive approach first, and then build on that. That might slow you down and also tell the interviewer that you are organically at least thinking about it. Even if you know the problem, try to be somewhat a little discreet. And then for the first problem, same feedback, like try to ask more questions about like the range of the values of these nodes. And then what is the maximum size of the tree minimum side size of the tree? Can there be duplicate values, stuff like that? And then the other question, other feedback would be, too, so I had, I had to give you some hint. So try to so whenever you feel like you're stuck, then try to think about like a toolkit, right? So for this problem, because it is a binary tree problem, then things like BFS DFS came to your mind. But then when you thought about DFS, you also want to think about in order, post order, and pre order, right? So in this case, post order seems to work because you are collecting the children's you're processing the level for the children and then processing the level of the nodes. And you also want to think a little deeper, right. So whenever you look at the menu, look at this problem, you want to think about like, think in terms of like, if I knew the levels already, then it will be pretty easy problem. And then but how do I compute those levels? Right? If you compute the levels from the top, the leaves will be in different positions. So that should tell you that you don't want to compute it from the top, but you want to compute it from the bottom right. So instead of going top down, you want to bottom up. So yeah, like whenever you're trying to solve problems, just try to think one step more like whenever you're blocked, then see, try to reason about. Yeah, try to think out loud and try to reason about. Think about that next step you can take when you just think about the next lesson, think about like too many at once. And then what happens? Oh, yeah, there's not a one more approach you can use for solving the first problem, which is, let's say like you, you know how to find out the leaves, right? In any given tree, you just use a DFS, and you can add a filter on it. It says, If the node doesn't have any children, that is a leaf. So you can extract all the leaves. And now once you have the leaves, the parent of those leaves are going to be the next set of leaves. Right? But you don't know how to get to the parents. What can you do to have that information? Right? How can you do something to build a map, which tells you who is the parent of who, does that make sense?

Epic Gargoyle: I see but that will need to do the record of like have a HashMap to record everything is there like that?

Rocket Samurai: Yes, we will never HashMap to which says when you do your DFS, right? You will record everything saying that, hey, please, parent is one two, spirit is one, sevens, parent is three, and so on. So when you go about top down, you can build that map. And that map is only using extra size. And it is still better than taking hint from the interviewer right. So you even though you're spending a little bit extra space, it is not the end of the world. You don't necessarily have to come up with the most ideal solution. You just have to come up with a reasonable solution with your own thought process. So that's why this solution might be more intuitive because here you just reach the last set of leaves and then you work backwards. you sort of do a backwards BFS. So you have, let me explain it on line number one, let's say you have your first set of leaves. So first, these are here in a list. And then from that you build your second leaves. And then from secondly, you will build your third leaves, and so on. So this is sort of a sort of a backward DFS. Does that make sense?

Epic Gargoyle: Yep, makes sense.

Rocket Samurai: Yeah, and not all the first set of leaves, you'll get candidate second leaves, because not all the leaves are going to be the next set of leaves, some of them will not because they will still have children. So you want to filter them out and compute the second set of leaves, and then so on. So from candidates second leaves, you will get secondaries and then from second leaves, you'll get candidates second. And then from candidates, secondly, none of them have anything, this is more complex approach. And this might come naturally to some people. So but it's still a good approach to and to come up with interview. Anything else? Yep. So another thing would be to make sure to be more proactive in talking about time and space complexity, right. So whenever they give you, whenever you come up with an approach, B, A naive approach or be optimal approach, always, in the end, include the time and space, right. So you can say, hey, this is how this is going to work. And the time complexity is this because of so and so reason space is this, because of so and so you don't have to wait for the interviewer to ask you for time in space. If you do that on your own, that shows that you're competent. And it also shows that you pay attention to these details in general. So it's always good to mention that whenever you discuss any approach. And then another thing that you can be proactive about is let's say once you do the walkthrough, which you did. So once you do the walkthrough, after writing the code, always try to include additional test cases, right, so you don't have to test them, you just have to tell the interviewer that these are the additional test cases you're considering to test your solution. So that will tell them that you pay attention to testing. And which is important, right? Yeah, that is it. And whenever you're explaining any approach, like recursion, right, so you want to show the tracing like how, how exactly it is going from root to its children to its other children, and then how it is unwinding back and what information is being returned or what information is being passed down. And then the and you can explain that either using the drawing pad, or you using the code editor where you show the difference. If you have any variables, you show the state changes of those variables, then you're doing the tracing.

Epic Gargoyle: I see. Yeah. Probably one more question. Yep. So like, how many key perspectives? Do like Amazon interviewers measure? A candidate like coding communication? And why else? And also what is like my level? For each one of them? Yeah.

Rocket Samurai: Okay. So I think like every most of the fang companies, they have like similar ideology, right? You want to think out loud, you want to be you want to ask good questions, or at least ask questions. So you don't have to worry about asking good questions, but ask questions, which will, which will tell you about the nature of the problem, right? So it's important to ask questions. And it's important to think out loud, show your thought process, right. And then write good code, which you wrote, your code was pretty readable, pretty nice. So that is good. And you also wrote the code quickly. So that is good. That is a good sign. You reason about time and space complexity. You told me about test cases. So just like I said, just be try to be more proactive in those areas. And I think you should be good. Nothing to worry about. Yeah.

Epic Gargoyle: Okay. Okay, yeah, exactly. Thanks for the information and feedback. Questions.

Rocket Samurai: Awesome. Yeah. And whenever you're stuck, just just think about that next step is like, try to be logical, and see what is not working out. So you want to be whenever you look at a problem, you want to see what approaches will work, and what approaches will not work and you want to quickly cycle through them. Right? You can you want to tell the interviewer that hey, I'm thinking about this and maybe this is not going to work. Because of so and so reason, so let me think about something else. And one more thing, which I noticed was you were asking me sort of like, can I use a heap here? So instead of saying, Can I use heap here? Because that is like a question to the interviewer and interview has to answer you. So that is sort of like asking a hint, instead of that you can say, I'm thinking about using a heap here, let me think, where this leads to, right? So you don't want to like ask the interviewer whether a data structure is good to use in that problem, because that is what you are doing in this session, right? You want in there trying to see what data structures you use and why. So I try to avoid that question, asking that question directly to the interviewer. But instead say, hey, I'm thinking to use this and because of so and so. And if they don't like what you're using, anyway, yeah.

Epic Gargoyle: I see I see.

Rocket Samurai: I have to get going but nice to meet you and all the best.

Epic Gargoyle: Yeah, thank you. Thank you very appreciate for this. Okay. bye.