interviewing.io

Python Interview with a Meta/Facebook engineer

Watch someone solve the find the minimum and maximum number of nodes between critical points problem in an interview with a Meta/Facebook 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

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].

Interview Feedback

Feedback about Propitious Dromedary (the interviewee)

Advance this person to the next round?
Thumbs upYes
How were their technical skills?
4/4
How was their problem solving ability?
4/4
What about their communication ability?
4/4
Strengths: + TC clarified if the input could be empty link list. + TC shared the observation that there could be duplicate element in the link list. + TC asked if there is any limit on size of link list. + TC mentioned that if they can find all the local minima and local maxima, they can compute the answer. + TC mentioned that maximum distance would be between first critical point and last critical point. + TC shared the observation as this is link list we can not scan it from end. + TC mentioned that they can solve in linear time by storing the position of all the critical points with additional space of O(n). + When asking if they really need to sort this list, they identified that they don't need to sort. + TC correctly analysed the time complexity to be linear and space complexity to be linear. + TC took pause and asked if they should try to optimise the space complexity. + TC mentioned they need store the first and last position of critical point and they can optimise the space complexity to constant. + TC came up with right method signature. + TC used the optional to efficiently deal with null. + TC identified the edge case that if list is empty or of single node. + TC tried to write the modular code with helper method to check if current node is local minima or local maxima. + TC was able to complete the implementation for the first problem. + For second problem, TC clarified if the two input nodes can be anywhere in the tree. + TC shared the approach where they would update the parent pointer for each node in linear pass and then find the paths from given nodes to root. + TC correctly analysed that space complexity would be linear and time complexity would be linear. + TC explained their time and space complexity analysis by going through all the steps in their approach. + TC is clearly communicating what they are doing while writing the code for their solution for first problem. + TC is done with the code within the time limit. + TC came up with really good test-cases for the second problem. Improvement Areas: - TC mentioned that they would need to sort the positions list. - TC needed some help in implementation details for first problem. - TC took more time than expected for first problem. - Did not have enough time to discuss alternative approach for second problem.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?
Thumbs upYes
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
N/A

Interview Transcript

Red Maelstrom: Okay, cool. Awesome. So, yeah, let's start let's start with the coding problems. Like we will go through a couple of coding problems as it would be in the actual meta interview.
Propitious Dromedary: Yes, sure.
Red Maelstrom: Like 10-15 minutes for feedback.
Propitious Dromedary: No problem. Cool.
Red Maelstrom: Let me just paste the first problem. It yeah, so basically this is the problem. Like you have a link list and a critical point in link list is defined as either local maxima or local minima. So local maxima is the node where the value of that node is smaller than both of its previous and the next element and local maxima and the same like minima. So basically you have to find out the minimum and the maximum distance between any two critical points in the link list.
Propitious Dromedary: Okay. The minimum and the maximum distance between any two critical points in the link list. So given a link list had return an array of length, two containing min distance, where minus is the minimum distance. Between any two distinct critical points. Max is the maximum distance between if there are fewer than two critical points, return minus one, minus one. Okay. Local strictly greater than the previous node. Okay. Strictly smaller if there exists both a previous node and an x node. Oh, okay, I see.
Propitious Dromedary: So can the input so the input be an empty list?
Red Maelstrom: That's a good question. Yeah, it could be.
Propitious Dromedary: Okay, so I see from the example that not all the elements in the list would be distinct. Would be distinct. Okay is there like any constraint on the. Length of the linked list?
Red Maelstrom: You can assume that it would be ten to the power six.
Propitious Dromedary: Okay, so I think when I. Think about so there is one maxima and then one minima and we need to find both of them, right? So because we are going to return both of the min, so we are going to find the min and the max distance. So I think this can be like as I think about it, it can be reduced to a problem where we need to find or we need to find each maxima and minima in the list. If we can find it through a scan like all the Maximas and Minimas, then maybe there is a method where we can keep track of the. So if we get the earliest Maxima and Minima and the one which comes from the so if we have the earliest maxima and minima and the one that is nearest to the end, then definitely we get the maxi distance there that can be used to find the maximum distance between two critical points. Once we start scanning it from the beginning and we notice there is a maxima or a minima at a certain node, we just note it down because it is a list. So we can't just scan the list from the end here. That is another point. So can't just scan the list from the end. I think the method should be somewhat like include somewhat like scanning the list. Now let's see, how can we scan first thing is first thing I notice here is that we can have a function which can tell like given a node, if it is not the first or the last node, we can check if that particular node is either a maxima or minima. We can just write a function and that function would be like an order of one time. So we can check this For all. The nodes from the nodes between the first and the last node because the first and the last can't be the critical points anyways. And that will take us order n time to check each of this node now to check the nearest and the furthest. How can we basically do that? I'm just thinking is there a method we can just solve this whole problem in order end time? I think one trivial way we can just like we can have the positions of all the critical points basically which are either maxima or minima. We can store it in an array or something. Of course that will take order and extra space and then we can just maybe sort it out there. And when we sort it out then the difference between the first and the last is the maximum distance for sure. And then we can just scan it to get the minimum distance. But it will take because there is sorting involved here. This trivial method would take roughly like order n extra space and order n login overall time because we are sorting it. So this is just a trivial method. So now just quickly thinking about what can we do because anyway.
Red Maelstrom: Do you need to sort this?
Propitious Dromedary: Yeah, I'm just thinking about like how can we avoid sorting here. Okay, so yeah, I think we do not need to actually sort because when you'll be scanning we just will just store it like store the critical point in the order. Right? So there is no need to sort and then we can scan it. As I said, this is actually not required. So it is not required. So the time complexity will be order n but the space, there will be extra space for sure here. So just like thinking a minute about whether we would need this extra space or can we do it in the space that order one space or something. Do you think we should think in that direction or should we go to that? Okay. So here, let's store the first one and when the next one comes. So if we store one critical point we can store that one, the previous one. Yeah, we actually don't need to store it because we can just actually compare the distance. The first one, we just store the first critical point, right? And we can compare it from the one next one that we get. And we should store the first one that we observe, the first critical point, and we should store the one the second one also. And we can keep updating actually, the difference we should keep updating the distance between the first. So the first one should be stored somewhere, and the last one should be stored and in the middle, we can just keep an iterator for the point, like between the current.
Red Maelstrom: Do you mean the last you encountered till now or the last in the link list?
Propitious Dromedary: So last year encountered till now.
Red Maelstrom: Okay, I think that would solve your problem. Let's start with the code.
Propitious Dromedary: Yeah, sure. So. Max let's name the function some max mincritical difference or something. Sorry. And we have here a list which. We can say it's anything like node like a beginning of node of the list. And it is a list of int and that we are returning is we are returning a list actually. So it's a list of max initially.
Red Maelstrom: What do you mean by okay, node is a variable, right? And the list of ant, will it be list of ant or some structure or something?
Propitious Dromedary: Oh, sorry. It will be a list in order. Yeah, it's a structure. We can have an array of length two, right? So we will first check also here there will be some cases where the list is empty if not node or not node next. This means that if the list is of length. So if the list is of length zero or one so we have to return, I guess minus one. And minus one here. So we can return it here itself. We can say edge cases here now. Can just write function. Def like just. To separate the logic here. So this head of the list will be node here and we can check with the beginning node what head of the list will be node here. So we now know so we can start from node next. Actually we need to check at each point what will be the condition that we'll need to check? Because we know there exists a previous node here but there might not exist next node next node here. And we need to continue till we leep encountering node next to the head. Because that means that we are still in the middle of the list. So while this right, so this will be the loop which will run N times. And now we need to check the condition. So is minimum or like we can write two separate functions for that. Given a node. Here, we can write Bool the same as maximum. Yeah, so yeah, also Bool and yeah, so first writing this function but we don't have the what happened? Sorry. So when we get this node, we also need the previous value, right? So we should store the previous value like the previous node also here. We can write this instead as a previous encurrent or something. So to name it better just to name it better, we have previous as the node and the current as node next. Now we are going to trade while there is current next while there is. This so we have previous and current and when we iterate, we can update these nodes anyway. So here we will have do we need to pass all? Can we do it with? We just need to make sure. If we pass previous in that function, we will only need to pass one element. Otherwise we need to pass both the previous and the current node. So think what will make the code cleaner is if we pass both because it will make logic easier. So although we will be actually doing. Double the work but I think so. When we get this, we have if. Previous value so it's minimum, right? So is greater than strictly greater than. Dot current value and current value and current next valve strictly greater than value. Sorry, we return true, otherwise we return false. Similarly here if this dot value is less than if it. Now here because we already defined our previous and current. What we can do is if is minimum is minimum of areas and current r is maximum. So should we check it differently? So this is a mix of okay. So the critical point is either maximum or minimum. So yes, so we have this. If this is the case, then we can store it. So we should store the first one for sure. So how do we make sure when we encounter the first critical point. We store it just in a separate variable. So first we should define the min distance we want to return and we can define it as something like because it's. So this is the min distance. Variable that we. For just getting the min distance first. So if we have is minimum or is maximum, we can compare so what was the previous distance? Right? So we can define a previous distance as some like minus one because it can't be negative. So if we observe that the previous distance is minus one or. If and. We can also define the first critical point here as say minus one. So if we observe that if previous distance is equal to equal to minus one right? So that means we still don't if this is true. If the previous distance is minus one, that means that we need to first input our first critical point here. Right? Previous distance. Now the first has can could be. So first we should check for this. Sorry. If first critical point to minus one. So we should just add the first critical point where we should also hear current. What we should do here because it's. The first one we have already taken as previous, this is the second one. We can start from zero because at the end it's going to be the difference. And we increase this at the end of this loop. So first critical point is the current critical point, right? And so if. Yeah, if we get if else. This is not the first critical point, it's the second one. And if the previous. Distance is, I mean, will it matter if we have the previous distance as minus one or not? Or we can just check the minimum here because if it is critical, we are taking it as else. So we can just check the current critical point minus so the minimum we can just get as the minimum of. The minimum distance and the and the minimum distance and the difference between the current critical point and the first critical point. And we don't need to, I think, write this previous distance. So it's for either first or like at the end of this loop, we can also check for the maximum by okay, so we are increasing the iterator. We can't say it was a critical point or not. So I think this should be called an iterator node current ITR. And this is if it was a critical point, it's this at the end because we are not storing it, the current critical point anywhere. So we can just say, okay, last critical point, we should store the last critical point somewhere. So, yeah, it should be called an iterator. It shouldn't be called a current critical. Point because we are storing all the points here. Just a time check. I don't think we have much time. Current iterator is zero current iterator plus equal to one. And here it should be iterator instead of critical point. That means that it was a critical point and that's there so the last critical point, where will it be stored? So the Min distance, we got the Min distance, max distance. We got the max distance as we can say minus one and we can just do a max distance here also, although it will calculate it again and again. But for the last time this loop is run, the max distance will automatically get updated instead of the okay, here when we do max distance, why we are doing it with the first critical point? It should be the previous one.
Red Maelstrom: The max should be with the first, right?
Propitious Dromedary: Max will.
Red Maelstrom: First and the last.
Propitious Dromedary: Yeah. So this is the max. That's why the previous distance was important. Because here, if the previous distance equal minus one, both so the Min distance was supposed to be this, right? Else it was supposed to be and we can just previous is equal to.
Red Maelstrom: What do you mean by previous?
Propitious Dromedary: So it is the like if we are updating, if it is the first time, that when we reach the second critical point, right? So the minimum will be this, right? Okay.
Red Maelstrom: Two consecutive critical points.
Propitious Dromedary: Yeah, two consecutive critical points. So, yeah, previous distance is distance between two consecutive critical points. First time we do this and we assign the previous distance as this, right? So when we design the previous distance as this, what we can do the thing is I'm not storing.
Red Maelstrom: Do you need previous distance? I'm not sure.
Propitious Dromedary: Okay, just I think you're right. You can just simplify it here, right?
Red Maelstrom: You can just look, because if the first one is not initialized, then no previous distance calculated, right?
Propitious Dromedary: Yeah.
Red Maelstrom: And your infinity takes care of running this minimum condition anyway.
Propitious Dromedary: This minimum distance. Yeah. So here, I'm just saying that instead of this first critical point, I should be doing the distance between the current iterator and what the previous critical point was, right?
Red Maelstrom: Critical point, right. Distance, right? Yeah. Current and the previous critical point, not the previous distance.
Propitious Dromedary: Yeah. So I'm not storing the previous critical point anywhere in this code, right? So the first critical point and the sorry. And the previous last critical point.
Red Maelstrom: Okay. Previous critical point.
Propitious Dromedary: If.
Red Maelstrom: You can assign, you can initialize it in the first if condition, right? So whenever you are initializing the first critical point, you can initialize to be previous also, right.
Propitious Dromedary: But then the condition is if first is minus one, I should initialize it in every loop, right? Not only when the first critical point is minus one. Okay. Yeah. So I'm just like here else, like. If previous critical point, I can assign.
Red Maelstrom: It here first only in else also, right? It should be both. So it should be out of like this if block.
Propitious Dromedary: Yeah. So if out of this, what is this previous critical point effect? If this is minus one.
Red Maelstrom: Either way, right? Whether it is minus one or not, you will still need to update it.
Propitious Dromedary: Yeah, sure. Thank you. So we'll go here and then at the end we can just return a list of bing distance, I think. Do we have time for this problem? To go over the test, do you.
Red Maelstrom: Need to check whether if previous critical point is not minus one while calculating the minimum distance?
Propitious Dromedary: Yeah. The first time.
Red Maelstrom: Yeah. But you won't go for the first. Okay, sure. I think that would be handled.
Propitious Dromedary: No worry.
Red Maelstrom: Sorry, my bad.
Propitious Dromedary: I think.
Red Maelstrom: Yeah, this should work. Let's move to the second question.
Propitious Dromedary: Yeah.
Red Maelstrom: So the second question is this. I'm pasting it at top.
Propitious Dromedary: Okay.
Red Maelstrom: So you have two nodes in a binary tree. You have to find the lowest common ancestor of those two nodes.
Propitious Dromedary: Okay. So lowest common ancestor. So I think lowest common ancestor. So if we go from the node and these two nodes can be anywhere in the tree, right? Cool. So I think because we are talking about ancestors, so one thing that could definitely help us here is if we can just traverse the tree and while traversing the tree, we can also mark down every node's parents, right? And when we mark the parents of each of this node while traversing the tree, then we can just start from we know what are all the nodes that one would encounter from going from one of the node to the root, right? We have that path and once we have that whole path, we can store that path in a set. And then from the second node, if we start to iterate it we can start to iterate when we encounter the first node that was in the previously mentioned set where we already have a path from that node one to root, then that node would be the lowest common ancestor between both these two nodes. So however, in this case, because what we are essentially doing that basically. We iterate in a manner apart from the left and the right child, we want to store the parent of each node which means that it will cost us order of N space for each node in the tree. Second, we also plan to store the path. Stored the path from first node to root. So this path because maximum it will be the height of the tree. In worst case, it will be order N. Like in an average case because the height is login. So we will be spending this much space to store that and in the next, we don't need to store anything because we will be just checking the parent of the we will be just checking from the second node which is the earliest parent which is in the set. So this will be stored in a set. So overall I think in terms of time, like time complexity, in terms of space complexity, it will be order like N plus N like here for the two steps in the worst case so it will be order N space we will be spending for the problem. And apart from this for time because we are doing a traversal first which will be can be any traversal DFS or BFS to store it. For that, it will be order of N time. And then while constructing the set, it can be another order and time. In worst case I think yeah, it.
Red Maelstrom: Would be linear in space and time both, right?
Propitious Dromedary: What?
Red Maelstrom: Your approach is linear in space and linear in time, right?
Propitious Dromedary: Yes. Okay, so yeah, we can go through the code also this is like lowest. So here we have we have a tree first. I'm assuming the tree node has like value left and right here we have node A here which is also in itself a tree node and we have a node B and we have to return another sorry. So in this case we have so first we need to build so how can we build the parent? So first we just take the like we just mark ahead as root. For doing the breadth for search where we'll have the parent node and we traverse to its left and right children for each of them. While we traverse, we just make sure that we create a dictionary in which for each of these two nodes we mark like for the keys of the dictionary will be the children, the child nodes and the parent node will be the value. So that when we are creating the set we have this dictionary at hand. So we can have this as child. To parent dictionary here because we are starting from root so we can that. So I am doing here BFS so I will be implementing it using a queue here. So we have a BFS queue which will be just in python it's DQ. So what we do is we just push in the queue. Push in the queue the head node right. While there. So here how to check if it is it is empty or I think there is a function but we can check is while if this queue is empty I think it returns none. So we can just check it like this while bfsq like if there is something in the queue. So what we have is we will get the current node here by using this. So this will be BFS queue not pop left. If there is a left child to this node, what we can do is we can add child to parent DICT left this as the current node. So similarly we are doing it for the right node and once we do this we also need to we are adding it to the dictionary but we also need to add this particular so bfsq. Push push the left node here. Similarly we can push the right node. So this will end. So this will take because we are iterating over each of the node in the tree till skew is empty and the queue will be empty when it is like nothing to push here. So when all the leaves like we have reached all the leaves so we have this order and time. Now we need to make so we have node A and node B and we have this dictionary which is constructed. So what we can do is we can construct like a set like we can set path node A to root this is a set and what we can do is while. So how will we construct a set? So we have while node A and because we already have this root here. So while node not equal to. So what we can do where should we end this loop? While so because we are okay so. Let's check like we can check an iterator from Node A. You can check there's a node A. So while this iterator doesn't have a parent, right? So node is going to be the first node which doesn't have a parent. So we can just time check like.
Red Maelstrom: We have five more minutes.
Propitious Dromedary: Five more minutes, okay. Yeah. While iterator of node A is the dictionary. Yeah. So this is not there. What we can do is we add it a. This will create a path so from eight so now similarly while. We make another node B while B ITER node B so we iterate on B. If not we can check and update it as node B. Else. I think there is guaranteed to be like I'm assuming there is guaranteed to be a lowest common ancestor or it will be root because the root. Will be included here so if we reach the root it will return the root at the end. Should we go through some cases or do you think there is time for feedback now?
Red Maelstrom: No, yeah, we can identify a few cases, don't need to run through but you can just talk about what are the test cases.
Propitious Dromedary: I think for me I would test it for sure. Like some of the edge cases I would be testing it is when the tree is like in a straight line. So when one of the node is ancestor of another node itself is ancestor of another. Another test case I will test is I think one other interesting test case is when both nodes are same and another test case is when both the nodes are in different like the left and right subtree subtree of root. Yeah, another test case I will definitely check is when tree is empty. Another test case is when one of the node is null. I don't think we clarified it earlier but it could happen that one of the node is itself null or something so it is not in the tree, right? So it should return it. So definitely if that is the test case, if one of the node is Null we need to figure it out before itself in our code rather than just going through all the code what should be the output? And I think here there is no LCA but we didn't discuss this case earlier in the clarification but definitely another test like edge case could be know because we build upon this in future and something so it's just like a node with just a left and right subtree and different cases within that, right? So maybe just check the root and the left root and the right and left and the right and check if this basic test case is working or not.
Red Maelstrom: Cool. Those are really good test cases. Let's pause for the feedback right? I really like the way you clarified for the first problem if list could be empty. You also shared the observation that there are duplicates in the given example and you asked if there is a limit on size of link list. So those are really good clarification questions you ask before jumping into the solution. I think like you mentioned that if you can find all local minima and local maxima you can compute the answer. That was good observation. Then you mentioned that maximum distance would be between first critical point and the last critical point. The next observation you shared was like as it's a link list, we cannot scan from the end. So I really like the way you communicated your thoughts clearly rather than just thinking in silos. So I think, like you mentioned, that you can solve in linear time by storing the position of all critical points with additional space of linear of order of N. I think you got confused that you would require to sort this list. But, yeah, when asked, like you identify that sorting is not required, you correctly the time and space complexity of your first solution as linear. I think you took a pause. That is one good thing you did. You took a pause and asked whether you should really try to optimize for space complexity because that is a good thing rather than wasting time. So asking interviewer is a good strategy always then that whether you will need to store the first and last position of critical point and you can optimize the space complexity to be constant. Yeah, I think you came up with correct method signature you use the optional to efficiently deal with nulls and you identified the edge cases that if the list is empty or a single node and you wrote those HKS at the beginning and then you try to write a modular code with having local minima and local maxima.
Propitious Dromedary: Check.
Red Maelstrom: As a separate helper method. I think you needed some help on implementation details, but that's okay. Yeah. And you were able to complete the implementation for the first problem. I think you took much more time. It was like close to 30 minutes when you were done with the first problem. But yeah, you cover up the time by implementing the second problem faster. You clarified whether two inputs nodes can be anywhere in a tree. You shared approach where you will update the parent pointers for each node and linear path and then find a path from given node to root. I think you did well by correctly analyzing space and time complexity. I think the way you explained was also good. You went through each step of your approach and explained how much time it would take in this particular step.
Propitious Dromedary: Right.
Red Maelstrom: I think you were done with the code within given time frame and you were able to come up with really good test cases for the second problem.
Propitious Dromedary: Right.
Red Maelstrom: But as we didn't have much time, we could not discuss about optimizing your approach for the second problem.
Propitious Dromedary: Right.
Red Maelstrom: But I think that's okay. It wouldn't be optimizing asymptotically it would be just like if you can reduce the passes we are doing through going through the tree. But yeah, I think acceptable solution. But I do feel like when it comes to pointers and maintaining different variables, I think you do need some practice. At least the first problem could have been solved at least five, six minutes earlier. Yeah. So that is the only area you should try to improve, try to practice with. Few more questions involving pointers and arrays so that the implementation things get clear. Yeah, I think this interview it would have been higher call. There is no issue in that. The highlight of this entire interview is your communication. I think that's the biggest positive from this interview and another good positive is like your code quality. You are able to code one go without having much many bugs in the implementation handling the edge cases.
Propitious Dromedary: Because I have my phone screen this week for meta do you think I Have been striving.
Red Maelstrom: Even easier than this. I think questions would be easier than this.
Propitious Dromedary: Okay. Yeah, so I was just thinking about it that I need more time for the onsite. Definitely. I feel that in terms of my time management because sometimes that I take more time than is required, I can solve the problem but I'm trying to do more the timed contests or something like solving two problems in 40 minutes kind of challenges. But I do feel I'm okay to go for the phone screen at least this week. So let's see how.
Red Maelstrom: Only hint would be like in meta your coding interview don't have any say on your leveling part. It just say that whether you have decent coding skill for meta or not, it does not have right about deciding your level. It's just system design and behavioral which decides the leveling part.
Propitious Dromedary: Right? Yeah.
Red Maelstrom: So it's okay to be abstract while communicating your idea. It's okay to skip some steps while explaining your for example complexity analysis. It's okay say that okay, the bottleneck is like going through all the nodes. It would be linear and also we need to store it would be linear. It's okay to be abstract at least in meta while explaining your yeah, because it's really important to get two code is unlike Google or Amazon in meta it's compulsory to have two questions.
Propitious Dromedary: Yes, I do know that.
Red Maelstrom: Okay, cool for phone screen I think you are sorted all the best for your phone screen. Maybe if you required, you can reach out to me over email if you need any guidance regarding system design or behavioral interview.
Propitious Dromedary: Yeah, thank you very much. Yeah, definitely. This was very helpful and I hope to speak to you sometime.
Red Maelstrom: Awesome. So are you applying for London location or US?
Propitious Dromedary: So currently I am in US and I'm applying for US locations.
Red Maelstrom: Okay, sure, yeah. Cool. All the best. Thank you. Okay, 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.