Python Interview with an Amazon engineer

Watch someone solve the sort colors 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

Sort colors

Interview question

1) Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. 2) Given an array of Tree nodes, return the root node.

Interview Feedback

Feedback about The Masked Hedgehog (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

Great job in solving both problems today. Because you solved them with running code in reasonable time, I rate this interview as a pass. For reference, here are the questions: https://leetcode.com/problems/sort-colors/ https://leetcode.com/problems/find-root-of-n-ary-tree/ We discussed the feedback at the end of each question, and below is a brief summary: - good job coming up with various approaches and reasoning through them - you demonstrated good coding style and principles - good job coming up with thorough unit test - make sure to keep track of time for each question and exert a bit of urgency to each problem to ensure you have enough time - can use a bit of review in complexity analysis. I suggest thinking about the edge case in general to come up with the correct big-O Good luck with your interview preparations!

Feedback about Hot Gyro (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

I think my interviewer was very good. He steered me in the right direction. Once I had solved the problem with one particular approach, he also explained different approaches to solve the problem. His demeanor was friendly, positive, pleasant and helpful. Thank you!

Interview Transcript

The Masked Hedgehog: Hey, good afternoon.

Hot Gyro: Good afternoon. How are you?

The Masked Hedgehog: I'm good. Thank you. How's it going?

Hot Gyro: It's going well, it's pretty sunny today, for me. That sounds good. So we have an hour together for a coding session. Is that correct?

The Masked Hedgehog: That is correct. Yes. Yes.

Hot Gyro: So I've got a couple of questions prepared. But I'd like to ask you do you prefer a harder problem or an easier problem?

The Masked Hedgehog: I think, let's go with an easier problem.

Hot Gyro: Okay, sounds good. So let's start with that. And then if you've seen the problem, or you don't like the problem, just let me know, I will switch it up. And depending on how we do, we'll just keep tweaking the question, adjusting to the difficulty of the question for the next one.

The Masked Hedgehog: Okay.

Hot Gyro: With that, let's get started. Can you pick the language that you will be using for this?

The Masked Hedgehog: Sure thing, I'll use Python3, okay.

Hot Gyro: Good, all right. So, let me put the question up here. Here we go. Okay.

The Masked Hedgehog: Okay. So, I will read the question loudly, is that okay?

Hot Gyro: Yeah, okay.

The Masked Hedgehog: So, given an array with n objects, colored red, white, or blue - sort them in place, so that objects of the same color are at the center with the colors in the order red, white, and blue. Okay. Here we will use the integers 0 1 2 to represent red, white, and blue respectively. Note you are not supposed to use library sort function for this problem. So, if the input is like this, suppose to get 0 0 1 1 2 2. Okay, cool. I see. Okay, I think I understand the problem. I definitely understand the problem. So, I think I'll, I'll just start talking about the problem, just ask some questions, thinking out loud, essentially, the array is given... it has only three kinds of elements, either you have a zero or a one or a two. My job is to do an in-place sort of the array, that means that means I cannot use an extra data structure like I cannot use extra space other than other than what is given to me which is an array. So, that means I can modify the input array that is given to me in place, which is what the goal is, sorting in place. Another thing is that I cannot use any library functions. So basically, it's an algorithm from first principles trying to trying to further that is given to me in place, okay. So, I am thinking of various sorting algorithms in my mind at this point. I think some of the algorithms that do in place sorting is Insertion Sort, Bubble sort, those kinds of algorithms, the complexity is O(n^2). Trying to think of quicksort... Actually, quicksort is a little bit heavy in my head. So, I, but I think quicksort also does it in place, definitely does it in place, the input has to be randomly sorted to start with otherwise if it is already sorted, the complexity could be O(n^2), merge sort is a recursive algorithm. Better implemented recursively actually. Does it do in place sorting? Probably not, I think... Maybe it does, it can be implemented to do in place sorting. So I'm trying to think what is the right way to do this. So obviously, the runtime is should be as low as possible. So basically, trying to rule out Insertion sort and Bubble sort because they will be O(n^2) nested loop algorithms. I'm trying to think if I should use Quicksort. Or try to build an implementation for in place Merge sort? Or if there's anything else I can do. Yeah, I think at this point, probably Quicksort is the... or Merge sort are the best algorithms. But unfortunately quicksort I'm hazy on quicksort.Mergesort, I think I remember the algorithm. But I think I'm a bit rusty on that, too.

Hot Gyro: Yeah, yeah, let's pause for a little bit here. That was actually pretty good in terms of coming up with so many different sorting algorithms here. And then sort of comparing all of them the pros and cons of each. And that was good to kind of see that discussion there. It was more one sided, but it was good to see that survey of algorithms. However, one thing I wanted to point out there is that this problem is a little bit different than what you're envisioning. I see that you're seeing a sorting question here. In many ways, that's true, we are trying to sort some values in the list. But keep in mind that there are only three types of data. Right? Everything that you've talked about so far, applies to an array of many values, right? That's a sorting algorithm. Here, if we have three values, and you know that there's only three values at most, right? Can you think of something much easier than sorting algorithm?

The Masked Hedgehog: I see. I see. That's a good hint. So I'm trying to think, think of something easier than a sorting algorithm, okay. Something isn't a sorting algorithm. Um, so what I was thinking in my head is, you know, something like swapping, if as soon as I see an element, I swap it like, see, I start with a two here, and then I see a two, so it has to go to the end. So I swap it with a zero, and then I get a zero, and then I zero on index one, then I let it remain there, then I get a two. But what do I do with that two? Because I saw, if I swap it, it's not gonna help me much, even though I can do it as a no op, sort of a step in my algorithm. But what do I do with the one that comes after two after that? So I think I'm not quite getting the algorithm in my head, it has... I have not quite been able to wrap my head around this yet.

Hot Gyro: Okay. That's fair. What you've been describing so far with the swapping and then seeing the zeros to do, that's actually a very feasible solution. Obviously, it requires a decision tree, like what do you do with one? What happens when you do a swap? Right? And then you see a two later on, what do you do? These are actually questions that you need to answer in order to solve the problem this particular way, which is moving the two to the end, moving the zeros to the end and then leaving the ones in the middle. That's one approach that you can explore further if you want. Another approach for problems like this is that let's assume that you can visit the array in two passes, right? Let's say in your first pass, you are collecting some statistics. And then in the second pass, you are using these statistics to actually sort the array. You think about it like that, in that sort of template, can you think of a way or an implementation to actually solve this problem?

The Masked Hedgehog: Right. So I think, I think, so when you said two passes... Okay. So in the first pass, I'm supposed to be collecting some information about the input, which I can use in my second pass to actually sorted the way the problem requires. So what kind of two pass solution I can think of? So let's say you get an index of all the places where two occurs, will that help me at all? I think it can it can I see, I see, I think it can. So what I can do is I can do a count, I can say okay, two appears two times zero appears two times one appears one times. So essentially just merge three lists, zero, multiplied by two plus one multiplied by two and two multiplied by two. So that would be the answer.

Hot Gyro: Yeah, that sounds like a very feasible solution as well, before you start coding, what would be the time complexity and space complexity of this algorithm?

The Masked Hedgehog: Right, the time complexity, so in my first pass, I iterate over it, so that's O(n) and then I don't need a second pass, really on the array. But since I created my data structure, which is a dictionary, I'm thinking or a counter. So I need to iterate over it. And so I need to iterate over it. So that would require an iteration. So O(n), and it would be upper bound, so upper bound is O(n). And so the that is the time complexity, I have the upper bound is O(n). And now space complexity... Coming to space complexity, now. Actually, the problem set in place, but I'm using extra space here, the space complexity would be upper bound for space complexity would be O(n) and because essentially, I'll be creating a dictionary saying, hey, zero appears five times or one appears seven times and two appears nine times. So that is one thing where I'll be using space, upper bounded by O(n), but there is another place that I'm using, where I'm creating using extra space, which is when I create my list, let's say when I say zero appears five times. So I create a list with all zeros, then I create a list with all ones and all twos, and then I merge it together. So that is a new list that I'm creating. So I'm creating a sub list. And then I'm combining them. So I think the O(n) and O(n) and the time and space complexity. That is what I think.

Hot Gyro: Yep, yep, I follow you on the assessment there. Based on what you are implementing I agree with you, it's linear time and space. However, on the space side, I think we can tweak a little bit to make it better. First thing I'll point out is that you said you're going to use a dictionary to keep track of the count. But from what I hear from you, you're keeping track of zero, one, and two, so there's just three entries. And no matter how long the input is, it's just three entries here, right? So that's one quick observation there. The other is that, you said you are creating the list and then merge them together? What if you don't create the list at all? Like, what if you just have to count, right? Let's say there's two ones, two zeros, and two twos. And you just have three numbers by twos, twos and two. Are you able to recreate the sorted list with just these numbers, instead of creating a list and then merging them?

The Masked Hedgehog: Yes, yes. In fact, I can just modify my original list. Once I have a count, I can go over the... I can just say, hey, put all zeros first these many zeros and put these many ones and put these many twos in the original list itself. So I don't even have to create new lists and later on merge them. Yeah, I can use variables to do the count. We don't need a dictionary.

Hot Gyro: Right. Sounds good. So now with all these optimizations, what would be the final space complexity here?

The Masked Hedgehog: The final space complexity, so I'm using three extra variables. So that's constant because we can we could say, it's three, right? So O(3). So I think that's constant. So space complexity would be constant. Time complexity would be first pass, I need to do a count. Okay. And then in second pass, I'm going to iterate over the three variables and modify those units. So I think, O(n), the time complexity would be O(n).

Hot Gyro: Yep, that's good. So I agree with you, I think time complexity O(n), we cannot do better than that. Space wise is constant. So that's good. So with that, I think we can get started coding this up. And then test it out to see if it works?

The Masked Hedgehog: Sure, sure. All right. So I will start writing my code saying def sort array, let's say this, and this will be my array. And then what I'll do is I need to do a count. So I'm trying to think if I can use map here, no, I don't have to. So zeros... I'm trying to avoid writing three loops, basically. Or, what I'm thinking is, now I have these counts and three different variables. How do I use it to populate the array? And I'm also trying not to create an array and assign it like slice the original and assign a new array to that slice. Because that would that would require more space. So what I can do is... I don't want to create another variable. I can define a function, maybe? What would I do here is... I think I'm making it more complicated than it needs to be.

Hot Gyro: Yeah, I don't need to worry about it. The red squiggles will go away when you write something inside a for loop.

The Masked Hedgehog: I see, I sse. So, now, what I am saying is thinking is... I think this looks... perhaps there's a problem but let's see this is no longer needed... Okay, so yeah, I think it is giving this, but let's see...

Hot Gyro: Hello, can you hear me? Yeah I don't think I can hear you at this point, if you can hear me, can you type something? Okay okay, I'm having a little bit of audio issue here. Let me rejoin. Hello? Hello? Okay, can you dial in? There, in the bottom right corner...

The Masked Hedgehog: Hi, can you hear me?

Hot Gyro: Yep, I can hear you now. Perfect.

The Masked Hedgehog: Okay. Good.

Hot Gyro: Glad that we can recover from that audio problem there. I like to call it audiomagaden. Anyways, I think we're testing. And we saw an issue with your second test case, which is good, by the way. Your test case is able to reveal a bug. So let's try to debug it. And then, and I think you're very close.

The Masked Hedgehog: Sure. So actually, the bug is because, you know, if I don't have any zeros, then this is zero. The loop doesn't have any iterations, and i doesn't get initialized. So then when I try to add an i, which is not initialized, so it throws an error there. So that's the reason for the bug. I am trying to think if there is a better way to do this so that I can avoid all these issues.

Hot Gyro: No, I think what you have is pretty good, right? If var is zero, right? Then maybe we can return something before the for loop.

The Masked Hedgehog: I see, just check if var is zero. Okay. Yeah, I can try that. Yeah. So let's see if this gets something. Okay, the more interesting case would be an empty list. And maybe I can comment these ones out. Okay, so I got an empty array, which is nice. If I get a zero there, if I put a zero, let's see. Oh, well, I just run all four of these. This shouldn't take much time. Be quick. 012. Okay. So they seem to have worked. Okay. Now, what else? What else is a good test case for this. So mult empty, single values, multiple repeated values, mixed values of just a... Yeah, there's another one that I'm missing here. Were, let's say, I just have a zero and a two in here, or just this like this. There's no one. So it should just work. Okay, this should also work. And let's see if I give an input in a different order. So let's say 2 0 2 2 like this. This is commented out. Okay. Yeah, this seems to work so far. Yeah.

Hot Gyro: All right. Yeah, let's end there for this question. Because I want to ask you a second question. I will, I'll give you some feedback on this problem, and then we can quickly move on to the second problem, how's that?

The Masked Hedgehog: Sure. Sure. Sounds good. Thank you.

Hot Gyro: All right. So I think that this problem is sort of considered on the easier side. But it was great that we had some discussions in the beginning, various approaches. One thing I really liked is that you are able to take feedback right away on directions that I'm trying to steer you towards. Mainly that there's no sorting algorithm necessarily for this problem. You can make use of the fact that there's just three values, you can use some sort of count, you quickly came up with an approach similar to that and then we are able to also optimize that. And just overall with that discussion, I see that you're able to make progress, as I give you a little bit of hints here and there. And that's a good sign, because you're able to kind of move to the right direction, right? And then that's perfectly normal. And then, and I really liked that when you're writing the code, you are very quick in identifying or computing the count. And the next part is you recognize that you don't want to repeat writing the same code three times. So you put it into a refactoring separate function that does that job once, which is good, because you're using the DRY principle, and I don't see a lot of people do that, by the way. So that is good in terms of the coding style. And obviously, there was a bug and your testing was, again, great in order so that it was able to reveal that bug. And you're able to take a quick hint to just solve it, fix it, I say. So that was good. Unit testing is very thorough, because there are so many cases, if I didn't stop you, you might be continuing with that. That's good. But sometimes it can be a little bit bad in the sense that you need to manage your time as well. Because in a real interview, you might be expected to solve two problems within a certain amount of time. So you really need to look at the time and say, Okay, how much time do I have left for this problem there? Right? So, but besides that, the thoroughness was there. The unit testing coverage was there, which is great. We talked about the complexity analysis there. So with this question, I think you're able to take some hints, take some feedback, then demonstrate good coding style, you get the right answer, good testing. So I think there's nothing major improvements needed here at all, except that maybe a little bit more on the time management there just to be aware of how much time you have left, and then just be a little bit quicker on the unit testing, just don't take your time, but like go a little faster there. But other than that, I think within half an hour solve this problem is reasonable. Again, also depends on the company, sometimes they expect you to do in 20 minutes. But I think 20 to 30 would be reasonable, you spend a little more than there will be a bit of a risk as in terms of the timing of solving this problem. Any questions for me before we move on to the next problem?

The Masked Hedgehog: No, no, no other questions. Thank you for the detailed feedback. That was very helpful.

Hot Gyro: Okay, great. So let me paste the second question down below in line 50. And then we can get started. So this one I need to draw a little bit of a picture here for you. But go ahead and read it.

The Masked Hedgehog: Okay, so I'll start by reading the problem aloud. Okay.

Hot Gyro: Yeah, sure.

The Masked Hedgehog: Okay, so given all the nodes of an n-ary tree as an array, node tree, array of type node, okay, where each node has a unique value, okay. So let's say I have this, this is a tree and an array is given containing all the nodes. Find and return the root of the n-ary tree. Okay. Return node one okay, because one is the root node got it. So now, this is a class node. Okay. So array of objects of type instance instance objects of type class. Okay. So basically in itself all in similar... That is children equally children. If children is not none else, it's an empty array. Okay, if it is none, then it's a empty array. As such children is a... Hello, can you hear me?

Hot Gyro: Yeah, I can hear you perfectly.

The Masked Hedgehog: Yeah, okay. Okay. Okay. Thanks. So, children is an array then. Right? It's an array.

Hot Gyro: Yeah, children is a list of nodes. So, yeah, it's an array. Yeah.

The Masked Hedgehog: N-ary tree, correct. Correct. So now... Essentially, the class node and then find root? So tree and tree? So I'm supposed to return an object of type node. And I'm given a list of objects, which are instance objects of type node. Right? That's what I'm given?

Hot Gyro: Yeah. You are given an array of nodes.

The Masked Hedgehog: Array of nodes, okay. Okay, so if I'm giving an array of nodes, oh and each node has some children, okay, I see I see. So basically, basically, if I'm given one, then my object one would have would have the self dot value equal to one, and children will be object representing two, three, and four. And then my, so that's my, let's say, first node, and then I'll have second. So my object two would have val equally to two and children, five, and six, and three would have three and empty, four would have four and empty. So that's how it will be. So and I'm given an object, an array of node object 1 2 3 4 5 6. So and then five and six, we'll have five, empty six empty like that. So that's how it is, if I'm understanding correctly, and then if I'm given this array of objects, I have to figure out my child node, okay. Now, the thing to notice here is that I could... I can identify the leaf node very easily, because the leaf nodes will have no children. So that is easy to identify. Now, if I have... and so the nodes, okay, the nodes have children, we cannot infer the children. So if I have a five I can tell it's not. It could be a root node if it's only a tree with one node. So it could be a root node and a leaf node at the same time. Okay, so how do I do this? So it's... okay, let me see. So five, and six. If I get a three? So let's say I have... I start with a five, find root. Okay. So five, I can look at the val, there are no children. Okay. Oh, but since I know the length of the list, I can tell that it has how many nodes it has. So if it has more than one, then obviously, the node I'm looking at... If it is if it has no children, it's a leaf node, so I can ignore that. Then I let's say look at... then I look at six, six can... Same thing with six. Same thing with three and fours, I can eliminate, let's say `5 6 3 4, I know a way to eliminate them. Now, then I'm limited, then I have... I have two and one remaining. So two... So basically the root node is is the node that is not the children of any node. So that is the, that is what I'm fine trying to find. Amongst these lists, I have to find a node which is not a child of any node. So what is this, this is sort of a breadth first search type of question, if I'm getting this correctly, so basically, it is like a graph, I have an adjacency list where final two has children five and six. But I don't five to two, I have to check if two is a child of any node. And so, okay, so I start with two, let's say, and I say five and six are children. So I ignore five and six. And then I go to three, three doesn't have, four doesn't have. But I go to one. So essentially, I start, so let's say I start with a node, and I look at the children. And whatever children, if I find children, I store that value. I store the value of the children in a list, let's say, and then as I'm iterating... And so I say, okay, I got a two, I'm iterating on my master list. So I say, okay, two, what children do you have, so I have three and four. So three and four cannot be the root nodes. So I put it in that data structure. So then, but two could be two could be. So then I go to another one, I say I come across, three, I come across, three, and four, three, and four, cannot be three and four, don't have children. Three and four, don't have children. So nothing to do there. One, then I get five and six, nothing to do there, then I get one. So two... So now I can add... So five, and six are already there in my list which are not root nodes, then I can add two, then I can add three and four. So I have added two, three, and four. And then I get a one... to one is not there. So now... So then my trimmed list, then I need to iterate again, it over is one and three and four. No, just one because three and four are already excluded. So I think that's how I have to do this. It's like I iterate and if something... okay, if something is a children, yeah... Okay, so my algorithm is like this, I start with all the nodes, then I take a node, and I find out what its children are I get the values. Now, I take the children and put it in a data structure. So my first iteration will essentially... I'll iterate over all of them, and I'll try to figure out all the children and then in my second, and then what I have to do is from my original list, I need to remove all the elements that have... whose values appear in the list of child nodes. And then I continue doing this till I'm only left with... till I'm only left with one node in my main list that I'm iterating over and then I return the value of that so that is my root node, because it has no children, okay.

Hot Gyro: So, a couple clarifications here. The function that you need to write, returns the node not the value, but the node.

The Masked Hedgehog: I see I see.

Hot Gyro: The other thing is, I follow your algorithm here, but the last part where you are iterating on a second pass to remove the node that is in your data structure. I want to know why that step is necessary? That you have to, like remove something from the input list. Are you still able to get the answer if you do not remove?

The Masked Hedgehog: I think... Yeah, you're right, you're right. Because I can just do a sort of set subtraction, convert original list into a set, the children list into a set, do a subtraction, and that will give me the nodes or a node that are not children. And that would be my root node at that point.

Hot Gyro: Okay, okay. Sure. Yeah, you can definitely do a set subtraction there, or a set difference there. Okay, yeah, so there's different ways of doing it. I think we have the time to close this up quickly. And I can help you with running the unit tests or like setting up the trees test it, but if you can start with writing the actual main function, that would be great.

The Masked Hedgehog: Sure, sure. So, oh find root you've already given me the prototype okay. So find root. Oh, here I have this and then what do I have to do is for node in tree... Okay, what was I finding? I was trying to identify nodes which are children. So, okay, so if node dot... Okay, so, what first I have to do child nodes... have to do this, this is this. Now... So what I did here is for node in three... Yeah, so else it will be node dot children. Oh, it will be none. Okay, it will be if children is not none then children, okay, it's an empty list, okay? It will not be none. Okay, got it. So then... So, five, let's say I got a five and six, it would be empty, then I got a two, to add five and six, then I got three will be empty five I got, two it will be empty. So that's how it'll be done. So I got my child nodes, all my child nodes are there. And once I have that, so now we are coming to what you were hinting me at the beginning you were saying that... How do I, so now in one pass, I found all my child nodes. Now how do I know my root node because my root node is now still... So my tree has one extra node and my child nodes has all other child nodes. So and what I was saying is I can do a set difference. I think you had a different idea. But I just go with that what I was thinking perhaps it would come to me later, set child nodes like this, return. I think this should do it. Oh, if I were to do find root, let's say with a list of nodes. So okay, how do I do that? Extra list? Okay, this can get complicated. So yeah.

Hot Gyro: Don't worry about the time, we'll take a little bit longer if necessary, just focus on the coding and the worry about the time.

The Masked Hedgehog: Sure, thank you. So I have you new node, two, which was... So then a new node value is the children are five and none. So that is one, and then this... so let me copy, paste. So let's say I start with this trivial case. So I just use the sub three like to add five. And I am hoping I will get two returned. Let's see. Invalid syntax, right. New node. I think I made a problem in the constructor somewhere. What is the problem? Did I miss this? Yeah? No.

Hot Gyro: Do you need new in Python when you create new object?

The Masked Hedgehog: Yeah. You're right. Sorry. I'm sorry. Yeah. New is in Java. This should be easier to fix. Oh, did I create a list? Oh, oh.

Hot Gyro: Yeah, I think the self there might be throwing you off a little bit. I think this is not part of a class. Right? The find root, we need to self? I'm not too sure what the syntax? So I think we can remove that, oh, yeah. Oh, that's bad. I'm gonna leave it there. What if we just removed this whole kind of Python3 syntax here? And just how would that work? This is...

The Masked Hedgehog: I think this was this was good. I mean, here, we can just print the value, because I think this is the object. Okay. An object with value two.

Hot Gyro: Okay. Oh, yeah. I think the square brackets here. Maybe? Oh, yeah. I see. I see why you. Yeah, because it's all, let me see. Oh, I know what's going on. You. Okay, I see what's going on. Let's break this into parts. I think what's happening is that you created a tree. Right? And I think the tree is 2 5 6. Like that's the tree that you created. Right? Let me just take it out. I take it out there. And we're not passing all the notes into the input as is happening. So this is the tree. Let's just call this the root. Right. I think I have everything maybe missing bracket? Okay, so this is the what is this? How come? We have another bracket here. I see. Okay, I think this is going to be a little bit hard to create. Let me... Yeah, I said I was going to create this, I forgot, I didn't do it. Sorry. I'm going to recreate the tree. Now with the two, five, and six, and then we can do this. So I say node five is five. My node six is node six, right? And then node two. Let's put that in the bottom as the root. And then let's just say node five. So now we're going to pass in the input as an array. I'm going to say node six first, node five, and node two. And we pass in a, that's all we're passing in right?

The Masked Hedgehog: Okay.

Hot Gyro: A is there array where all these nodes form this n-ary tree, right?

The Masked Hedgehog: Correct. Correct. Yeah.

Hot Gyro: So let's see how this goes. Let's run it. I hope this runs.

The Masked Hedgehog: So we need to know we need node two here, the variable.

Hot Gyro: Oh, oh, yeah. Should be six like that. I meant to put six. Oh, sorry. Yeah, I meant to put roots there.

The Masked Hedgehog: Okay, cool. Cool. Yeah.

Hot Gyro: Now, now we should get...?

The Masked Hedgehog: We can delete self.

Hot Gyro: Okay, okay. Yeah. Sounds good. Right. All right. Let's do this. Oh...

The Masked Hedgehog: It takes one, two, three positional.

Hot Gyro: Which is that?

The Masked Hedgehog: Oh, we need node five and none. Oh, it should be an array. Like the root node five and six should be an array.

Hot Gyro: Why? Oh? Oh. Oh, yeah. Oh, that's how you call it. Okay. Okay.

The Masked Hedgehog: So now? Yeah, now we can print. We can do a dot val.

Hot Gyro: Okay, okay. Yeah, go ahead and do that. Oh, are you talking about writing the 78? Is that the problem?

The Masked Hedgehog: I was talking about line 87. Actually, I was thinking if I did this...

Hot Gyro: Yeah. Yeah.

The Masked Hedgehog: No, did I return a set?

Hot Gyro: Yeah, it's returning a set. So maybe get 0? I don't know, how do you get the first item of... maybe like, just let me do this. Let me do this. I think I got an idea. I like that. And then down.

The Masked Hedgehog: Right, right. Yes, exactly. Yeah. Oh, sets are unordered. So we can't do that. We can't index them.

Hot Gyro: So what do we do in Python? For sets?

The Masked Hedgehog: I think it's a set of one elements. I think we can do pop, pop should work I think pop or get...

Hot Gyro: Pop and then dot val. All right. Yeah, let's see the I can see the IntelliJ or like the... Good. So we did get what we want there. Let me just quickly do the test of the original tree that I had. I had node one. We have two there. Let's do three and four. And then just kind of put it together. What do we do, so we have node one. Actually, I'll just put one here again. And then there will be node two, three and four. Node two, three, four. And then I'll remove the one on the top there. Will that be all? Yeah, that's it right? Just before...

The Masked Hedgehog: Yes.

Hot Gyro: And we just pass in our input here. We need... actually two would be, this will be moved too. So it will be node two and maybe node one in the middle node four, node three. This looks good to me. I don't know why there's some squiggles in there. I think we're good. So if I run this, I should get one. Right?

The Masked Hedgehog: Correct.

Hot Gyro: Let's do it. Great. Yeah, I think this program works. That's good, if you can tell me the complexity of this algorithm, then we can wrap it up? S

The Masked Hedgehog: ure, sure. The complexity of this algorithm. So, starting with runtime complexity, I am iterating over the tree and my tree is an array. So for each node, I am checking the children. So... Oh no, I am for for each node, I am iterating over the children. So, what is the complexity here? So my outer loop, so if my tree has n nodes, my outer loop runs n times, and then my inner loop runs for the number of children of each node. So, yeah, I am not sure how to describe the complexity of the inner loop because the inner loop will sometimes run if the node has children. And it sometimes won't run if the node has no children. So...

Hot Gyro: Yeah, it can can be a little confusing there, especially with a double for loop itself O(n^2). But then, like you said, sometimes there is a child node there. The best way to think about this is to ask yourself, how many times will a node be visited ever, right? You know that there's an input array, which goes through each node once. So every node will be visited at least once. And every node is a child of something. So it will be visited just once as a child. So the upper bound here is every node will be visited twice, at most. And so because of that, it's still a linear time runtime because node traversal is just O(2n). Like, that would be a linear time. Right. And, and the space here, you can tell me what is the space?

The Masked Hedgehog: Yeah, the space would be... I'm using extra space, because... so tree is already known to me. Child nodes is n minus one. So I'm creating a set there. So since I'm creating a set, my upper bound is O(n), because I'm creating a set. Right? But yeah, so yeah, upper bound is O(n) extra space.

Hot Gyro: That's right. Yep, that's right. So this is a linear time linear space implementation, which is fair. But there is actually an even better solution. And I'm gonna explain that, I don't think we have time to code it. And the optimal solution, or a slightly better solution is a constant space solution. Now, sometimes things don't come for free, right, if you want to save on space, you have to spend a little bit more on the on the time. So for this problem, we're going to spend a little bit more on the time, however, it's still going to be linear time, right? So asymptotically is the same, but we can actually we remove the second comparison or any kind of data structure to do it. And the way to do that is to make use of another characteristic of this problem, which is that every node has a unique value, right? It turns out to be very important here. So what what we would do here is that we would sum up all the values in the first path. Right? So 1 + 2 + 3, know that. Now as we as we iterate through this loop to sum up the values, we are also going through the children of every note and subtracting the sum from those values, right? So what happens is, if I visit one, I'm going to sum up the value one into my variable sum. But then at the same time, I'm going to do subtract two, three and four from the sum. And then when you go to two, when you go to two, you add the two back, but then you subtracting five and six. But then when you visit the five and six, you added all that right? And so what happens is, after all that, you will end up with the value one as your final sum, because one doesn't have a child, right? And so what happens is, in your next pass, you just compare which node has the value one, when that node has to value one, you know, that's the extra node and then you return that node. So that way you're using one variable to track the sum. And you don't need to use any kind of extra data structure to track to tell the difference between a root node versus a non root node. So that that is more of a full question. Once you get this problem, which you did, if we had time, I would be kind of asking you this follow up problem to see if you can further optimize the space. Sometimes, you know interviewer may not ask that because this is a little bit of a trick question. Not quite algorithm type of thing. But I just want to explain that to you. Since you're got the first part. Just want to give you the second part as well. And just overall feedback about this question here. I really like our kind of discussion, I really like the way you problem solve this problem coming up with different strategies, identifying a data structure, even without knowing what it is, you know that that data structure will be able to help you distinguish between the root and a non root node and be able to implement a solution that is linear time and space. One could use that map as well, instead of set difference. But again, same space complexity, so it doesn't really matter which implementation it is, as long as it works. So at the end, you're able solver within reasonable time, 25 minutes here, I know I had to write a little bit of the unit test there. But that's just because we don't have enough time. But if you were to do it, I'm sure you can do that, too. So that's again, no, nothing, nothing negative that stood out to me in this problem, I think you're able to reason your way through able to identify the right data structure to solve this problem in a reasonable amount of time. And the good part about this is you're able to express your thoughts along the way. So that was good.

The Masked Hedgehog: Thank you, thank you for your detailed feedback. This is very helpful. I just had one last question. So instead of the set, you said, I can use a map there?

Hot Gyro: Right, dictionary Yeah. In Python. Yeah.

The Masked Hedgehog: Yeah, dictionary in Python. I'm trying to think, how do... what would be my approach if I used a dictionary?

Hot Gyro: Yep. So there's also a couple ways to do it using a dictionary, the simplest way would be you traverse the input, right? And every time you see a node, all you do is you put the children of each node into the dictionary by... this dictionary keeps capturing all the child. And so when you when do go through the input array, and storing all the children in there, that dictionary will have all the nodes except the root node, right? And then you do a second pass and check does this node exists in the dictionary or not? If it's not, then you know that the root note. So the dictionary is for you to track, whether it's a child node is to help you track all the child nodes.

The Masked Hedgehog: I see, I see... if so child nodes are added to the dictionary. And in a second pass, I can check if I can then filter out a node which is not in the dictionary. So that is my root node.

Hot Gyro: Again, the subtlety here is that every node has a different value. So that's why you're able to do that, right? If two nodes have the same value, then you just failed. Maybe you have to store the address so that it gets a little complicated, but it only works because of this. So and then once you see that, that oh, you can compare nodes like that, then you can you can figure out, maybe you don't even need that data structure all together, right, using the sum as a way to replace this dictionary. And kind, the first solution kind of leads to a more optimized solution. But for the most part, this solution, a linear space solution will suffice as well.

The Masked Hedgehog: Cool, cool. Cool. Thank you. Yeah, this is great. Yeah. Thank you for your feedback. Was very nice and very helpful. Yeah.

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

The Masked Hedgehog: Yeah, you too. And thank you for your time. I really appreciate you taking the time to interview me. This was very helpful for me. Thank you again.

Hot Gyro: Yep. Yep.

The Masked Hedgehog: Yeah, have a nice day. Yep. Bye.

Hot Gyro: Bye.