We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Python Interview with a Meta engineer

Watch someone solve the closest pair sum problem in an interview with a Meta engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Closest Pair Sum

Interview question

1) Find and return a pair of integers in a sorted array (all integers are positive) that, when summed up, bring you the closest to the value of k. 2) Given the root of a binary tree, imagine yourself standing on the right side of it and your best friend standing on the left side, both observing the tree from their respective sides. Return the values of the nodes you can both see, first from the left side (bottom to top), followed by those from the right side (top to bottom)

Interview Feedback

Feedback about Exquisite Platypus (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

4/4

What went well: She was amazing. She did a great job first asking clarifying questions. She then took notes and helped visualize what she was thinking. Her explanations were clear and she explained her thought process during the code as well. She followed the 8 step process to coding interviews perfectly and I have no doubt in my mind that she will succeed in her future interviews. Additional tips: Writing down the steps of how to solve problem is optional but I believe it can help some candidates when it comes to communication.

Feedback about Platinum Warrior (the interviewer)

Would you want to work with this person?

Yes

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

He provided me with a very detailed guidance on what to do during an interview. Really appreciate it!

Interview Transcript

Platinum Warrior: Okay, so today I'll ask you a couple of coding. I'll ask you a coding question and we have time to ask you like a second coding question. And the main thing that I do want to say is I do not care. I mean, I don't care about syntax that much. All I care is all I really care. I mean I care about a lot of things. But what I really want to see, where I really want to see you shine is like in your, in the way that you communicate. I want to see you communicating clearly. So yeah, I guess at the end, at first I'll ask you these two questions and then after that at the end I'll kind of tell you about my eight step process to kind of just like passing any coding interview and stuff like that and also tell you about what, what went well and what could have gone better. Cool.The main point is it's not about the question and it's not even about you getting the question. I guess like you writing the right syntax for the question or you even knowing how to code at all. The main thing that I really want to see is two things like efficiency, communication and I guess a little bit of speed as well. Okay, the first question I'll ask you is this. Okay, so you're given a sorted array of positive integers and an integer K. I want you to find the pair of numbers whose sum is closest to K. And this sum can be equal to less than or greater than K. And all I want you to do is just return the pair. For example, you have this input which is like a 5, 8, 14, 17, 25 and K is 35. And the right answer would be 8, 25. The reason for that is 8 plus 25 is 33 and that's the closest to 35.

Exquisite Platypus: I see, perfect. Let me make sure I understand the question correctly. So basically I want to find two numbers and then I, I should return this sum, right?

Platinum Warrior: No, you would return.

Exquisite Platypus: I'll return the 2 number.

Platinum Warrior: Yeah, return the 2 numbers.

Exquisite Platypus: Yeah, I see. So I return the 2 number that has the sum that are closest to a given number K in the input. Perfect. So I mean, what can I assume that, you know, the input always have at least two elements?

Platinum Warrior: Yeah, that's a great question. And I would say. No, I think that's actually something that you should take.

Exquisite Platypus: Okay, so edge case first we have to check if input have at least two elements in that one thing I'm going to check for first. Second thing, you know, will I have to deal with your negative numbers or is it going to be only, you know, non negative numbers?

Platinum Warrior: Yeah, no, because like I said over here it says all integers are positive.

Exquisite Platypus: Okay, sounds good. So I mean, I don't think it changed that much, but.

Platinum Warrior: Yeah, but K, K can be negative.

Exquisite Platypus: Oh, K can be negative. Great. K can be negative.

Platinum Warrior: I see.

Exquisite Platypus: Perfect. So I want to return the two number and I want to make sure that your sum is closest to K and then perfect. So I guess with this kind of problem, the brute force approach would be, you know, you check every possible pair. So it would be like two will be like a nested loop. Basically you check every single pair. You record what's the difference between the pair with K and then you could record the. You basically record the answer with the minimum delta and you store it in like in a variable. And then once you have iterate through all the possible pairs in the array, you can make sure to return the current minimum, the current answer you have. With that kind of approach, we'll be looking at on square, where N is the number of elements in the array and then obviously space will be a one because you only use like, you know, like an answer variable to store whatever we have at that time. But I think we can definitely optimize it a little better. Instead of on, we can do something. Sorry, on square, we can do something like on approach here. You know what I think of right now is we do some sort of like a two pointer where. Let me try to copy paste this so I can explain it. So because we are giving a sorted array, right? So I think we can utilize this, this thing uses like a sorted feature to kind of design an algorithm here. So I can have like two pointer I and J that starts from either end, from the two ends of the input array and then I'll calculate their sum. Basically, I want to be like closest to K as possible. So, you know, if the current sum, if I'll just. If it's equal to K, then we can just return the 2 number, right? If the current sum is greater than K. So we know that, you know, we have to make the current sum smaller so we can get closer to K. So how do we make this smaller? Because these are the two like extreme ends. So if you want to make this smaller, we have to make one of the two numbers smaller. And the only smaller number we can get to is to make j smaller here. So basically, if I want to make the sum smaller, I will decrement J and then I'll get to a new sum and then I can check that sum again. And if the current sum is smaller than K, decrement J and then I can increment I, because that's the only way I can do to make the sum bigger. Does that kind of make sense? And then in the end I should have some Sort of a combination that is the closest to K. Does that make sense?

Platinum Warrior: Yeah, that makes sense. So how would you check that your sum is closest to K?

Exquisite Platypus: I see, so that's a great question. So to check if from the closest to K, I can have like a variable to store, you know, you know, the current answer, I guess for. Just answer for short. And I will have it like. Basically I will keep checking. So let's say our current is. So our case 35. We wanted to return 33. We wanted return 8 and 25 in this case. Right? With that example we have I and J start at 0 and 1, 2, 1 2, 3, 4, 0 and 4. The current sum is 30. And we see that it's actually smaller than our K. Right. So let me write it down. So I equals 0, J is equal to 4, per sum is 30, which is smaller than K. So I record Ans as. I guess I need to do as like a tuple. I mean. Yeah, that's fine. We'll store it like that for now. And then we'll have this. And then because cursor is smaller than K, so we increment I as I said up here. So we increment I. And so now we have, you know, 8 and 25. Right? So 8 and 25 is 33. And we can check it by having a function where we check the sum of the 2 number recorded as and the current sum of the 2 number that we're checking at the moment. So we see that the delta is actually smaller because 35 minus 30 is 5, whereas 35 minus 33, our recursant is only 2. So we change that to 14 here. And then we can go up because it's still smaller than K. So we actually can still keep going up. And now we get like, you know, 14 and 25. So it's going to be 39. So the third time is 39. It's already greater than K. And we check. So the current Delta would be 4. And the current delta is actually greater than what I have right now. So I can actually break this loop right here because I know that no matter. Oh, actually, no, I can't. So it's 39, it's greater than K. So we're not going to change the answer. So the current sum is greater. So we're going to decrement A. Right? And then when we reach this step here, we're going to get to. The current sum will be 31, I equal 2 and J equals 3. So we have the current sum will be 31. 31 is smaller than. Is more than K. But you know, my current delta is 2, whereas, you know, my smallest delta is 2. And this delta is 4. So we still not gonna change my answer. And then, you know, the smaller than K. So we increment J. Sorry, we increment I. And now I and J is equal to each other. It's gonna be at three. This is when we break the loop, when I is equal to j. And then once we finish the iteration, we should have the answer as a number of index one and four, which is eight and 25.

Platinum Warrior: Okay, cool. I guess the question that I wanted to ask was just like how do you calculate the delta?

Exquisite Platypus: Oh, that's. So I will take the sum of the two number array at, you know, I and J. Array at J and then minus K. Obviously we have to make sure we are, we are doing this in the absolute value because we want to make sure that we, you know, is the difference. So it could be smaller or larger. So we have to make sure that we do the absolute value.

Platinum Warrior: Okay, awesome, awesome. Sounds good. Sounds good. And now what would the. So how would this decrease the time complexity? What would the new time complexity. Complexity?

Exquisite Platypus: The new complexity would be O because we only do we only go through all. Every element in array at most ones because like at each step, I either decrement J or I increment I. So it should be on time complexity and space should be O1 because I only have, you know, three, four variables most.

Platinum Warrior: Okay, cool. Sounds good. Whenever you're free, you can start coding it whenever you're ready.

Exquisite Platypus: Oh, perfect. Sounds good. I will just type it down here. I will have my function as, you know, find here.

Platinum Warrior: Closest.

Exquisite Platypus: And then I have an input as my array and a number K. Right. So we have to make sure that, you know, as I said before, there's an edge case where the input. There's not. There's not enough elements in the input array. So we have to make sure if length of array is smaller than two, what should I return in this case? Do I return like a nothing or should I return the empty tuple?

Platinum Warrior: Yeah, that's a great question. What do you think we should return? If let's say a user gives you an invalid input, what do you think we should return?

Exquisite Platypus: I usually return something that can flag as an invalid input. I can write exception here as like invalid input or I can just return like a null or I can return, you know. Yeah, an empty tuple that I think would be the best case just to Find that we don't have anything.

Platinum Warrior: Okay. Actually, I think, yeah, I think what you said, I think raising an exception would be the best. But I think for now you can just return none.

Exquisite Platypus: Okay, I should return none. Sounds good.

Platinum Warrior: Cool.

Exquisite Platypus: Perfect. So that will be the edge gate. We want to make sure we get. We have our I. We will initiate I and J equal to 0 and length of array minus 1. That's the 2 index. I have my current and will be none. And yeah, I think, I think we only need. We can have Delta 2. I think not really necessary, but.

Platinum Warrior: We.

Exquisite Platypus: Should set it to none right now. Okay. So our loop will keep going when I is smaller than J. That's our condition to keep the loop going or break the loop. So basically you have to check currency will be the total sum at index I plus the number at index J. And then we want to check, you know, if this cursor is equal to K, we'd like to return immediately because, you know, we wouldn't have any other combinations that could, that could have any smaller kind of difference, basically because it's equal to K. So we can actually return array at I and array at J. Aleph current sum is smaller than K. So in this case. Right. So if current sum is smaller than K, we want to make the sum bigger. So here we will increment I. But before we increment I, we have to check the current sum and the delta to see if, you know, if it's smaller. And then we replace. And so basically, if not ans, we're just going to return, we're just going to report this as our current answer. Answer equal to this. Else we have to check if our unoccurrent delta is smaller.

Platinum Warrior: Okay.

Exquisite Platypus: Than that recorded delta. So if ABS of array at I + array at j +k is smaller than delta, then we report our new answer, basically. And then we have to upgrade our delta too. E is going to be this part here. Yeah. And then we increment I. Oh yeah, no, we increment I over here. That's correct.

Platinum Warrior: Yeah.

Exquisite Platypus: And then this is the case where current sum is greater than K. Right. So sorry. So again, if not answer, we still, we still want to record this as our current answer as our most, you know, the closest we can get. And then if not, then still we, we still want to make sure that, you know, we record the new delta that we have. So if, oh, you know, this is correct. So if the current total -k, the delta is smaller than our current delta, record our new answer and we update our delta accordingly. But in this case, instead of increment, I will decrement J and then, you know, the loop will keep going back until we have I equal to J. And in the end we should return and as our final answer. And. Yeah, I think that should work.

Platinum Warrior: Okay. Okay. So is there anything you can do to make your code, I guess, more efficient? It's not efficient, but cleaner. Shorter. Yeah, a little cleaner. I think there's something that's catching my eye.

Exquisite Platypus: I see. Perfect. Let me. Let me do real quick. I guess. I guess this, this else if is a little. A little. A little, you know, lengthy kind of. So instead of this if else statement.

Platinum Warrior: And instead this delta or action or. I mean, that's.

Exquisite Platypus: That's fine.

Platinum Warrior: No, the thing is, you're doing it twice, right? You need to do it twice.

Exquisite Platypus: Oh, yeah, that's what I mean. So I don't actually have to do it twice. That's actually a great idea. So we'll do this and move this up here. So basically we'll do this every time and we'll increment or decrement J based on whatever we have. So let's say if array I + array J is greater than K. Sorry, decrement J and L, we can increment I. Does that seem better? Because I only do this once and then I change it after.

Platinum Warrior: Yeah, yeah, that's. That's much better. That's much better. Cool, cool. I mean, you could. You could also, like, you know, instead of RI plus rj, you already have a first sum as well, you know.

Exquisite Platypus: Oh, yeah, that's right. That's true.

Platinum Warrior: Yeah, that's fine. That's fine. Yeah, I can just change it. Okay, cool. And then you already said the time and space complexity, which is O of N and O of one. That's good.

Exquisite Platypus: Yeah, that's right. O and O.

Platinum Warrior: Cool. I think. Now, so at Meta and Google, we don't. We turn off the run button. We never want people to run. Instead we ask people to do a dry run. So can you do a dry run?

Exquisite Platypus: Yeah, for sure. Can I do that with a given input that you give me or you want me to try it within, like another different input?

Platinum Warrior: You can use either the given input or you can use your own. It doesn't matter to me. Anything's fine.

Exquisite Platypus: Okay, sounds good. I can just use the given input. So I just paste it here so I can keep track of that. So first thing, as we call, you know, we check if the length of array is smaller than two in this case. It is five. So you know, we don't actually execute this block. So we're going to go to this one right here. So we have I equals 0, J equal 4 in this case, right? And then and would be none. That's what we initialize it to. Delta will also be none. Perfect. So right now I J will equal to 0 and J equal to 4. So first our cursor will be array I plus array J which is 35 plus 25 is 30. That's our cursor. Cursum is not equal to K, right? K is 35. So Cursum is not equal to K. So we're actually not going to be executing this block. We're going to go down here. So if not. And so we don't have any answer. So we update and to be 5 and 25, basically so, and then we move down here. Cursor is 30, which is smaller than K. So we want to increment I. So I will be 1 and J will be the same. So right Now I is 1, J is 4. Cursor will be 8 plus 25, which is 33. We have 33 here. So cursor is not equal to K. So we're not gonna, you know, do anything. We're gonna go down here because our and exists. So we actually want to execute this block here we have, you know, the sum is 33 minus 35, which is minus 2. And the absolute value will be 2 and a smaller. Oh, I should have the delta here too because delta is none because I didn't record delta in this line. So delta will be basically this. So I have, so now I have Delta which is 5 plus 25, 30 minus 35. So it's going to be 5 right now. So my delta is 5 and the current sum is 33 minus 35 is 2. So because 2 is smaller than 5. So we actually want to report our new answer. Ask 8 and 25. And now Delta will be 2, right? And then you know, the current, the current sum is still smaller than K. So we still want to increment I. So I will be 2. So we add I equal 2, I equal to j equal 4 here. So the current sum will be 39. So 39. The 39 is not 35. So we're not executing this again, we have our answer. So we're going to check this block here. The current delta is 39 minus 35 is 4. And our current delta is recorded as 2 here. So it's actually not smaller. So none of this will be executed. We'll just move straight down here, these blocks because our current sum is greater than K. So we want to decrement I. Sorry, decrement J. So we have j equal 4 up here. So j will now be equal to 3. So we go back to our loop again. So we have I2J equal 3. So the current sum will be these 2 number which is 31. And then it's not. It's still not our current. It's not K. So we want to check this one because our ands existed. So again we check into this block. So the delta with 31 and 35 is 4, but the current delta is 2. Right. So this will not be satisfied. So we're not going to execute anything in here. We're going to go down here again. So we have 31 smaller than 35. So we actually want to increment I, but then, you know, I equal to J and the condition for outlook no longer is no longer satisfied. So we break out the loop and we return our current answer, which is 8 and 25, which is the expected.

Platinum Warrior: Answer for this problem. Okay, cool, cool. Yeah, I have a couple of questions for you. So I guess what would your code do if there were, let's say, two closest values? For example, there's 825 and there's also, I don't know, 14, I don't know, 1419. Right. So what would your code return?

Exquisite Platypus: My code will return 825 because I only updated when the new delta is smaller than the current Delta. So because 1419 will be basically after 8:25 because the iteration goes inward. Right. I start ing. So it's going to be processed after. So it's going to record 8 and 25.

Platinum Warrior: Okay, cool. And then the other question I have for you is what would your code return if K was smaller than all of the values in the array? For example, k is 2 or k is negative 5 or something like that.

Exquisite Platypus: That's a great question. I actually thought about that before and then I forgot. So if K is smaller than all of the possible number, it returned the first two elements here. That's like the closest we can get because we know. I actually thought about it. So because we know that our, our array only consists of, you know, positive non negative numbers. So actually you can make like another case, you know, where if K is smaller or equal to 0, we can actually return immediately array at 0 and array at 1. Because we know that, you know, it's only going to get bigger and bigger and bigger with Whatever number is after the first number here, because they already sorted.

Platinum Warrior: Okay, cool, cool. Awesome, awesome. Okay, cool. Yeah, I think, I think we're good on this one. I think you came up with the edge faces, so good job. Yeah. If you're ready, we can move on to the next question.

Exquisite Platypus: Yep, perfect. I'm good.

Platinum Warrior: Cool, cool. Okay, here is the next question. Let me, let me give you some few examples. Okay, here's the next question. The next question is, you're given the root of a binary tree. I want you to imagine that you're standing on the right side of it and your best friend is standing on the left side. You both observe the tree from your respective sides. I want you to return the value of the nodes that you can both see. So what I mean by that is first output the nodes from the left side view in bottom to top order. Then output the nodes from the right side view in top to bottom order and just kind of combine them. For example, if you look at this example 1, you'll see on the left side view your friend 1, 2, 5. But I want your friend to return it as like 5, 2, 1. And on your side you can see a 1, 3, 4. And then the output, I want you to combine them. So you combine 5, 2, 1, 3, 4. Same thing. On example 2, your friend is standing on the left side. He sees 1, 2, 4, 5, but he has to return bottom up. So it's 5, 4, 2, 1. And your view is 1, 3. So but you 5, 4, 2, 1, 3.

Exquisite Platypus: I actually have done this question before. I mean, I'm not sure if that's the most optimal way, but basically we do a level order traversal and we want to have two separate arrays to store the, you know, the left side and the right side. In the end, we should flip the left side and combine the right side and minus the root. I think that's what I was going to do. And the problem.

Platinum Warrior: Okay, cool. Yeah, I think, I think that would be it. But there's actually a couple nuances in this. That's actually, that actually could get you. Let's, let's try the problem and I'll ask and then you'll kind of see what I mean.

Exquisite Platypus: Okay, I guess you do. No worries.

Platinum Warrior: I'll. I'll let you. I'll let you know. There's like, there's like more to it than meets the eye. If you could find out those things and let me know. But. Yeah, go ahead, Go ahead.

Exquisite Platypus: Perfect. So I'm just gonna approach this. I, you know, I Haven't known anything. Okay for, for this kind of problem because you want to see, you know, both the left and the right side and we want to, you know, basically have it like level by level. So basically the best way to approach this would be, is some type of like a level order traversal entry. So basically we will go from, you know, the first level which is the root and then we go down and down we go, we keep processing, you know, the next level until we don't have any elements. So it should be a type BFS traversal. And to do this I will implement like the queue that store a double ended queue. So I mean a queue but in Python you use a double ended queue. So that goes start from the root and then, you know, and then I'll traverse this queue until there's still element in it. And then I will have, you know, basically I would, I would check the current index of the element in within the length of queue. So we know that, you know, let's say start at you know, the first element is the root in this case, right? So we know if it's the leftmost element if the index is zero and we know it is the rightmost element. If the index to relative to the queue is going to be n minus 1, which, where n is the number of elements in the queue. When we process it, I want to first process it. So basically we check for current index index if I equal to zero, so it belongs to the left side and if I equal to n minus 1 it belong to the right side. And yes. So in the end I will have once I traverse everything So I have two array which is 1, 2, 5 and 1, 3, 4 because I do a level order traversal. So it'll go from top to bottom. But so we want to do a left view bottom up. So you know, we actually want to flip our array. So it's going to be 5, 2, 1 and 1, 3, 4 and then we want to make sure that you know, our root only count one. So I will actually pop the last element from the left side because I know it's going to be the root and then I just going to, you know, append the right side view to it and it should be 5, 2, 1, 3, 4 as the final answer. Some of the edge case would be, you know, where you know, we don't have a tree root doesn't exist. So we just return an empty array. Then I, I would say because we don't have any, we can't see anything from either side of the tree.

Platinum Warrior: Okay.

Exquisite Platypus: And for this edge case too. So. So this one. So we look 1, 2, 4, 5 is the left and we have 1, 3, 4, 5 as the right side. Oh, you actually don't see anything on the right side. Oh, I see.

Platinum Warrior: Okay. So actually that's actually the edge case that I wanted you to think about. Because even if you're So I guess. Okay, So I guess let's talk about this part for a little bit.

Exquisite Platypus: Yeah.

Platinum Warrior: So you see here, let's look at nine. So what would be the. What do you think would be the left view and the right. What would be the left view?

Exquisite Platypus: The left view would be 1, 2, 9.

Platinum Warrior: Okay. It'd be 1, 2, 9. Right. Okay.

Exquisite Platypus: Yeah.

Platinum Warrior: So what if. What if we did. What if we did this? Okay, so what would be the left view for this?

Exquisite Platypus: Would it be 1298?

Platinum Warrior: Yeah, it would be 1298. But here's the problem. So I did. This is what I said initially, right. I said for this one, I think it was a little confusing because I did say right view is 1, 3, but if you really think about it, right view is also 1, 3, 4, 5. Right.

Exquisite Platypus: Yeah, that's what I thought.

Platinum Warrior: 2.

Exquisite Platypus: Because. Yeah, I mean, you don't. You still have two notes and if you stand from the right side, you can still see them.

Platinum Warrior: Yeah, yeah. And same thing here, right? The same thing. The right view be for this side.

Exquisite Platypus: As you 1, 3, 4, 8.

Platinum Warrior: Yeah, yeah, exactly. So you would probably. You would need a little bit extra processing before. Before you finally get the answer. So how would you deal with that edge case?

Exquisite Platypus: Well, I mean, I think for my code it would actually be the same because, you know, I mean, I process all these levels, right. And then for the last level, my queue only have one element, which is this eight here. And if I check, you know, I equal to zero, so I append it to the left. And if I equal to n minus 1, which is n minus 1 equals 0, I will append it to the right. So I don't think that it matter for my logic because I only check like, I don't do like an if else. I do just if, basically.

Platinum Warrior: Oh, okay, I see, I see, I see. Okay. Actually, can you, can you turn that into code? I'm kind of curious.

Exquisite Platypus: Yeah, of course. Sounds good. So I'm just going to do it right here. So I'm going to have my function as binary tree view. So I have a root, and I think that's the only input that I need. Right, perfect. So sounds good. And then I start with if the root doesn't exist, we're just going to return an empty array. You don't see anything. Let's say above. And then we want to have our queue that has. Sorry, I need to import form collections. Import back. Perfect. So that should be good now. And then I will do y my cues to exist. I will check for I in n would be equal to length of Q and for I in range of n. So this is where the indexing I said would be. And. Sorry, I need left hand right equal to 2 NT arrays to store my answer. Right. So for I in range of N, so it will iterate from 0 to n minus 1. Right. So if I equal to 0, I know it's in the left side. So left will append. Sorry, I need to curve equal q top left. Yeah, because it's a Q right cur.

Platinum Warrior: Val.

Exquisite Platypus: Assuming we have the A note class, I can implement that later. But let's say we have a note class that have a tree note that has a value property. And then if I equal to n minus 1, basically it means that it's the last element in the current queue. I will have write appendix. And then I want to check if you know, for child. I want to check their children to keep appending to the queue. Curl cur. Right. You know, I want to append it to my queue. Append child. If child. Sorry, I need to check if child. Listen, because I don't want to append any. That joint does exist.

Platinum Warrior: No.

Exquisite Platypus: Yeah, if a node doesn't exist, I don't want, I don't want to process that. So, yeah, so that should be it. And then I want to reverse left pop. Because we want to remove the root in the left function.

Platinum Warrior: Okay.

Exquisite Platypus: Yeah.

Platinum Warrior: And then, so if you, if you reverse do left dot top. Does that, does that get the end element or the first element?

Exquisite Platypus: Sorry, it get the. So, so right. So here, let me, let me come back to this. So it starts at, you know, one two, nine, I guess up here. One two nine eight. Right. So if I reverse it, it will be 8,921 and if I pop it, it will pop the last element of the reverse, which is the first element.

Platinum Warrior: Okay, got it, got it.

Exquisite Platypus: Yeah. So I return left plus right. And that should be the answer. I think the reverse is wrong, but.

Platinum Warrior: Yeah, that works. But I guess so does. Okay, so here's the question. Here's a question I have for you.

Exquisite Platypus: Yep.

Platinum Warrior: If you look at your code, actually let's go through a. Let's go through this example. All right.

Exquisite Platypus: Yeah, sounds good.

Platinum Warrior: Yeah, let's. Let's do a dry run because. Because I want to see if you. Okay, let's do a dry run and I'll show you what I mean.

Exquisite Platypus: Okay, sounds good. I can try to go through a dry run. So with this modified one right here. Right. So let me copy paste the tree.

Platinum Warrior: So I can see. And.

Exquisite Platypus: Yep. So that's our tree there. So our root is the node one. So deck will be one here. Left and right will be two empty arrays. Right? Our root is only one. Perfect. So while Q still exists, so you know, we have our Q as the only element, N will be equal to one. So for I in range of N, so we iterate. We only iterate this once because. Because we only have one element here. So you know, I will be equal to zero. Cur will be equal to Q pop left, which is Q pop left, which is this one right here. Let me just copy the Q here. So I can see. So that will be the root node. So we see that I equal to zero, right? So left will append curve out. So this is left. We append it here. I equal to n minus 1, which is also right because n is 1 and 1 minus 1 is 0. So we actually satisfied this one right here. So right will also append curval. And then we check the left and right child. So we have two and three as their left and right child of the root node. They both exist. So our q will be 2 and 3 here. Yeah. So now the queue will be 2 and 3. Our length of the queue will be 2 because there are two elements in the queue, right? So we iterate from for I in range of length of n. So I start at VO. The current node will be 2 and we pop it out of the queue. And then. Sorry, where am I? So rv equals 0. The current node is 2, I is 0. So we left the pen curl valve. So we actually append here to the left. We know that zero is not equal to two minus one. So we're actually not gonna. Not gonna deal with this. And then we. We will check for the child of the current node. So 2/2 the children is 9 and 5. So we're gonna append it to our current queue. And then we go back to the iteration. So I will be equal to 1 now and the current node will be 3 because we pop the first element out the queue, right? And we know that I is one. So we're not going to append here. We're going to execute this because two minus one is one. So this is satisfied. So we append three to our to our answer. And then we check for the children of the node with value 3. So the left child exists. So we're not going to append it. Then we append the right child, which is four in this case. So we append four because we already finished our iteration here. So we're going to come back with our queue with this while loop right here, the other iteration. So the length of Q will be three now. And then, you know, I starts again at zero. Current will be nine. We pop it out of the queue, right? And then, you know, because I is zero. So we append nine to our left. And then we check for children of nine. So we don't have anything. Nine doesn't have any children. So, you know, our Q will remain the same after. So I will be equal to one now because of this loop. So when I equal to 1, the current node be 5, we actually pop that 1 is not equal to 0, nor it's equal to n minus 1, which is 3 minus 2 in this case. So we're not going to append anything. We don't want to append the current node to any of the left or right view. We want to check the children though. So five have children as eight, right? It's a left child. So we're gonna append eight to our current queue. And then so we're gonna have one last iteration for this one. So I put a two. You know, we know that the current node will be 4. We pop this out of the queue 4, not 5. My bad. So 4. So we have I is not equal to 0, but I equal to n minus 1 here. So it's going to be 1, 3, 4. So you want to append the value over there. And we check the children. So 4 doesn't have any children, right? So we're not going to do anything. And so we have already finished this iteration. We're going to go back to this queue, to this outer loop here. Basically we see that, you know, Q still have the one last element here. We change our length to be one and iterate from zero. Sorry. So here we have current will be eight and our Q will be empty. So the current value is 8 and I is 0. So we actually left a 10 curve out. So it's going to be 8 here. And we see that, you know, I is also equal to n minus 1. So we actually also want to append it to the right. And A doesn't have Any children. So, you know.

Platinum Warrior: So this is kind of exactly the problem that I was kind of getting at. Right. Because you have duplicates and we. And I think maybe I wasn't clear enough. I think the reason why you see it says 5421 and right view says 13 is because we don't want any duplicates. We don't want eight on both sides. We want to pick one side. That's what I was saying, like, okay, this 5421, that's why the example, the right view only has 13 because we don't want to have same thing.

Exquisite Platypus: I see. Sorry about that. I didn't. Sorry, I should have.

Platinum Warrior: Yeah, no, clarified it.

Exquisite Platypus: No problem for that. Then I think I can. Instead of like a two IF statement, I can do an ELIF here. So basically it's only gonna append to either or if it satisfies both. Right. So for the last one, eight's not gonna be there, you know, or even the first one when it's not gonna be here. So we don't even. Then we don't have to pop from left because our boot is not gonna be. The output is not going to be repeated because only append if or else if. So we can make sure that we only do one element at a time. Yeah, that would be the code then.

Platinum Warrior: Yeah, that works. Cool. Okay. Yeah, yeah, yeah. Are you done? Sorry.

Exquisite Platypus: Yeah. Oh, sorry. I should talk about complexity.

Platinum Warrior: Yeah.

Exquisite Platypus: So for this problem, because we do a level order traversal, so the maximum space complexity will be the width of the tree. I mean, but we don't have like a complete, complete binary tree. So I mean, the worst case scenario it could be O divided by two, I think. But still on. In the best case scenario it could be a one. Because every node only, you know, there's only one node in each level, but still average out still be O. And then, you know, for time wise, we are traversing each node once. So it's going to be on for where N is the number of nodes in the tree.

Platinum Warrior: Okay, cool, cool. And. And one more time, do you have any other edge cases or. I think this might be good.

Exquisite Platypus: But let me think if I can think of any other edge case. I mean the edge K would be root doesn't exist or it would be a very skewed binary tree. That would be one of the other edge case. But I think the code actually deal with that. Let me think. One, two, nine. Yeah, I think, I think that's it. I can't. I don't really think of any other edge case.

Platinum Warrior: Oh, yeah, yeah, no problem. No problem. I don't think there are any other edge cases.

Exquisite Platypus: Okay. I was curious for a second.

Platinum Warrior: Okay. Okay. Cool. Cool. Yeah. Awesome. Awesome. And I guess one of the questions. Another question that I have is. I don't know, they usually ask this, like, dumb question. I hate this question. But, oh, like, what would you do if, like, the tree doesn't fit in memory? Or some dumb question like that. But I don't know. Do you have an answer for that even? I don't know if I have the answer for, but if you do, I think, like, I'd be down to listen.

Exquisite Platypus: So basically the tree doesn't fit into memory.

Platinum Warrior: Yeah, that's a dumb question. Never mind. Don't worry about it.

Exquisite Platypus: I mean, if you're only given a root note. I don't know.

Platinum Warrior: Yeah, me neither. Me either. It was a dumb question. It was a dumb question.

Exquisite Platypus: Yeah.

Platinum Warrior: Don't worry about it. For some reason, I get that. I used to get that question a lot. I'm not getting it as much anymore. That question for every time I got asked a question and I. Maybe I finished early, they would always ask, okay, what would you do if this array doesn't fit in memory? What would you do? And I'd have to give them, like, a design answer. And I was like, dude, this is such a dumb question. But, yeah, cool. Cool. Yeah. Great job. Yeah. Sorry for giving you a problem that you probably have already seen.

Exquisite Platypus: That's fine. I think it's very good when I can see work with the different educators and everything. And I do misunderstood the question. So, I mean, definitely on my end too. So.

Platinum Warrior: Yeah, yeah, no problem. No problem. Yeah. And. Yeah. And I think. I think overall you did. You did an amazing job. You did a really good job. You communicated how I wanted you to communicate. And the last couple of minutes, I'll kind of tell you what I see in all the interviews that I've done and what I think is, like, the process where I've seen the most candidates succeed following this process. And we'll go through. We'll go through these steps and I'll tell you, like, what you did and what maybe you didn't do, but either way, I think you did an amazing job. Five stars all around, so no problem. But yeah. Okay, so let's go. Let's go through it. Okay. Step one would. Would always be ask clarifying questions. And you did ask clarifying questions. And I think the rule of thumb is try to ask at least two Clarifying questions. You always need to ask clarifying questions because you want the interviewer to think that they're smart, you know. And also let's say that I give you like a project and whole project and then you just go down and do the project. You didn't ask any questions. Then I won't really like think that you knew you understood the project and I won't really have any trust in you completing the project correctly. So you did do a good job on that. I did see you ask, ask at least two clarifying questions. And, and if you can't, if you can't think of one, can't think of one, then just ask what to do for an edge case, which you also did that. You also asked for that. Like, what do I do if like less than two elements in the array. Yeah, the root is null. You can't think of two elements ones. And the second one can always be like just, just talk about the edge case. Like, what should I do if this? What should I do with that? So you did a good job. So good job on that. Part two, step two, after clarifying questions, step two is always visualize the problem. And you did do that part as well. So I did. You were writing down, you were writing down like you were taking notes, writing down. And this is the main thing that I don't see like a lot of interviews, lot of people do. And this kind of makes worried about some people. A lot of people kind of like just start going into the problem or they don't really like visualize a problem. I saw you, you're. You did a good job. You did take notes. You were like, okay, I did this, I do that. Okay. Q equals EQ and stuff like that. Great job on this part. One thing I will say, this is actually optional. You don't have to do this. But I do very strong candidates doing this. You didn't really need to do it. But I also see a lot of, a lot of the candidates that I've interviewed did this and we end up passing and reason thing that they did is they write down the steps. They write down the steps of actually. Sorry, sorry, sorry, sorry. This is step, this is step three. Oops. Brute force. Yeah, a lot of candidates forget the brute force solution. They're just jumping in. This is actually my rubric at Meta right now. And this is actually one of the things, this is actually one of the things that we actually test people on. Did the candidate come the brute force solution and improve upon that solution? And obviously there is no Brute force solution. But the first question there is a brute force solution. And I'm really glad that you brought that up. So great job. For this you only need need one sentence. You don't even need more than one sentence to be honest. The thing about, I guess, ripple interviews and other interviews is you get an hour for all of this.

Exquisite Platypus: But yeah, I do get an hour.

Platinum Warrior: An hour for all this, but a meta interview you get exactly. You get about 35 to 40 minutes. You have to solve two questions, right? So you need to find ways to like, increase the. And you need to find ways where you can like, you know, decrease the amount of this, decrease the amount of that and increase like this. So that's why it's okay that you, you can, you could say in more than one sentence. But I would say for like a meta interview, keep that one. Okay, we can solve this using this. But that would be O of N squared. But I think that we can do better. That's it. Brute force solution. You did do that, so great job on that part. And step three, the reason why I tell a lot of candidates to write down the steps of how to solve the problem. And these steps don't even have to be that good. Here, I'll do it over here. So it could be like step one. Okay, what was it? Hold up. Sorry, sorry. Okay, step one, step one, two pointers. Step two, check absolute value minus K. Step three, if some greater than K, move left and less than K, I don't know, move right. Yeah, yeah. It doesn't have to be like, it doesn't have to be like an essay. You're a software engineer. You're not a, not an English. Just like a couple steps. And there's two reasons why I usually tell these. Can't tell candidates write down the steps of like what they're going to solve. You don't it. Because you did a great job. But I tell a lot of other candidates, a lot of other candidates that struggle a little bit to do this. And the reason why is two things. Well, let's say you wrote down, let's say you wrote down the steps of the problem and you wrote some code. And right after the interview I have to go go through like five different meetings. And after, right. I have a lot of stuff to do and I'm really stressed with work. Then after five, six hours, I come back to your code and I look at your code, see a lot of the syntax is off. Or I see the code and I see like some parts of the code that look Kind of wrong. If I see that and I don't see any steps, I'll be like, okay, I think she misunderstood the problem. She got the syntax wrong. Okay. Probably have to fail her. But if I see the steps. If I see the steps that you wrote and then I see your code and I see there's some syntax issues, I'll look at the steps that you wrote, and I'll be like, hey, got the steps right? Maybe she just get the syntax. She just got the syntax wrong a little bit. You know what? She still has the right idea, and she communicated well, so I think I'll still pass her. The other reason that I tell some candidates to write down the steps is because usually there's times where if you don't write down the steps, you'll begin to code. And obviously, the stress of an interview is a little bit stressful. So you begin to code, and you kind of forget what you're doing as you code, right?

Exquisite Platypus: Yeah.

Platinum Warrior: What do I do now? What do I do here? I totally forgot. Blah, blah, blah. So you forget what you're doing as you're doing because of the stress of the interview. And these steps will kind of be like, oh, okay. Okay, this part I got to do the two pointers. Okay, this part I got to check the absolute value. The last thing is sometimes talking while coding is kind of, like, difficult, but you did a great job on that. You did a great job on that. So for some people, talking while coding is difficult, and this kind of gives people, like, a good kind of script.

Exquisite Platypus: I see.

Platinum Warrior: So obviously, you don't have to do it if you don't want to. This is optional, but I do see my strongest candidates doing this. And. Yeah, and it. And it can help. And it can help. But also, you have to look at the time. Right. If you only have, like, yeah, don't worry about. You have a lot of time. Okay, go ahead, do this. You know, pretty clear. But overall, you don't. You don't need to do it, but it's an optional thing. And that's just what I tell Candice.

Exquisite Platypus: I see. That makes sense.

Platinum Warrior: And step four, after you, like, visualize the problem, you take notes, you write down the steps of how to solve the problem. You always ask, can I code now or can I code now, or may I begin coding? Can I start coding now? The reason why you want. You always want to ask this is because. Or like you said, okay, are we good now? Or do you understand? The reason why we want to ask this is because if you don't ask the interviewer how they're feeling. We're just going to. You're overconfident, and you don't want to listen to the interviewer. Because a lot of interviewers, they really want to ask you a question, right? They want to be. When you ask. When you ask, can I code now? Usually some mean interviewers, they'll ask you a bunch of, like, dumb questions like, what about this? Or they'll try to, like, trip you out for some reason. And you want to let them. Do you want to let them do that to you? Or else they'll kind of. Or else you'll get docked a couple points being like, okay, I can't work with this person. They're overcome. They didn't allow me to speak. So you want to have pause. Allow the interviewer to, like, digest what you said and then ask you questions. Ask you questions. And if they don't need to ask you questions. And you're very clear. Okay, you did a good job on that part as well. So step five, obviously, begin coding and explain your code as you're coding.

Exquisite Platypus: Yeah.

Platinum Warrior: So obviously you don't need to explain every single line of code, but you can just explain. Okay, so this part I need to, like. Okay, this part I need to go through the. Go through the. Go through the queue. Okay, this part. Oh, if it's the first element, and then if it's the last element, I'll append. Okay, boom. Start coding that. Okay, this part then. Now I need to do, like, a for loop. Okay, you just need to do that. You don't need to explain every single line of code. You kind of explain, like, just explain, like. Yeah, just explain, like, an excerpt, like a little part of the code. Code it part of the code and stuff like that. Or do it during that. That's great, too. Job on that part. So step six, right after you code, try to come up with. Try to come up with two edge cases yourself. If there's only one, come up with one. But after coding, you should always try to come up with the edge cases yourself, because if the interviewer comes up with the edge cases before you come up with an edge cases, that's all. Unfortunately, they'll dock you a point because they'll be, oh, she didn't really think about the edge cases. I had to come up with the edge cases, and I had to think about the edge cases. Please try to come up with your own edge cases. Try to come up with at least two edge cases if you can. There's only One. Sometimes there's none. That's totally understandable. But try to come up with your own edge cases and be quick, because if you want to come up with these edge cases before the interviewer comes up with the edge cases. Yeah, that part. And then so, and then step seven, obviously, either dry run or. Yeah, let's say step seven is actually time and space correctly. You did a good job on that part. So no qualms about that. And final step is dry run. Or some places make you run the. Yeah, it depends. So I guess Meta, Google, they don't. They make you. They may. They don't make you run the code. The run button is always like, grayed out. But yeah, so you usually have to do like a dry run. And then usually for the dry run, I tell my candidates to do a dry run right next to the code. And you did it, and you did exactly that. So overall, I wrote all of these steps to kind of just say you did everything damn near perfectly. Oh, I think if you follow what you did today, like I said, I don't at meta, I don't care if you know how to code. I mean, I guess I do a little bit. I don't care about syntax. Like, even if you said, like, even if you said reverse left, like you said, maybe it's not reverse left, I would have not cared at all, you know?

Exquisite Platypus: I see.

Platinum Warrior: Yeah, that, like, does not. That does not matter. So what mattered to me is about your communication and if what matters to me is can I work with this person or not? And how I can tell if I can work with you or not is based on how you communicate. So. Yeah, overall, great job. Really? No, I don't have too many pointers for you. I think you did amazing. And I think if you. And I think if you just follow this, follow the steps that you already did today, I think you do well in any interview you ever do.

Exquisite Platypus: Thank you very much for the feedback. Appreciate it a lot.

Platinum Warrior: Cool. Cool. Yeah, I guess. Yeah. Cool. Do you. You just. You have the ripple interview next week and that's it?

Exquisite Platypus: Yeah, I. That's. That's the only interview I have scheduled for next Tuesday.

Platinum Warrior: Is it ripple or ripple?

Exquisite Platypus: Rippling. Rippling.

Platinum Warrior: Oh, okay. Rippling. Yeah. Okay. I had an interview.

Exquisite Platypus: Well, yeah, it's a sort of ish.

Platinum Warrior: I. I know, I know. Rippling. Yeah, I interviewed with rippling as well.

Exquisite Platypus: Oh, okay. You did.

Platinum Warrior: Okay. The problem with rippling is I don't know if they still do this, but I think they do more real world problems.

Exquisite Platypus: Do you know what I'm saying?

Platinum Warrior: Is that what they said?

Exquisite Platypus: Yeah, I, I, I thought so. I mean the, I did the OA and in the OA there was a bit of like a parsing, you know, request kind of JSON file stuff. But then I think in the interview they said it's going to be more leako style question.

Platinum Warrior: Oh, they did. Okay. Yeah.

Exquisite Platypus: So obviously they might have follow up that relate to design but I think in the core coding question it should be more Leetcode.

Platinum Warrior: Okay, okay. Cool, cool, cool, cool. Awesome, awesome. I remember, I think I did an interview with them, it was leetot style but then they said they didn't care about time complexity. They just wanted me to horse things and like yeah, they didn't care about time flexi that much. So that's kind of cool. But maybe, maybe it's different now.

Exquisite Platypus: Well, I mean, I mean I check, I try to do some research to see like what people have been interview like recently. It seems to be very much coding question.

Platinum Warrior: Okay.

Exquisite Platypus: I haven't seen any like you know, parse JSON or design this, design that. Or maybe it could be different for you know, higher level interviews because I only interview for interns. So that could be.

Platinum Warrior: Oh, oh yeah, yeah, that's true. Right, you're interviewing. Okay, sorry.

Exquisite Platypus: Yeah, so I don't know design. So.

Platinum Warrior: Yeah, yeah. Okay. That's cool, that's cool. Yeah. And you, and remember, remember that if they ask you a design question it's always going to be the same thing. What's it going to be if something doesn't fit in memory, what do you do? Just always think about that. That's the question every company asks if you finish too early.

Exquisite Platypus: Okay. I would definitely try to think about that.

Platinum Warrior: They always ask that question. But I don't think you need to think about it as an intern. I think you'll probably like later. So you're done. But yeah, cool. Good job. I don't have any more advice for you. I think you did amazing and I think you'll kill it in your interview if you do the same thing. This eight step process which you followed almost exactly is all you need for any coding interview ever in your life. That's it. Cool.

Exquisite Platypus: Thank you very much for your time and for your advice.

Platinum Warrior: Yeah, yeah. And I guess last thing is here's two things I think closer to the I think when you're far away from the interview, I think you've already been doing this. Right. I think just do the, I think I just use, I just need just did the problems of this.

Exquisite Platypus: Oh, Nicode IO. Yeah, I. I know. Neat code.

Platinum Warrior: Yeah. Yeah, I just did the, the 75 in that. When I finished that, I went to the need code 150. I think those are the best. I mean, skip, skip, skip the DP and I only skipped the. What's it called? The little.

Exquisite Platypus: These binary as a bit manipulation or.

Platinum Warrior: I hate those. I always pray that.

Exquisite Platypus: Yeah, no, I, I did actually go through bit inflation and DP too, so.

Platinum Warrior: Oh, you did?

Exquisite Platypus: Yeah, I actually, I'm that desperate, so.

Platinum Warrior: Okay, okay. Yeah, the bit manipulation first. I always skip and then. And I always pray that I never get it. And I never get it. I've. I've got.

Exquisite Platypus: That's great. I, I never wish to get it. But like, I did have to kind of try to explore. I did have to do like a few problems. I'm not, I'm not a God at it, obviously not. But like, I need to at least understand what's going on.

Platinum Warrior: Yeah.

Exquisite Platypus: Yeah.

Platinum Warrior: Okay. Okay, you're good. So that, so that's what you do if you have a lot of time. And I think you did that. Good job. And closer, closer to the interview, always just, just lead code, discuss every day, lead code, discuss. Check if there's any new rippling interview questions. Look online for rippling interview questions. Just keep, keep looking online just as much as you can. Just look online for any like pass interview questions as you go closer and closer. I guess the last thing I want to say is this thing is a numbers game, right? I would honestly say interviews are 60% luck and 40% preparation. The reason why I say 60% luck is because you can do everything right. But your interviewer can like wake up on the wrong side of bed and just decide to be an asshole that day. You can just be like, okay, you know what? I'm going to wake up and I'm going to give this person a DP plus bit manipulation problem. Or you can do something right and the interviewer will be like, no, that's wrong. This is the way I wanted you to do it and because of that, I'll fail you. So this thing is a numbers game. So don't get discouraged if something doesn't go your way. Just keep clicking, apply. And then. And sometimes when you think you did really well, it might not go well. Sometimes when you did really bad, you'll get the job. So you never know. Yeah, good luck. You got this. I think if you follow what you did today, you're good.

Exquisite Platypus: Thank you very much for the feedback I really appreciate them, but.

Platinum Warrior: Yeah. Cool, Cool. Good luck and see you another time.

Exquisite Platypus: Okay, I'll see you then. Bye. Bye.

Platinum Warrior: Bye.