We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
Please read our definitive guide on Meta's hiring process and questions
Python Interview with a Meta engineer
Watch someone solve the find the minimum and maximum number of nodes between critical points 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
Find the Minimum and Maximum Number of Nodes Between Critical Points
Interview question
1) A critical point in a linked list is defined as either a local maxima or a local minima. A node is a local maxima if the current node has a value strictly greater than the previous node and the next node. A node is a local minima if the current node has a value strictly smaller than the previous node and the next node. Note that a node can only be a local maxima/minima if there exists both a previous node and a next node. Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1]. 2) Given an array of integers arr, return true if and only if it is a valid mountain array.
Interview Feedback
Feedback about Immutable Laser (the interviewee)
Advance this person to the next round?
YesHow were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Overall: Candidate makes sure they understand the problem by asking clarification questions around the problem and working through the examples. Candidate can articulate their solutions well. Candidate analyses the complexity of their solution well. Candidate reason about how optimising their solution further is not possible. Candidate write working code with good speed. Candidate has good testing/debugging skills. Overall, it would be hire call based on this interview performance. Notes: For the first problem: + TC clarified the maximum and minimum length of the link list. + TC clarified whether distance could be between any two critical points specifically minima-minima, maxima-maxima or minima-maxima. + TC tried to reason about applying the binary search on the input. - TC needed some help to understand that binary search won't be applicable. + TC mentioned that best we can try for is linear time solution. + TC shared the approach based on maintaining couple of pointers which was linear in time and constant in space. + TC wrote the bug free working code handling all edge cases and pointer manipulation. + TC came up with good test-cases. For second problem: + TC clarified maximum length of the array. + TC clarified if the values of array can be negative. + TC clarified minimum and maximum value in the array. + TC worked with examples to make sure they understand the problem. + TC mentioned that if there are multiple peaks, it's not a mountain array. + TC reason about why binary search is not applicable and linear time solution is best we can get. + TC shared approach and analysed the complexity for same. + TC wrote the working code in no time. + TC came up with good set of test-cases.
Feedback about Red Maelstrom (the interviewer)
Would you want to work with this person?
YesHow excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4
I liked the question choices since I have not seen them before and they test fundamental skills rather than require "tricks" to solve. In addition, you gave a very appropriate amount of nudging when I was thinking in the right/wrong direction. I also appreciate the advice you gave me for system design. Keep being awesome an awesome interviewer, and thank you for your time!
Interview Transcript
Red Maelstrom: So let me just paste the first question. So, yeah, you have a link list as an input. Head of a link list as an input. A node is a critical point if it is a local minima or local maxima, and as name suggests, local minimum maxima nodes which have values greater, strictly greater, or strictly less than previous, and a next node. So given such a link list, you have to return two things. Minimum distance between any two critical points and the maximum distance between any two critical points. Go through the question and the examples and let me know if you have any doubts.
Immutable Laser: Okay, so a node is a local maximum if the current node has a value strictly greater than the previous node and the next node. Okay, that makes sense. So it's like the maximum, it's like the peak node. So between those two nodes, and then a node is a local minima if the current node has a valley strictly smaller than the previous node and the next node. So that's like a valley. Note that a node can only be a local maxima minima if there exists both a previous node and a next node. Right? So if we're at the head or we're at the tail of a linked list, we cannot be a local maxima or a local minima. So given a linked list head, return an array of length two containing both the minimum distance and the maximum distance, where the min distance is the minimum distance between any two distinct critical points and max distance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return negative one. Negative one. So a critical point is a critical point, either a local maxima or a local minima. Okay.
Red Maelstrom: Yeah, it could be between any two critical points. It doesn't need to be between two minima or two maxima.
Immutable Laser: Got you. So it could be a local minima and a local maxima, or vice versa.
Red Maelstrom: Between two minima or between two maxima.
Immutable Laser: Got you. Okay, so we want the min distance and we want the maximum distance. Okay, so now, looking at the examples down here, the first example makes sense. The second example, so we have 531-2512 so if we look at the one there, the first one that we see, that's a local minima. And then we have a local maxima at five because two and one are smaller than five. And then we have a local minima at one, at that last one there because five and two are greater than the one.
Red Maelstrom: Right?
Immutable Laser: And so those are the three critical points. And so the minimum distances between the fifth and the 6th node. Okay, so basically, as we're going through the link list, we need to check, we first determine, is this node local or a local maxima or a local minima? And then we need to basically just find the minimum distance and the maximum distance. Okay, so just thinking out loud here, if we loop through the linked list and we recorded the positions, the indexes of the critical points, how can we get the minimum? And how can we get the maximum? Um, so we're looping through five, three, one, that's our first one, so we could keep track of the leftmost critical point. So right now I'm just thinking a lot about like a two pointer approach where we iterate through the first one that we see, we move our left pointer to that value. So we set that to the index of two and the value one for our left pointer, we keep iterating through and the next one that we find is five. And at that point in time, that's the next critical point. And since we found the next critical point there, we know that there's a distance of two. And so when we find a distance, we can keep track of the min and the max. So at this point, the minimum is two and the maximum is two. And then we move to one. And once we move to one, our maximum would become three. And then what we want to do is update the left pointer to move to the five and then store that as the minimum. Okay. And then the other thing that's, so that makes sense. Right now I'm just wondering if there's like a binary search approach, because there's are peaks and valleys, and when you have peaks and valleys, I feel like a binary search approach can work.
Red Maelstrom: But will the binary search work on linked list?
Immutable Laser: No, I think you'd have to convert it to an array.
Red Maelstrom: Right. If you are converting it, you are anyway taking linear time.
Immutable Laser: Right. So yeah, that makes sense. Or best case scenario, in that case would be o of n. Okay, that makes sense. So yeah, binary search approach wouldn't be valid for this solution. So I'm going to start coding here. So let's thinking about some constraints here. So for input, it looks like we get the head of the linked list, and then for the output, it looks like we're just looking for an array or a two element array. Is that true?
Red Maelstrom: Yeah.
Immutable Laser: Okay, cool. And that would just be the values of the two values. I'm just checking to see. So the min distance and the max distance. Okay, and then what is the maximum amount of items that we can see in the linked list?
Red Maelstrom: You can assume ten to the power, five. How many?
Immutable Laser: Sorry? Ten to the power, 510 to the power of five. And then minimum.
Red Maelstrom: It could be null.
Immutable Laser: Could be null. Okay. All right, I'm going to start coding here. So we have the head and we want to keep track of the index and the link list. And we also want to kind of have like a left pointer that we can update. So we'll start with that while we're looping through the link list, starting at the first node. So the first node we know can never be a critical point, right. So we probably want to keep track of the previous node at each step. So we'll start with previous equals none, and then we'll set the previous to the current node. And so this way. So the first step that we get in here, previous is none. But if we have a previous value, we can check to see. So if we have a previous value and we have a next value, we can check to see if it's a critical point. If we have a previous node and the next value, then we want to check. So if previous val is greater than, and I'm just checking here, so it would have to be greater. Okay. Yeah. So if the previous value is greater than the current value, and the current value is, or the current next value is greater than the current value, then we have a local minima. So we'll also check for. Let's do this is critical. Depending on how I want to organize this. I guess we'll just do one big if statement for nowhere it. Okay, so if the previous dev l is smaller than current value, end current, next dev l is smaller than the current val, then in that case we want to. So if, if our left is not set, we want to update it to that critical point. And then when we find the next critical point, then we want to capture our min and our max. So I'm going to initially set left equal to negative one. I'm going to add a couple more variables here. So, minimum critical point is equal to.
Red Maelstrom: Um.
Immutable Laser: Let's set it to this for nowhere. In this case, we found a critical point. Let's set left to none, actually. So if left isn't set, then we just want to set it here. So we want to store the index I. So left equals I. Otherwise if left is set, I think at that point in time we can, so it is a critical point. At that point we can measure the minimum critical point and the max critical point. And that's going to be I minus left plus one and the max critical point. Okay, so looking at our example here, we get to five, three, and then one. One is a local minima. And so we store that as a critical point. So we store that as our left index. And then we keep moving on, we get to the five. Since we have that left index in there, we subtract the difference, which is 01234 minus two. And so is that distance two or three.
Red Maelstrom: So the max distance could be between any two critical points. You're working on the second example or which.
Immutable Laser: Yeah, I was just looking at the second example there. Yeah.
Red Maelstrom: And the distance would be two, right?
Immutable Laser: I think so. Okay, so I don't need the plus one there then. Okay, if we find it, here's what I'm trying to figure out, is that we want to keep a reference to the farthest index. Okay? So if we're being greedy, we can keep a reference to the, we know that we always need the leftmost critical point to find our maximum, but to find our minimum, we always want to update that critical point. So we actually need two pointers here, not just a left pointer, but our left max and our left min. And we can do this using like a greedy approach where basically the first critical point that we see becomes the one that we use for a maximum and we never reset it. And then the min, we always update, but we do it after we, okay, so for the max critical point, that makes sense. And then we want to set the left min is equal to I. We always want to set it, but we want to calculate this will always equal zero. So we need to make sure we set the left min after we calculate the minimum critical point. But if we don't have an initial one, right, we do need to set it.
Red Maelstrom: That's correct.
Immutable Laser: The left men equals I.
Red Maelstrom: So left mean is leftmost point or a rightmost point or the last critical.
Immutable Laser: Sorry, the variable name is not great there. So the left min is actually the rightmost point.
Red Maelstrom: So this is literally the right, yeah.
Immutable Laser: We'Ll just call this the right critical point. I guess we'll call it right most critical point, just to be very specific.
Red Maelstrom: Right.
Immutable Laser: And this is left most critical point.
Red Maelstrom: The first critical point. Okay.
Immutable Laser: There we go. Okay, so using our example, let me just make sure I'm not missing anything else here. Then we want to return the min and the max. And then, and if it's, we'll do a little check here. So infinite there, and it that'll convert it from infinity. So in the case where we can't find one, we'll turn it from infinity or negative infinity into negative one. Okay, so now I'll go through the example here. I'll use the second example. So we go five, three, we get to one, we find our local minimum. So we set our, since the leftmost crip point is not set, we set that to I, and then the rightmost crip point is also not set. So we set that to I and then we find our min and our max. At this point, the min and the max are zero and zero. So we would update those.
Red Maelstrom: This will work for these examples. What if like link list has just one element or link list is null?
Immutable Laser: Yes. So those are some edge cases that we need to take care of. So if the link list is null, we just want to return negative one, negative one, and then what was the other one that you said? The other scenario, it just has one element. It just has one element. So if it just has one element, then we know that we can't get one either. So if head next is none, then we can return this and we can combine this into one statement.
Red Maelstrom: Yeah, so let's say that even in the normal case, like the second example, when will your while condition terminate?
Immutable Laser: So the while condition will terminate when we get to the end of the list. So we could terminate right before the end of the list. So we never need to actually look at the tail node. So we could actually say, well, current next year instead of current, because if there is nothing. Yeah. Is that correct? I think that's correct.
Red Maelstrom: Cool. Now it will work. Otherwise it will give like current next would have given you null pointer thing.
Immutable Laser: Say that one more time. Sorry.
Red Maelstrom: Now it makes sense. Otherwise current next would have given you the null pointer exception because.
Immutable Laser: Right. Yeah. So if next is none, so we are checking this here so we wouldn't see an exception, but we can actually remove that check. Now we can just do this since we're doing that in the while clause.
Red Maelstrom: Cool. I think. Yeah, this is good. Let's move to the second question.
Immutable Laser: Okay.
Red Maelstrom: I'm testing at the top. So you have an array as an input, and basically you have to return a true, if it is a mountain array or not a mountain array. Is an array which has at least three elements and there exists an index I such that the array is strictly increasing till that index and array is strictly decreasing after that index. And both of these increasing and decreasing parts should be non empty. So yeah, again, go through the question and let me know if you have any.
Immutable Laser: Okay, so given an array of integers, array return true if and only if it is a valid mountain array. An array is a mountain array if and only if array length is greater than or equal to three. So we need at least three elements. And there exists some I with zero is smaller than I is smaller than a rate out length minus one such that, okay, so example one, it needs three elements, so that's false. Example two, we have three elements, but we have no peak because five is equal to five and the last five would need to be four or less to make it a valid mountain. And then example three, we have 03213 is a valid peak because zero is less than three and two is less than three. Therefore it's a valid peak.
Red Maelstrom: Yeah, it's not about just one peak. It should keep on decreasing also. So this is not, for example, if this would have been like this, it would not be a mountain array.
Immutable Laser: Okay.
Red Maelstrom: Basically, once it start dipping, it should keep on dipping till the end of the array.
Immutable Laser: I see. Okay, so there can only be one peak basically in the array. If there's more than one peak, it's not a valid mountain array. So the easiest way to do this would be an ov n operation where we loop through the array and it, we validate that it's increasing and then decreasing in some way. Looking at example three, we make sure that it's increasing initially, and then when it starts decreasing, it never stops decreasing. That part seems pretty straightforward. I wonder if there's a binary search solution here that we can do in log n time instead of o of n time. It, it. So if we did a binary search, what are we looking for? We're looking for the maximum in the array. So the highest value. But even if we find the highest value, we have to confirm that every element is still either increasing if it's to the left, or I guess if we're starting at the highest element.
Red Maelstrom: Right. Even for finding the highest right, you're not sure because you are not guaranteed that this is a mountain array, right? It's not always guaranteed.
Immutable Laser: Yeah, so this binary search wouldn't work for this. Okay, so I think an oven operation here where we iterate through, we verify that it's increasing and then decreasing would work so I'm going to type up that solution.
Red Maelstrom: Mmhmm.
Immutable Laser: So the inputs in this case are going to be an array and the outputs are going to be a boolean. Are the inputs always integers? Is it an integer array? Are you there right now? I can't hear you.
Red Maelstrom: Hi. Yeah, I lost you for a bit. What was this actually?
Immutable Laser: Is it an integer array for the input?
Red Maelstrom: Yeah, you can consider it as an integer array, but it could be negative also.
Immutable Laser: Okay, and then what are the maximum values of the integers in the array?
Red Maelstrom: I can assume ten to the power six and ten to the power minus six. Minus ten to the power six.
Immutable Laser: Oh, did you say they can go negative too?
Red Maelstrom: Yeah.
Immutable Laser: Okay. If all of the integers are negative, can we still find a mountain? Yeah. Okay, just making sure. And then what is the maximum and minimum length of the array for the constraints? I think I lost. Never mind.
Red Maelstrom: Yeah, so basically your array length could be ten to the power seven, and your increasing part could be ten to the power seven. Like just one in a valid case, your increasing part could be of length two only and your decreasing part could be of length two only. In the extreme case, yeah. So it should be non zero increasing or non zero decreasing. It doesn't need to be like in between. That peak of a mountain array doesn't need to be in between of the array.
Immutable Laser: Okay, sounds good. So we start looping through the array. I'm just going to handle some of the edge cases first. So if the length of the array is smaller than three, we can just return false right away. So this guarantees that we can start from the first node and end before the last node or last element. So we can check before and after. So if. So in this case, if the left node or element is smaller than the current element, and the current element is greater than the next element, then we've found our mountain. But then after that, we just need to make sure that everything is decreasing after that, because before. Okay, cool. We found our mountain. Just make sure everything is decreasing. So we could say what we could do is just use a mountain index equals set the mountain index and then break and then do one more for loop to finish it out. So we would start from the mountain index plus one. So if we never find a mountain, we need to quit out as well. So if mountain index is equal to negative one, we need to return false. And then now we just need to make sure that the array is decreasing. And so.
Red Maelstrom: Mmhmm.
Immutable Laser: We can use the previous value because that should be the greatest value initially. Why is this not happy. I'm not sure why this is not completely happy, but, um.
Red Maelstrom: Because you have not declared I right.
Immutable Laser: Oh, right. Sorry, I messed that up here. There we go. So the previous value is equal to the array at mountain index. And then there we go. And then, so before we reset the previous value, we can use that for our current iteration and make sure that the array at I index is smaller than the previous. And if it's not, we want to return false. And we can return true at the very end because that will indicate that the array is decreasing. I'm just trying to think if there's any other edge cases that I missed here. So we make sure that the array is of length three, the first mountain index that we find, we just make sure that it's decreasing. After that, if we can't find a mountain index at all, then we return false.
Red Maelstrom: That's also correct.
Immutable Laser: Cool. Yeah. I can't think of any other edge cases at this point. It, yeah.
Red Maelstrom: Can you look at this condition once? Line number 25?
Immutable Laser: Yes.
Red Maelstrom: Okay. Sorry. You already have length minus one. Okay. So it won't go out of bound.
Immutable Laser: Yeah.
Red Maelstrom: So that is taking care of mountain array. Mountain index is mountain one.
Immutable Laser: Oh, actually there is one thing I missed on line 33 there. I want to go all the way to the end of the Ray to make sure it's not increasing at the very end.
Red Maelstrom: Right. Okay. Yeah. Okay. You're looking at the previous one, so you have to go to length. Okay.
Immutable Laser: It.
Red Maelstrom: Is control, I think. Yeah, this makes sense. It will work. Yeah. So you don't need to run through every test case, but can you think about different kind of test cases which will make sense for this code?
Immutable Laser: Yeah. So I would want to do some happy path edge cases. So cases where the array has one mountain, I'd want to add test cases where there's multiple peaks and verify that it returns false. I'd want to verify that if the length is smaller than three, that it always returns false. If, for example, we had no peaks. Right. So we just had like example two there where it's like only increasing or only decreasing that it always returns false.
Red Maelstrom: Cool. I think this is good. I don't have any other questions, so let's pause for feedback. I think you did really well in terms of all of the things. I really like the way you clarified the question and I really like the way you shared your approach before going into the implementation details. And the speed of implementation is, no doubt, is really good. So, yeah, I think based on this interview, I would have definitely given a strong hire call. Only thing which I would recommend, I would recommend these to only candidates who have good implementation skill, is that once you write a code, think about opportunity to modularize it a bit. For example, in the first code, I think its critical point is something which you can extract out from line number 88. You could make it that condition as one function. Yeah, that is only small thing I say, but do it at the end. Don't think about writing modular code right from front, because at meta the speed is important. Yeah. So that is the only thing in terms of improvement I would suggest, and I think other things you might be aware about meta interview is that coding interview does not indicate level. So if you are giving a coding interview at meta, so interviewer just has one thing to talk about, whether this candidate has good enough skills, coding skills for meta or not. It does not have any indication about which level the candidate should be hired upon. Only system design and behavioral interview decides the leveling part. So that is the thing which you can keep in mind. Yeah, I think along with coding do focus on system design. And the real part, I think one thing which in the part is important to keep in mind is meta has very back driven culture. So whenever you're talking about any projects or your previous example, if you can conclude those examples with numbers, let's say for example, how much cost it saved you for your company because of this. Or in terms of request, also like previously, it was gathering only 2000 requests. Now with the same resources, it's gathering three and a half thousand requests. If you have such quantifiable numbers to conclude your examples, doing that would be a great, because meta do have that impact driven culture. That's the one thing. And in terms of system design, if you can think about in terms of data privacy. So for example, if you are being asked to design a Twitter kind of a thing, right? Asking questions like whether do we need data localization, the data needs to be in the same region where the user resides. Is there any requirement against data like policies against data retention? Do we have to make sure that data gets deleted after a certain amount of time? Asking these questions will also make you more aligned towards what meta really values. These are the small tips I usually try to give a candidate who apply for system design.
Immutable Laser: While I have you here, are there any other system design tips that you can give me off the top of your head? Yeah.
Red Maelstrom: So one is this, that do talk about data privacy and data localization, then what you can generate. This is very meta specific thing. As an interviewer, we do look out for the four different aspects from a candidate during the interview. One is ability to clarify the question. So it includes functional requirement, non functional requirement like resource estimation in terms of qps, or memory requirement in terms of how much storage would be required, those kind of things. That is one part of evaluation, like how well you can scope out the problem. Second part of evaluation is whether candidate can at least come up with a working solution, whether it's not about scaling it up, whether at least he can think about something which will work for a given problem. So that is a second evaluation. Third is like scaling up for the meta kind of scale traffic. So basically how well your solution can scale up. The fourth is technical communication. So how easily you can articulate your ideas, or how easily I can communicate with you if I have any follow up questions or those things. So these are the four areas on which usually interviewers evaluate candidate on I usually recommend to follow this framework, like first thing, functional requirements. Second, non functional aspects of the system design, writing it down. Third is estimation. Then these three things takes care of your first evaluation point, scoping out the problem. Then I usually recommend to write down API specs, like what are the APIs you think about functionalities that needs to be there, and what is the request response for that. And once you have API design, I recommend to come up with very high level context, zero diagram about very high level components like these two parts, API design and high level design takes care of the second aspect of evaluation, which is like coming up with a working solution, right? And once you have that working solution, I usually recommend people to write down key aspects, key problems which they can think about. Let's say, for example, if I'm asking you to build an Uber, right? Once you have a system like high level design, you can think about key problems which you can solve about. One of those things could be pricing, how you decide the pricing of your cab ride, how your driver allocation algorithm, or it could be about whether do you want to prioritize customers or those things. So you can come up with very high level problems, like different kind of problems which you can try to solve, and then go back to the interviewer and ask what area you want me to go deeper into. And that's from where you try to get a point for your third evaluation point, which is like scaling up the system. We'll talk about schemes and everything. Okay? Yeah. Cool.
Immutable Laser: That makes sense. Thank you.
Red Maelstrom: Do you have any other questions?
Immutable Laser: I don't think so. At this point. I do have a Facebook interview, phone screening coming up. So I'm just preparing from a technical standpoint initially, and then.
Red Maelstrom: Sorry.
Immutable Laser: Go ahead.
Red Maelstrom: Yeah, please. Go ahead.
Immutable Laser: Yeah. I was just going to say that if I do get to the onsite interview, then I'll need to focus on system design. But right now, I'm focused primarily on just getting through the phone screening. Cool.
Red Maelstrom: Awesome. And for phone screening, I'd think coding is good enough and that's the right strategy to do.
Immutable Laser: Cool.
Red Maelstrom: Awesome. All the best for your phone screen.
Immutable Laser: Thank you. I very much appreciate it. And, yeah, have a good day.
Red Maelstrom: Yeah, thank you. You too. Bye.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
