Python Interview with a Meta engineer

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.

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? Yes
• How 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 reasons about how optimizing their solution further is not possible. Candidate writes working code with good speed. Candidate has good testing/debugging skills. Overall, it would be a hiring 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 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 reasoned about why binary search is not applicable and linear time solution is best we can get.
  • TC shared approach and analyzed 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? 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

Overall Feedback: 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.

Interview Transcript

Red Maelstrom: So let me just paste the first question. So, yeah, you have 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.

... (continuing with the transcript and interview details).

Analysis of the Mountain Array

An array is a mountain array if and only if the array length is greater than or equal to three. The conditions for a valid mountain are:

1. There exists an index I such that the array is strictly increasing until that index.
2. After that index, the array is strictly decreasing.

Edge Cases to Consider:

• Length of the array less than 3 should return false.
• Multiple peaks should return false.
• All increasing or all decreasing should return false.