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 Indefatigable Awesome (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 and edges cases and expected behaviour in case of edge-cases before jumping into solution. Candidate makes sure they are communicating their thought process while thinking about approach and implementing the their approach. Candidate used good naming convention for variables. They could have used better naming convention for method name instead of "Solution". Overall, it was good speed of implementation and would be happy to give a hire call. Note: + TC clarified what should be output in case if link list has less critical points. + TC clarified if the distances could be between minima and maxima or needs to be between two minimas or two maximas. + TC shared their approach where they first find the indices of all critical point and then loop through those indices to find the min distance and max distance. + TC analysed the complexity of their solution as linear in terms of space and time. + TC also mentioned they can think about optimising the space complexity once they implement the code. + TC wrote the working code for first problem. - TC missed null check for head of link list. + TC improved the space complexity by using few pointer rather than a list for all critical points. + TC clarified for second problem if mountain array can be first decreasing and then increasing. + TC also clarified if it needs to be strictly increasing and strictly decreasing. + TC shared their approach that they first check for increasing phase and then for decreasing phase. + TC wrote code in no time. - There were few issues with their code which they corrected when pointed out. + TC correctly analysed the time complexity to be linear and space complexity to be constant. + TC came up with good set of test-cases for second problem.
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
Interview Transcript
Red Maelstrom: Yeah, I saw like you booked a meta interview. So basically, meta usually has two coding problems in 45 minutes, and we'll try to do the same. So we'll spend like 45 minutes on coding problems and last 1015 minutes for feedback.
Indefatigable Awesome: Okay, yeah, sounds good. I actually have a meta interview on 9 January and I'm thinking of rescheduling it, but that depends on how well I do the mocks. This is the first mock that I'm taking. Sure.
Red Maelstrom: So, yeah, I think this is the problem you have ahead of a link list as an input. And basically a critical point is a node in a link list which is either local minima or local maxima. So local minima, as name suggests, is a node which has value strictly less than its previous, and an x node. And local maxima is a node which has value strictly greater than its previous and an x node. And basically as an output, you have to return two things. One is like minimum distance between any two critical points and the maximum distance between any two critical points. To go through the problem and the examples and let me know if you have any question.
Indefatigable Awesome: Yeah, sure. To understand correctly, given a link list head, return an array of length to main distance on max distance, where main distance is the minimum distance between any two distinct critical points, minus one. Okay, so that's why the first example is minus one. Minus one, because there are no zero. Okay. And in this case, so over here in second example, one would be a local minima, right? Because it's lower than its element on the left and right.
Red Maelstrom: Exactly.
Indefatigable Awesome: And same here. Five would be your local maximum. So the distance should be the minimum distances between any two distinct critical points. So critical points are both minima and maximum. Both are considered critical points, is that correct?
Red Maelstrom: Right. So distance would be between either minima and maxima or between each other.
Indefatigable Awesome: Okay, so distance can be between a minima and a maxima, or a minima and a minima, or a maxima and a minima, right? Correct. Okay, got it. I see. And can this link list have negative values?
Red Maelstrom: Yeah, it can.
Indefatigable Awesome: Okay, I see. So the one thing that is clear right off the bat is that I'll have to traverse through all the elements at least once I'm thinking, and I have to store the previous value in order to know whether the current element I'm looking at is actually greater or smaller than the previous one. And I guess it should be possible to do it in one pass for example, when I'm looking at three, I'm basically comparing five and one and seeing if it is actually greater than both the element left and element right. And if it is greater than both, I'll mark it as a critical point, store its index, and if it is greater than both, again I'll mark it as critical point and store its index. So now I will have the index of all stored in somewhere. And then basically all I have to do is get the maximum difference between two indexes and the minimum differences between the two indexes. And if, let's say there are no maximum minimal, like in example one, then in that case you can just give minus one. Minus one. I guess that can be when the link list is small, like just two elements. Or it can be when it's strictly increasing or strictly decreasing values. Cool.
Red Maelstrom: I think yeah, that works. What would be the complexity, time and space complexity of your.
Indefatigable Awesome: I think it would be on. And space complexity I guess would definitely be less than on, but I'm thinking if, yeah, it will definitely be less than on, but given that it can be very dynamic, I'll have to say on. I'm sure that once I write it, I can look into optimizing it so that it gets lower. But right now with the current approach in mind, I think the space complexity is going to be om. Cool.
Red Maelstrom: Yeah. Let's write a code. And then.
Indefatigable Awesome: I'm only given a head, right? Okay.
Red Maelstrom: Yeah, only head of Olympus.
Indefatigable Awesome: Okay. So looking at that, I would say that one is an array that stores all the indexes of all the critical points. So let's say it, critical point index. And now what I have to do is prev or Int. And next, I guess I can make this the head. Yeah. So basically for each element, as long as there is a next element, which will be the, I guess this can be head next and head next. So as long as there is, like I'm going to do while next and keep on going as long as there is one. So while next, I guess I'll have to, or I can just do one. And this is the current position, I will keep incrementing it as my pointer moves forward in the link list. And so I'm thinking if there is any edge case, but I think I'll return minus one, minus one if there is no next. Makes sense. So I'm assuming the value can be, I can get the value by just inputting Prev. Well, of the lex list, of the node, of the link list.
Red Maelstrom: It doesn't change.
Indefatigable Awesome: Or. So basically either it is a local maxima or minima. I am going to. One thing I should have asked is that it is only when it is less or more. I shouldn't put equal here, correct?
Red Maelstrom: Yeah, that's correct.
Indefatigable Awesome: You. So now we have moved forward and we keep going. And now we have critical point index array full of all the local maximas and minimas. So obviously the first answer would be easy. Like max distance would be easy. It would be. Would be like point index zero. And yeah, this would be the distance. Now, as for min distance, that's where things get tricky. For min distance, I have to basically loop over all the critical point indexes and after that find the shortest distance. So yeah, I guess just looping over would be fine for in it, just set it as max distance. And after that's it. And distance is equal to distance. Now I can just return indistance and max distance. Yeah, I guess that's going over it, but I think I'm done. Yeah, I think that's like going over a case. It basically loops over 132-2377 so because three is. Have I done a mistake here? No, I think that's fine. First, three is greater than previous value and greater than next value. It will get stored. So let's say. So we have stored two and then again two. Then again this 3567. And in this case the max distance will be five minus two, which is three. And the min distance will also be three. And the answer will be three. Three. Is that righteous? Yeah, I, I think I'm done. Yes.
Red Maelstrom: What if link list is empty or it does not have more than one node or something?
Indefatigable Awesome: Sorry, can you repeat?
Red Maelstrom: What if link list is empty?
Indefatigable Awesome: Will there be if link list is empty? Okay, yeah, if not next or not head. Yes, in that case, just written minus one and minus one. Makes sense. And in every other case I can basically add if not current as well. But I think that would be, yeah, I guess in that case, next will also not exist.
Red Maelstrom: Okay, let's try to optimize for space now.
Indefatigable Awesome: Okay. It I can have basically the first critical point that I encounter and then the last. And then along with that like Rev, Rev C and Curt C. That's it. Instead of basically having the entire array critical point IDX, I can basically have these four points. For each iteration I will check the index of, I'll store the index of prev critical point and then current critical point. And after that I will just store it like this in the minimum distance. And through that I will get the minimum distance. The first will be if there hasn't been a first. Then that's it. The last would be after the loop has ended. I will just put the index of currency in the last. So that's it. That sounds good. Should I go ahead?
Red Maelstrom: Yeah.
Indefatigable Awesome: And that way the space complexity will be one.
Red Maelstrom: Understood.
Indefatigable Awesome: So right now I'm going to put all of these as. Actually, that doesn't sound right. Equals to pause. And if, and if we have ref c, this is where I get the local minima. It. I guess I need to initialize these values minus one for now. So last, minus first. Yeah, done. Hello? Are you there? Hello?
Red Maelstrom: Yeah, I'm just looking at the code.
Indefatigable Awesome: Okay, sorry.
Red Maelstrom: Yeah, I think this will do. Let's move to the second question.
Indefatigable Awesome: Okay, great.
Red Maelstrom: I'm again pasting it on the top.
Indefatigable Awesome: Sure.
Red Maelstrom: So you have an integer array and you have to return true if it is a mountain array. The mountain array has at least three elements and there exists an integer index I such that the array is strictly increasing till that index and array is strictly decreasing after that index.
Indefatigable Awesome: I see. Okay, so will it always be a maxima or can it be a minima as well, like an upside down mountain?
Red Maelstrom: No, it will always be maximum.
Indefatigable Awesome: Okay. Basically at one point decreasing is true. Like in the third example, it starts from zero, three. After that it's just decreasing, decreasing, decreasing. If we had seen if, let's say over here, there was a value ten at the end, that would be false, correct?
Red Maelstrom: That's correct.
Indefatigable Awesome: I see. Yeah, that sounds simple. Over here I can just, in this case it cannot. Okay, yeah, that sounds simple. I can just go through the solution. But basically I can basically have two boolean variables. Actually three boolean variables. First should be increasing, and as long as the previous value and the current value are increasing, it's true. Once it starts being false, it has to stay false. If it is true again, then basically I will return false as an answer. And if we have reached the end and it's still decreasing, then the output will be true and that should be it. Solution. And let's say we have arrsing equals. And in order to see that, I will basically just loop over and if you it, the other is flipped equals to one. So flipped can only happen once. Basically from decreasing, can only flip to true once. And once it's flipped, if its value increases, two increases, it goes more than true. I will simply return false at the time. And at the end of the loop, if the value has flipped more than once, I can just return true. Sorry. If the value hasn't flipped more than once. If it's not equal to two, I will just return false. If it is equal to two, I will return true.
Red Maelstrom: So, understood.
Indefatigable Awesome: I think one thing I'm missing is keeping track of was it previously decreasing or not? For example, like zero, three, it is increasing is false. It. Yeah, I think so. But while true, it. Yeah, I can actually have this. Yeah, this means that over here, while increasing. So this has to be true at least for one valued. Now, if I is greater than if I equals zero, meaning there hasn't been any increase at all. Return false. And now, while not increasing, because once it has been set to false, we'll again continue. And now what I have to check is if the if I equals, it's false. So if I has reached the end and the increasing was false till the end, it means that we have passed the case and it's true. Otherwise the value of increasing changed, in which case we return false. Basically, we cover all our bases. And I think over here it can be an index error. So just for that, if I equals ARR. Yeah, just one edge case where this can actually keep on increasing till we reach the end of the array.
Red Maelstrom: Do you want to go through the example number three on your code?
Indefatigable Awesome: Yeah, something. So zero, three to one, we have increasing equals false. And first we go through this loop. Arri is less than arri plus one.
Red Maelstrom: But you won't go into that, right? Because increasing is false.
Indefatigable Awesome: Oh, sorry. It should start with true. Yeah, basically zero and three. And if we, we start from here, we, and then we reach two when I is one. So we compare three and two. Given that that is false, we exit. Then we check if I equal equal to zero, which is not the case. So we move on to this. At this point, increasing is false. So as long as the value of I is less, that means the value of I here is two. We check again the same situation. And because increasing is false again, we increment I and it keeps on going until it reaches the length. 1234. Yeah, until I reaches four. And then after that we check four equals I, which is four equal, equal length of array. And then we return true and. Yeah, that's it.
Red Maelstrom: Got it. What if like array is entirely increasing.
Indefatigable Awesome: In that case? Yeah, in that case, this case will handle it. So basically, as long as it is increasing, I will keep on increasing and it will reach the length of array. Like let's say it's four elements. So four and it will return false.
Red Maelstrom: Yeah, but if your I is already, length is equals to length of array, you won't go in for while loop. It could be array out of bound. Index. Out of bound.
Indefatigable Awesome: Right. So I increment I here. Like I starts from zero. Okay.
Red Maelstrom: Yeah. But at the end it would be I minus length minus one.
Indefatigable Awesome: Right.
Red Maelstrom: But I plus one would be the length of array.
Indefatigable Awesome: Oh, I see. Yes. Good point. Yeah. I can actually put this here. Yeah, the good point. Yeah. Good catch. And in can happen here as well. I think if it is strictly decreasing, then I equals. Yeah. Does that look okay? Or am I still missing something over here?
Red Maelstrom: Technically, do you want to take a pause and kind of think about the test cases which comes to your mind?
Indefatigable Awesome: Yeah, I think right now also it can go wrong. Because over here what I'm doing is I plus one. I'm actually thinking that instead of that I can just go for I minus one and I here and start I with one here. And what would happen in that case? In that case I would be able to just simple. But I'm thinking about it right now. Not sure. Same with here's. It's. Let me just go over 1234 as well as 4321. Both these cases. Let's see. U. So increasing is true. And after that I is one. So one and two are compared. Then two and three. Then three and four. And I keeps increasing. If I equals, which does happen at four. In case of strictly increasing, it works. Now, in case of strictly decreasing, we actually skip through this part and we check over here. It should be one. I equal, equal one. False. And. And now we are looking at. Yeah, I think it's fine.
Red Maelstrom: Okay. No, I don't have any test case in my mind which will fail. But yeah. I would like you to consider about. Think about test cases which comes to your mind for this problem and the code.
Indefatigable Awesome: Yeah, other than this, the test cases I'm thinking of is where it is where there are multiple points. So 12345 and then again one and then nine. So in case like this till five, everything will be fine. It's five. Everything is fine. After that we go to not increasing and then increasing flips. But at the last, when I is 123456. When I is six, the increasing flips again and 123-4567. And given that the length does not match, I. This last condition is not true. So we return false. Yeah, I think that's the longest scenario. Like the scenario in which the entire on will be passed to return false. Thinking of the edge cases. Given that I'm checking for length here, I think it should be fine. Now it can have super long length. That is fine. Yeah, I'm confident that this will work.
Red Maelstrom: What about if array is strictly decreasing right from beginning.
Indefatigable Awesome: Strictly decreasing as in 4321, right?
Red Maelstrom: Oh, your I equals to equals to one will take care of it. Okay.
Indefatigable Awesome: Yeah.
Red Maelstrom: Sure. I think, yeah, this should work. What would be complexity of this?
Indefatigable Awesome: The time complexity will be on and space will be one because I'm not really creating any array, just these variables increasing. Just the variable increasing and I so one. Cool.
Red Maelstrom: Awesome. Yeah, I think I don't have any other question. Let's pause for feedback. I think you did well in both of the problems by asking clarification questions and making sure that you understand the problem first and then only jumping into the implementation details. So that's a good thing to do even in the actual interview. Also, and even while you are thinking about how to do it, you were communicating about it like your thought process. Not just like you thought about solution and just sharing the solution, but even while thinking about it, you were talking to me about what are you thinking and all, which is good. You also made sure that before writing the code you get an approval from me about approach and complexity and the correctness of the approach. So that is another good point because I have seen candidates implementing a wrong solution or approach in their mind and wasting time. And at the end there is no time left for thinking about the right solution. So I think what you're doing is a very practical thing and you should keep doing that while writing code. Also, you are communicating about what you are trying to do here and things like that. One thing I would suggest you to think about is rather than having a very generic function name solution, think about a function name which is more related to the problem itself. So for example, in the second problem it could be east mountain array. For the first problem, get mean and max distance or something like that. That would be a small thing, it wouldn't hamper much, but it does create that mindset that the candidate has practiced a lot but don't have much hands on in current job, something like that kind of impression. So I would say that it's good to use a meaningful name rather than just solution. Yeah, I think that is the only point. In terms of code quality I would say you should think about. I'm thinking like in the first problem you did not think about link list being empty and things at the initially. So make sure that you think about those corner cases upfront. Similarly, in the second problem, there were a few issues with different kind of test cases. So in the actual interview, if you have enough time after your completion, you're done with the code. Right. You can go ahead and try to run your code against some sample test case, or you can try to come up with a few test cases of your own. So that creates a good impression that you are not just a guy who just writes a code, but you do actually care about whether it's working or not. So that's a differentiation between a college grad and the person who has industry experience. I'm not saying that do it for first problem itself, but at least for the second problem. If you have time, right after writing your code, you can ask interviewer like, do you want me to go through the test case or do you want me to think about some test cases?
Indefatigable Awesome: Okay.
Red Maelstrom: Yeah, but, yeah, depending on this interview, I would have given a higher call for e four. I'm guessing e four is something like which you're targeting at meta.
Indefatigable Awesome: Yeah, I'm targeting both e four and e five.
Red Maelstrom: Okay.
Indefatigable Awesome: I'm just not very confident right now. Although this problem went well. Right before this, I was practicing some other problem like subarray sum equals k, and I was struggling with that a little. So those are the problems I'm working through. In case of backtracking, I currently work at Google, so I've already cleared the interview two years ago. So I'm just looking for a change. So that's why going.
Red Maelstrom: How many years of experience you have.
Indefatigable Awesome: In India, I worked for like four years and in just, just one and a half.
Red Maelstrom: Okay, cool. Then I think for e five, I think coding wise, it doesn't matter whether you are e four or e five is what you're targeting. Because coding interviewer at Meta don't have a labeling guideline. So basically, if I am taking a coding interview for candidate, I just say that whether this candidate has a coding skills which are required for meta, I don't specify the level. Another thing is, but for the e five, I think the depreciating factor would be your behavioral interview and the system design.
Indefatigable Awesome: Yeah, I'm going for machine learning system design. So yeah, right now, first I have the screening interview, the 1 hour screening interview on 9th. So right now preparing for that.
Red Maelstrom: Cool. Awesome. Yeah. Then don't worry about a lot about leveling part and just practice coding. Those are the feedback and all the best for your excellent. If you're online.
Indefatigable Awesome: Yeah. Thank you so much. Thank you. This was very helpful. Yeah, cool.
Red Maelstrom: Have a nice day. Bye bye.
Indefatigable Awesome: 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.
