Jump Game

Watch someone solve the jump game problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Jump Game: Python Interview with a FAANG Engineer - YouTube

Interview Summary

Problem type
Jump game
Interview question
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1].

Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2

Interview Feedback

Feedback about Wheedling Abacus (the interviewee)
Advance this person to the next round?
No
How were their technical skills?
3/4
How was their problem-solving ability?
2/4
What about their communication ability?
4/4

Overall you showed good skill in problem understanding by asking right clarification problem. You showed skill in narrowing down the problem statement to one of the known programming paradigms (you were able to understand that this problem could be solved using dynamic programming). You need some practice over graph algorithms to understand for any specific problems how those algorithms can be applied.
Notes:

• TC went through the problem statement and shared their understanding to make sure they understand the problem statement.
• TC clarified if there is always going to be one solution. Explained to them that there could be multiple ways of reaching to the last index in minimum steps. Also, there could be the possibility that you cannot reach the last index.
• TC mentioned that by look of it, it looks like a dynamic programming problem.

• TC mentioned that they think it's a dynamic programming problem and they are not good at it.
  Hint: Mentioned that there is a way to solve using the graph.

• TC was able to model the given problem into the graph with every index being a node and there being edges from every index to reachable nodes.

• TC needed some help to understand that this is a directed acyclic graph.
• TC needed some help to understand why BFS is a better choice in this case as compared to DFS.

• TC was able to come up with the implementation of BFS.

• TC needed some help to modify their implementation of BFS to work as per the given problem.
• TC did not maintain the visited set in their implementation. TC also struggled with why the visited set is important.

• TC implemented visited logic.
• TC ran through some test cases.

Feedback about Red (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
3/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4

Was a great interview, super helpful. Great at guiding me to the solution without being overbearing. Appreciated the feedback during and after as well.

Interview Transcript

Red Maelstrom: I was saying we'll spend like around 40 to 45 minutes on coding problem and I will keep the last 5 to 10 minutes for feedback.

Wheedling Abacus: Okay, sounds good.

Red Maelstrom: Cool. So this is the problem. Like, you have zero-index integers, array of length n. So basically every number you are at the first position, zero index, and every value represents, like how many jumps you can take from any particular index forward. So basically, you can go to, let's say, for example, your current index is I, and your value is X. You can go to I plus one, I plus two up to I plus x. I see. So you have to reach to the last index, last index, which is n minus one. And you have to return the minimum number of jumps required.

Wheedling Abacus: Okay. Each element nums I represents the maximum length of a jump. If you are at nums I, you can jump to any I plus j. Okay. Then j is between zero and right. Okay. I plus j is less than n. Turn the minimum number of jumps to reach nums of n minus one. So return the minimum number of jumps to reach the last element of the array.
Red Maelstrom: Correct.

Note: The interview continues discussing strategies for solving the problem including comments on graph representations, understanding of breadth-first search, and possible implementations, concluding in a feedback session about performance in the interview.