The Inimitable Thunderstorm, an Amazon engineer, interviewed Fluorescent Tortoise in Python
Nodes in complete binary tree
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
Feedback about Fluorescent Tortoise (the interviewee)
Advance this person to the next round?
How were their technical skills?
How was their problem solving ability?
What about their communication ability?
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?
How good were the questions?
How helpful was your interviewer in guiding you to the solution(s)?
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.
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
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.