Python Interview with an Amazon engineer

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

Interview Summary

Problem type

Nodes in complete binary tree

Interview question

1) Double an array 2) Return the shortest edge of the squares that fit in the given rectangles 3) Given a complete binary tree, return the count of all the nodes in the tree

Interview Feedback

Feedback about Fluorescent Tortoise (the interviewee)

Advance this person to the next round?

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

As we talked on the session, please pay attention to the following: 1- Ask as much questions as you need. Always ask for an example when anything is unclear. You are doing that already, so just continue doing that. 2- After you ask, make your own example, put numbers on it and see if you understand the problem clearly. Again, you are doing that already. Very good! 3- Go into any interview with the mindset that you are talking to your coworker and you both are solving a problem at work. With that mindset, not only you would be much more relaxed in any interview, you would also be able to speak your mind (which is a HUGE plus in any interview) and interviewers would naturally find it easier to give you hints 4- Always look up for the quickest possible solution to a problem. Quickest solution doesn't always mean that it's the worst solution. Sometimes a perfect solution doesn't even exist (for example, NP complete problems). Communicate that solution to the interviewer and ask them if they want you to implement it or think about a better solution. Sometimes that "quick" solution is all what's needed to pass the interview! 5- Always divide any problem into sub-problems and do them one by one. I would quote Matt Damon in "The Martian" movie: "When you are faced with a huge problem, solve one problem at a time. When you solve enough of them, that's when you get to go home", but in your case, that's when you get to pass the interview. And good luck :)

Feedback about The Inimitable Thunderstorm (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

Extremely Helpful, gave thought provoking questions and helped me understand what I need to do in the interview to better position myself as a strong candidate. Also gave concrete examples of what to do/not to do in the interview.

Interview Transcript

The Inimitable Thunderstorm: Hello.

Fluorescent Tortoise: Hello.

The Inimitable Thunderstorm: How's it going?

Fluorescent Tortoise: Hi. How are you?

The Inimitable Thunderstorm: Yeah, everything's good.

Fluorescent Tortoise: Yep.

The Inimitable Thunderstorm: What time is it at your side? Now if you don't mind me asking?

Fluorescent Tortoise: Around three in the afternoon,

The Inimitable Thunderstorm: Okay. Are you on the west side?

Fluorescent Tortoise: East.

The Inimitable Thunderstorm: Okay. Okay, so before we start, if you don't mind telling me a little bit about like your experience, and what do you want to get out of this session?

Fluorescent Tortoise: Yeah, sure. So, right now I'm interviewing for software engineering, new graduate position at Facebook. Okay. Currently I pass the first technical round. Yeah. And yeah, basically have gotten invited to the follow up technical round, similar to the first round where it I think, one 45 minute session where they ask around one, two questions. Yeah. And yeah, my goal here is to basically to just maximize my chances of moving forward and passing this interview.

The Inimitable Thunderstorm: Okay, that sounds good. So, I see that decision is marked as, basically mentorship. So when I do mentorship, it goes all the way for me. basically solving problems and telling you how I solved it all. Actually, me doing, like almost a mock interview, similar to what you would face in Facebook or any other company can be anywhere in between. So what pace do you like? Or like, which direction you want to go?

Fluorescent Tortoise: I think the former where, I guess you kind of walk me through what I should be doing. I guess I give some of your advice, tips. Okay, whatever.

The Inimitable Thunderstorm: So how about we do this, basically, I'll give you the questions and you start on them and be like you like, hint all of us away. So I will let you try first on something. And then I tell you like, Okay, this is the way it should be done. Or you should have done this differently. Things like that. What do you think? Yeah.

Fluorescent Tortoise: Yeah, I think that's good. And then I was just wondering if I would be able to ask any questions about the process or whatnot.

The Inimitable Thunderstorm: Yeah, you can ask any question. I will leave like few minutes at the end. So you can ask any questions. But yeah, which programming language? Do you want to use?

Fluorescent Tortoise: Python.

The Inimitable Thunderstorm: Okay. Let me just copy. So initial, just to get things going. I would like to start with a very, like, simple questions that basically just to get things rolling? Let me just go get them a second. Yeah, this one.

Fluorescent Tortoise: Okay. Given an integer array, nums of length, and you want to create an array, answer of length two, and we're enter index is equal to nums at index i, and enter index i plus n equals nums at index i, for the range of zero to n, where is always less than n.

The Inimitable Thunderstorm: Do you understand it?

Fluorescent Tortoise: Yeah, still trying to understand.

The Inimitable Thunderstorm: Yeah. So the first hint that I would give you is basically when you get a question, sometimes interviewers intentionally leave the question a little bit vague. Okay. It's not like they forget to give you an example or stuff like that intentionally doing that. And the reason is, they want to see like how much you would actually chase down. One of the red flags that we see on interviews, of people solving a problem that we know that they don't fully understand is one of the next so, the idea here is that I do this personally and I know many people who do that, that we embrace any problem that may be a little bit vague or like has like wordings that would allow to propose ways. So the first thing that you can do is you need to ask questions, and you need to ask for an example. Okay, once your example, you would build your own example and ask the interviewer okay, this is what I understand. And example, Phil, is this correct? And was the interviewer say Yes, right. Okay, you can never solve all the problems.

Fluorescent Tortoise: Okay. Yeah, that's kind of what I did in my first interview, basically what you said and then I also tried to give like I gave a couple of examples like edge cases. And yeah, just just to make sure I kind of understood the problem but yeah, I guess the interviewer didn't it was a little more specific than this wasn't this vague but yeah, definitely good to know.

The Inimitable Thunderstorm: Yep. So what what what does this problem mean? Imagine that you have array a equals 123. We want to array answer equals 123123. So, this is basically what we wanted.

Fluorescent Tortoise: Okay, and the input just array in this example yes.

The Inimitable Thunderstorm: And it would have it will it will have like one or more items so it's never empty or anything like that.

Fluorescent Tortoise: Okay. So, basically the output of the array will be the output of the array will be size 2^N where N is the size of the initial array. Yes. Okay. And it'll basically repeat all the elements so, is it okay if I demonstrate with a few examples. Yes, it makes sense okay. So, my a is this is my a and my answer for B and then this is this a valid example?

The Inimitable Thunderstorm: Yes, exactly.

Fluorescent Tortoise: Okay. 2n and so, you said no empty input is beginning.

The Inimitable Thunderstorm: In which would always have something.

Fluorescent Tortoise: Okay. Are you characters are like if numbers are allowed to be repeated. So can have an instance where it's something like 113444 like that is a valid input?

The Inimitable Thunderstorm: Yes, it can be anything okay.

Fluorescent Tortoise: And is there a sorted order anything or just like you need to just repeat it whatever the order is.

The Inimitable Thunderstorm: No.

Fluorescent Tortoise: Okay. In that case, I think just like a naive solution, I would come up with would basically be we iterate through an array or input array and we basically have an output array where we the look at the first look at each element and output that number into or add that number to our output array. And then we could store that iteration in a while loop conditionals. So we can repeat that process two times to satisfy the to end condition.

The Inimitable Thunderstorm: Okay, that was small, but can you do it in one iteration.

Fluorescent Tortoise: In one iteration?

The Inimitable Thunderstorm: So I will give you a hint when you are given a problem statement. Just today a very close attention to every word in that statement, because sometimes the solution is, because if you, if I select something like this, do you see my selection? Yes. Okay. So if you look at this part, it will tell you how to do it in one iteration.

Fluorescent Tortoise: Okay, so we just create a... So I guess this would be the key conditional so or function, where I guess we would have to initialize our lists that it's has two n elements. And then for each index, we try and index for the output array, I, we update it with the corresponding variable value from our input, but then we have to update it simultaneously. With at index i plus n, since it's two n, so the length of the array is two. And so the n distance from the index, and essentially give it twice.

The Inimitable Thunderstorm: Is yeah, like one of the things that we also do a lot is, we sometimes give a problem, and there would be just a single word in that problem, that means everything. So they will let us say something like, you have a sorted array, you have a complete. So this word sorted, complete stuff like that, it is extremely important. That's the difference between making a solution, that's n squared. And the solutions that's like n log n, just this word. So that's like something that also you need to pay attention because many interviewers intentionally do that. They put that word to make sure that you actually pay attention to details. Got it? So can you implement it?

Fluorescent Tortoise: Yeah, I can, it's okay if I code it out? Output list and I guess we can initialize this by i in range, the size of our input array. And you could just initialize everything to zero dispersion for the sake and then a real function we'll begin here. So for item in array or input array, we basically add at index are actually a better if I use the range function in this case, since we want to be able to go through the index of our output array. So for i in range of array again I output array at index i is equal to input arrays value index i and then output array at index i plus length array is equal to the same value as well. And we would return our output array. So yeah, I believe the time complexity of this problem would be O of n, since we're iterating through the entire input array here. It would be technically n plus m since we have to initialize it here, but in the grand scheme of things, it's so bigger than n.

The Inimitable Thunderstorm: Why did you need to initialize it to zero? Do you need that?

Fluorescent Tortoise: I believe I need it because without this initialization, it would return an index out of bounds error.

The Inimitable Thunderstorm: Okay, um, yeah, you cannot in Python like set the size initially without needing to initial Is it?

Fluorescent Tortoise: I don't believe so.

The Inimitable Thunderstorm: Okay, sounds like yeah, I'm not very proficient in python myself. But yeah.

Fluorescent Tortoise: Yeah, I know in Java, when you declare the size in an array initializer size.

The Inimitable Thunderstorm: You can set that. But I think, for scripting language, this is the case. Okay, so good. Code is clean. This, this problem doesn't need that. But usually at this stage, what you do is basically your solution. And basically trace it with examples, we have a couple of examples above, you can walk through them. But we don't need to do this in because this one is very simple. But usually, like a problem like this, you need to trace and make sure that you could work before you tell the interviewer that you're not. So after you finish implementation, you'd say, Okay, I think I'm done. Just give me a minute I need to distance then you walk through the test cases. And that's all one thing that interviewers don't like, can you test your work or not?

Fluorescent Tortoise: Okay, so I have a question. So I'm doing that. And then I realized there's an error in my code. Do I explicitly articulate that to my interviewer and think, Oh, okay.

The Inimitable Thunderstorm: Yeah. So as interviewers, like I would never expect someone to write codes that are error free. Okay, it is extremely well received, if you also want who found. Because it means like, you will never find the developer no matter what the experience level is, that do I could bug free code, it never happens because we are humans humans make mistakes. And the idea of you being on who finds that mistake because that's a very big plus. Okay, so let's get a problem this one is a little bit harder.

Fluorescent Tortoise: Okay, you're given an array red things are thing was indexed two okay, like tie is equal to length and width, W is equal to it cut off the... Next line. Okay, so in this given example, they're given this two dimensional array for input and our output values three. And this is because the largest squares you can get from the rectangle are length 535 and five are possible square like five and you can get three rectangles. So in this problem, are we basically using rectangles to identify squares?

The Inimitable Thunderstorm: Yeah, so you would be giving, like different rectangles. So okay, what is the square that can fit into rectangles, so each rectangle you will get the biggest square, and then you would return the number of the biggest squares. So if we look at this example, you have the first rectangle item, that is the biggest squares that can fit here is five by five, and then like three and nine. So biggest ones that can fit here is three by three, then five and 12, the biggest five by five, and then 16. And five, that because the five by five, so we have 5355. So biggest square here, size is five. How many of that three? So here's the output that I want is three.

Fluorescent Tortoise: Okay, could you explain this last part just confused. So I understand that we so this is a list of rectangles. So each rectangle we have to find the largest square we can make. So that's kind of bounded by this either side since you're limited by the slight side. So then we return an array, which indicates the largest square for each rectangle.

The Inimitable Thunderstorm: We just returned the number of the biggest squares. So if you have like, let's say that your solution is actually like this. So it is 5356, then you return the biggest query is six. How many sixes Do you have is one, so you just return one. Now 5355. So, so biggest squares five, how many fives you have, you have to see your return. And so on.

Fluorescent Tortoise: Got it. So basically, in when we get to this stage, we want to one find the maximum value and count the number of occurrences of that maximum value and return that as an output. Exactly. Got it. Can I just add a few more examples just to make sure I have a solid understanding of this problem. Okay. So input, we have an input like this. Oh, yeah. Is all are all the inputs having a value for can you have an empty? If that makes sense for like an input like this? And then, like, would this be a valid input are?

The Inimitable Thunderstorm: No, it's always it's always, there are always rectangles.

Fluorescent Tortoise: Okay. And there's the minimum size of a rectangle one by one.

The Inimitable Thunderstorm: Yes. It will not be rectangle. It needs to have like, different length and width. It doesn't really matter. Because yeah, it can't be zero, it needs to be above.

Fluorescent Tortoise: It can't be zero. Okay. So it has to be a minimum of one and they have to have differing lengths. Yeah. And widths, okay.

The Inimitable Thunderstorm: And they're all integers. So there was no floats or stuff like that.

Fluorescent Tortoise: Okay. Kind of think to consider any other edge cases before?

The Inimitable Thunderstorm: Yeah, there would be at least one rectangle. So you don't need to worry about like empty set or anything like that.

Fluorescent Tortoise: Okay. So I guess this is the minimum size input. So one by one. Yeah. And then in that case, I would I guess our output would be something like one. Okay, and then I guess that middle array would be one as well, since it's the 1 squared. Okay. I guess that would, yeah, sorry. I meant to, because I know they can have the same values. Okay, yeah. So I think a, my initial solution would basically involve iterating through our input list of rectangles. And basically, having an output list, where we store the data, and basically checking to see which value is smaller, since that'll determine whether the largest size is square in each rectangle. And we basically add that to our output list. And after we get our output list, we check to see we find the max value of the output list. And then we count the number of occurrences in our output list of that maximum value. And then that's our final output.

The Inimitable Thunderstorm: Yeah, that would work what is the complexity of that solution?

Fluorescent Tortoise: That would be so let me just write down the steps first iterate through input array, then then find max value, that square value and find the... I guess, return that. So these are the main, like, main parts of our function iterating through the array would take O(n) time where n is the number of rectangles and then finding the max value would be I believe if we're using a binary search, it would be something like log n. And then I guess the last part would be find the number of occurrences of the max value which is also the n because we'd have to, in the event that the entire array, or yes, it would be n.

The Inimitable Thunderstorm: Okay, so you're... that sounds fine.

Fluorescent Tortoise: So I guess our overall time complexity would be n.

The Inimitable Thunderstorm: And what is the space complexity?

Fluorescent Tortoise: Space complexity would be. I think n since our... we're just doing the same the number of rectangles in that, that in that output array, which stores the values of each the max value square, yeah. Yeah. Is it okay, if I code that out?

The Inimitable Thunderstorm: Yeah. Let's code it.

Fluorescent Tortoise: Okay. So in our array, we let me initialize an output array. For each rectangle in our input array we output array or got zero is greater than output array one. So basically, we're comparing the length of each rectangle to the width. And if we, if our length is greater than the width, sorry, then we add that to our sorry, I meant to put a rectangle here the length is greater than our width, then we add that to our output array. Zero and otherwise? Well, we know that they have to be different values, so we don't need to check. Or I guess we could say, LS rectangle, one greater than... So if our width is greater than our length, then we add that to our output array. And otherwise, we go in air because they are the same length. Yeah. We can just say false for now. Oh, yeah. This first part will basically go through our input, check to find the smaller value of either the length or width and then add that to our output array, which will store the max square for each rectangle. So then you have to do the second part which finds the next square value. Python has a built in function to do this. Is that okay to use?

The Inimitable Thunderstorm: Yeah.

Fluorescent Tortoise: Okay. So, we just have max is equal to max of output an array. And this will basically store the max value and then we do that final search to return number of integers can just let me create an output variable which is basically a counter. So we can do a simple search. So for i in val in output array, we would it is equal to output array, you return or we increment our output value. And what would be the value of that? Yeah, yeah, so, yeah, just walking through, we can, I guess we can walk through an example. So going through the first example, let me just copy the input and output just to make it easier.

The Inimitable Thunderstorm: Okay, so starting with our input, so the first check, we have are initialized values here. And then for each rectangles, so each pair here, we check to see if the length is greater than the width. And if that's the case, then we add this to our output array list over here. If it's the width that's greater than the length, then we add that value to the list. And if they're equal within this last case, then we return an error because they have to be different values. So we do that for each rectangle. So our output array should look something like this. Array at this point would be 535, and five. So knowing that this is our output array, we find the maximum value, which would be five. And after that, we iterate through our output array one more time, just to see the number of occurrences of the max val. I found a bug right here. So this has be max val, since we're comparing it to the max val, we found here. And then yeah, if it's equal to the max, we update our output counter, which we declared over here. And we return that counter as our final output.

Fluorescent Tortoise: Yeah yeah, that's actually correct. So one more thing, can you make it to work without using extra memory?

The Inimitable Thunderstorm: Okay. So avoid using this is probably our biggest bottleneck. Think. I think one way I was considering going about this is I guess, using just updating the values of the input array. So what we could do is because I think even avoid one of these conditions, so if our width is greater than our length.

Fluorescent Tortoise: I don't believe you don't need to change the input away like I would give you a hint. All what we need to care about is just the biggest number, right? We don't care about the smallest number right? We care we don't we don't. We only care about the appearance of the biggest square right. So if we let in what is the biggest square in each step and maintain account on each step and if If we find the biggest square, we reset, and increment. So basically, we don't need to store everything right. So let me tell you what I mean. So you even have a variable called output right. And you have a variable called max seen, if we put Max seen here we are one. And all what we need to do is in this form, we would do something like check if like correct exists, we would say, free to do is because then wrecked one would say, if... we will, then what we would do is easy. Zero, and output are like plus equal one. And here as well as we would say something greater than next avail, actually, this one is equal to... equal one else the zero then, we would see output, and we do this exact same thing. And that's it. So basically, on each step, we get a bigger site. And we see if it is bigger than max avail, we set max avail to that side. And we set the output to one, if it is equal, we just increment. And by the time the loop is done, the output contains a maximum number. So let's go over here. So you have five and eight. Minimum here, we actually need to have the minimum not the maximum like this. If, yeah, we need to have the minimum side not the maximum side, because it needs to be on the minimum. So five and eight, the minimum is five. So we will see is five bigger than max val, which is negative one. Yes. So Max, Val would be five now and the output the next day, it will nine, three would not go through this. So nothing would happen. Five would go through an equal part. So it would be two and this five would go to the equal parts. This would be three. And then we would help us read it. And then we just like iterated once and we didn't use any extra but the first... Yeah. And didn't need this one as well. Yes, the first solution is just good enough for the interview. This one is like the extra. So this one like good question. We have time let's have one more problem just try to find this one is a little bit hard. Even harder than this one, totally fine if you find it hard to solve I can help you with that. But it is good to give you like a hint of what the harder problem would look like. And this also use what I gave you in the first question is there is one key word in this problem that makes all the delivers a very easy solution for this problem that you can go to it will solve it and it's extremely easy for for like if you know how to deal with a tree you can solve it. But there is like a very optimized one that's based on a single keyword in the problem statement.

The Inimitable Thunderstorm: Got it. Given the root, coin a tree. So would you be able to give an example of a complete binary tree? Or can I, should I? The complete binary tree?

Fluorescent Tortoise: Oh, what's the definition of a complete binary tree?

The Inimitable Thunderstorm: Yeah, just like, can I just draw one out? And then just to make sure it...

Fluorescent Tortoise: There is a drawing mode here that you can actually draw instead of just typing text. You will find Yeah.

The Inimitable Thunderstorm: Can you see this? Okay, so I have just like to the intro fine. Then. So this would be a complete binary tree.

Fluorescent Tortoise: Yeah. Okay. So to give you a good idea what to complete binary tree. So if we look at this one here. This is a full binary tree, but at the same time, it's a complete binary tree. Okay. This one is a complete binary tree. This one here is still a complete binary tree. This one here is still a complete binary tree. But this one is not a complete binary tree. So when like binary tree means all levels are complete. And the last level is either complete. If it's not complete, it is always nodes from the right. So you cannot ever find an audience right and send an empty note and send a note on the left. It needs to always be continuously complete from the left.

The Inimitable Thunderstorm: Okay, so like if, with the current example, right here, this would never occur as an input. Yes. Okay, so I guess that helps a little bit with our search. Because if we don't have to search the right side, we know that there's no....

Fluorescent Tortoise: So if you just, if I, if I didn't say it's a complete binary tree, if it is just a binary tree, what is what would you do in order to count the nodes in this tree?

The Inimitable Thunderstorm: So just a regular binary tree. So that means it could be so this would be about it. But it could be kind of any thing as long as it's at most two, I believe, a depth first search. Okay, good to probably count each and every node.

Fluorescent Tortoise: Yeah, so this is one one more hint I want to give you. So if you want to really impress your interviewer, here's what you do in a poll like this, you would say like, Okay, since it is a binary tree, I can count all nodes using a depth first search. And basically a depth first search should count go over all nodes, it will take an n number of steps, or the complexity of n, and it will solve the problem. And it is very easy to implement the just like a recursive function. But since the problem is stated that this is a complete binary, then there must be a solution that utilizes even if you don't know what the solution is just you saying what I just said. In most cases, it's for the interviewer. And you would say, basically, you would say, Okay, I, I can implement the recursive solution. And then we can think about how to write a better solution. And most interviewers would say, Okay, go ahead with it. Because the idea of you knowing that there is a solution for a problem, and there is a better solution for a problem, but you don't know about it yet. In most cases, that's enough, even if you don't find it. Many people are into them of trying to think about the best solution. And they cannot find it. And they also didn't implement a normal solution, which ends up with the interview ending without you providing any solution. It was a terrible case. Don't ever do that.

The Inimitable Thunderstorm: Got it. So yeah, like I mean, I've definitely encountered like a situation where I didn't know if it was like the best thing to do because I didn't know if it's like the right thing to do to like, say the solution. Like it's there's some times where I know it like in my head and I can like visualize it and draw it maybe but maybe not necessarily implemented code at the time.

Fluorescent Tortoise: Always in any interview, always state to the interviewer. The immediate answer, like if you already have a solution, even if he knows that the solution is not the best thing, just totally be open with the interviewer. Okay, I have, like basically a brute force solution for this problem. I know there must be a better solution, I just didn't think about it yet. Do you want me to implement a brute force? And then leave it to the interviewer to decide. Because it is always better to provide a solution even if it's not the best then not providing anything at all.

The Inimitable Thunderstorm: Correct. What if there's so like in the instance? Say, I know the brute force solution, but not optimized one in terms of implementation? Is that okay? Like, is it okay? If I'm like, I know how to like visually explain this, but I'm not sure how to implement it in code.

Fluorescent Tortoise: In most cases, when you implement the brute force solution, and basically the, the you tell the interviewer, okay, I think I have like maybe a linear approach, I think I would do X and Y and Z, just giving them that idea would be enough. In most cases, they will not ask you to implement it. So because like, here's what we're looking for, when we interview someone we're looking for, for someone who can problem solve. Okay, if you did what I told you, we already proven that, that you provided two different solutions. We want someone who know how to code. And in order to test your coding ability, I don't really care if you implement brute force, or you implement optimized solution, because I'm just testing coding ability right now. There's things that you write clean code, you know how to test for like edge cases, you know, how to write like conditions for verification of input, stuff like that, you know, how to test things like this. So the interview has multiple things that people look at. And if you know those components of the interview, you can basically drive the interview to success because you can provide those different pieces with a state that suits you instead of just providing all of them in one solution. Because providing them all in one solution is not always a straightforward. And that's what you will find in many people who struggle with interview because they know there is like a dynamic programming approach for problems that solves it in like an algorithmic approach, like this problem, for example, is a very simple solution here. If if n, there is another solution, that's log n multiplied by log n. If you bought it from the beginning, thinking about that logarithmic solution, we could have taken the entire hour, and you may not even find it. Yeah, and that's, that's the problems that I see many people make a mistake in interviews, and you need to pay very good attention to this.

The Inimitable Thunderstorm: Yeah, that's definitely good to know.

Fluorescent Tortoise: And don't worry about all those notes like once the interview end, I will summarize them and send them to you in the interview notes.

The Inimitable Thunderstorm: Okay, thank you.

Fluorescent Tortoise: So if you want to, like just, let's think, or one more hint, I also always give to everyone, if you want to have an interview that's basically much more relaxed. Always go into the interview with with a mindset, that it's not an interview, it's just a discussion with someone who could be your future colleague. And both of you are working on a problem together. If you go with that mindset, it would naturally make you speak while you're thinking. And that feeling of basically, ease would transfer to the interviewer. And the interviewer would just be giving you hints without him even noticing that. It would go much more. Yeah. Because at the end of the day, if I'm interviewing someone, I'm interviewing someone that either going to join my team, or like be my colleague op under me, I'm working in, I'm actually a manager, not not an engineer, basically, interviewing someone. I'm interviewing someone who's actually worked for me, or when I was an engineer, I'm interviewing someone who would work for me. So we always ask ourselves one question, can I work with that person or not? So if you go into the interview, and give them an answer to that question in the first 10 15 minutes, it would make them feel much easier to give you hints. It just psychological. They cannot control it.

The Inimitable Thunderstorm: Yeah, I didn't think of it that way. But that'd be mentioned. It definitely makes sense.

Fluorescent Tortoise: So let's think about the problem again, let's look at this tree. This is a complete, how can we calculate? Actually, let's go one step. If we have a full tree, how can we calculate the number of nodes in a full three without actually traversing it?

The Inimitable Thunderstorm: I guess then if we know that it's a full tree, we can just do half of the tree and then multiply it by two, since we know...

Fluorescent Tortoise: We don't even need that, if you know that you have a full tree. All you need to know is the number of nodes is the height, right?

The Inimitable Thunderstorm: Yeah, correct.

Fluorescent Tortoise: If this height is three, so the total number of nodes is two power three minus one, basically to power edge minus one. In this case, it's seven nodes. Because on each level, the number of nodes is multiplying by two, except the first level it is one. That's why we do like a minus one, it's the beginning. So if this is a full three, the number of nodes would be to power h minus one. Okay. So we know that yeah, if we're doing that, this is what we need to do to calculate the number. What if it is not a full tree? Like basically, it is like this? How can we use the fact of that equation to basically calculate how many nodes in that tree?

The Inimitable Thunderstorm: So I guess that equation two to the h minus one, that's our upper bound, that's the most of those will have?

Fluorescent Tortoise: Yes, exactly.

The Inimitable Thunderstorm: The problem. So knowing that we can I guess since we have a complete tree, we know that the lowest it could be is something like this, where you remove these middle nodes. And so this would be our lower bound, where it's like this, this, this and this.

Fluorescent Tortoise: Yeah, this would be basically two, yeah, two, H to power H minus one. One, there is no need to be plus one. So it's basically two, four h minus one, which is four. He was three, so two plus two is four. So like the minimum is minus one to two, or H minus. That's like the range of number of nodes.

The Inimitable Thunderstorm: Right. I guess knowing that, because. And I guess a breadth first search might be better. So we'll be kind of going wide on each level.

Fluorescent Tortoise: But first, you still going to visit all notes. It's still going to be n. Right. So let me give you a quick hint. How would you know that this is a complete tree or not, you need to compare basically, the height on the left to the height on the right. Right? If the heights are equal, then this is a full tree gives the heights are different. It's not a full tree, right? You basically have drills for calculating the number of nodes, it will have like two, it will first calculate the height from the left side and side from the right side. And then we'll have like two if statement. If l height equals other height, just return two to the power of h minus one. If the are different, that's the only thing that's remaining on that function to complete the entire problem. What would you do if the height is different?

The Inimitable Thunderstorm: Different than we don't care about the right side of that tree or sub tree.

Fluorescent Tortoise: Why do you not care about the right side.

The Inimitable Thunderstorm: Because we know that it'll be shorter than the left so there's no point in traversing that right side. Since we are trying to find the deepest level.

Fluorescent Tortoise: We already know the height. So actually, let me tell you like what is the topic in this question? So let's let me just to move on again.

The Inimitable Thunderstorm: So if you basically have this logic, so basically you will calculate as h and r h, okay? This is let's say this is equal x is equal to y, you would have an if statement, if x equal y, return two to the power of h minus one, we already know that, if the are different, what we would do is we would return one plus, we would recursively call the same function and give it node, but left plus node not quite not waiting for... So basically, if the height is different, I would return one plus number of nodes in this subtree plus number of nodes in the subtree. There, it gives a function for the subtree on the left, it will calculate the height from the left, which is two light from the right, which is still it would return to four h minus one, it would return three. So, it would be three plus one plus whatever is his function return, this function would calculate the height from the left, it's two forms it is one, so it would cause the two sub trees again, this one would be zero, this one would be one, so it would be one plus one plus one plus three, so it would be six, which is a correct number. Now, since we are doing a traversing of the tree, each step we are calculating the height, this is log n. And when each step we recursively are calling the subtree, either on the left or on select, which is another log n. So, it's n log n multiplied by log n instead of n, which is much better. Because if you are talking about a tweet that has like a million nodes, instead of taking like million steps, it will basically be like, so a log of a million is like 70? No, it's not just like 20 something. So to be like 600 steps or something like that total instead of a million? Did you understand?

Fluorescent Tortoise: Yeah, so basically, this implementation is recursive, and you will be going through each half of the function...

The Inimitable Thunderstorm: This is a function that takes a node and takes like a Boolean, to see if it goes right or left, and it will go depth either to the right or the left to just calculate the height. This is function one, this one is not recursive. Actually, this one is against it on its own. But it just calculates the height. And the other one is used to calculate the number of nodes in a sub tree, the first call, it will take the root. And if the heights are different, it will take the left subtree and right subtree and call its subtree. Using both of them, what each one of them is a log n and because they're used together, it's log n multiplied by log n.

Fluorescent Tortoise: One question I had about a runtime. So log n times log n, that's significantly better than n even right?

The Inimitable Thunderstorm: Yes. Because log n of a million is I think it's like 22 or something like that. So it would basically be 22. It's like 400. And something. If we're talking about a million that would be like 400. To a million.

Fluorescent Tortoise: Yeah. Which is a huge saving. Yeah. Time complexity.

The Inimitable Thunderstorm: Yeah. Yeah. Okay, I think that's the last question. So like, shoot any questions that you have?

Fluorescent Tortoise: Yeah, so just in general, like, I guess you kind of elaborate on it earlier, but just like, what did they exactly look for in like a follow up? Technically, you like this?

The Inimitable Thunderstorm: So generally speaking, like, I can't speak for Facebook, because I actually work for Amazon. But basically, I made interviews with Facebook before. So basically, like, especially in new grads, like they would be just looking for what I told you in this interview, like basically someone who can problem solve someone who can basically read the problem statement, and basically make sure that they understand the question, someone would ask questions. Like, even if you understand the problem very well, just make sure that you understand it very well. And ask questions. And you already do that, which is really good. So just continue what you are doing and like, because the idea of you giving examples and stuff like this is very, very good. Just continue doing it. And basically be no one expects you to like come up with a perfect solution. That's not really the goal of the interview. There is like much important things that we look at. This is like the last thing that we look at someone who comes with like the perfect complexity and everything. We look at someone who asked a question, someone who can provide as derivatives, someone who understands the trade offs, someone who can really determine if a problem has like a better solution, even if they don't know what that better solution is. Someone who can speak while they are doing their implementation, basically speak about the idea, and what they do. And you're already doing all of that. So it is just very good. So continue doing what you do. And I think if you just continue to do that, you will be totally fine.

Fluorescent Tortoise: Great, thank you. That means a lot.

The Inimitable Thunderstorm: Yeah, I would also summarize all of those points and puts them in interview feedback, so you can read them and make sure that before you go to the interview to make sure that all those points on everything.

Fluorescent Tortoise: Okay, yeah, thank you so much.

The Inimitable Thunderstorm: Okay, any other questions you have?

Fluorescent Tortoise: No, I think that that was like really my main thing like just kind of what to expect what? Highlight on my side to make me a better candidate. Yeah, I'm in the interview.

The Inimitable Thunderstorm: Yeah. Good luck with that.

Fluorescent Tortoise: Yeah. Thank you.

The Inimitable Thunderstorm: Thank you. Take care. Bye.

Fluorescent Tortoise: Bye.