We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free
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.
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?
NoHow 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 know programming paradigm(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 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 them that there could be multiple way of reaching to last index in minimum steps. Also there could be possibility that you can not reach to 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 and 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 node and there being the 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 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 given problem. - TC did not maintain the visited set in their implementation. TC also struggled why visited set is important. + TC implemented visited logic. + TC run through some test-cases.
Feedback about Red (the interviewer)
Would you want to work with this person?
YesHow 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 last and 50 minutes of 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 first position, zero index, and every value represent 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 minimum number of jumps required.
Wheedling Abacus: Okay. Each element nums I represents maximum length of four 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.
Wheedling Abacus: Okay, cool. All right, so let me just restate the problem real quick. So you have an input array, and the input array contains a bunch of numbers. And each number represents the amount of indices you can jump from that index. And you want to start from the zero th index and end up to the last index in the minimum number of jobs. Does that sound correct? Okay, cool. Let's see. So I'm going to look at the example. So, 23114, the output is two because it takes two jumps from the zero th index. You jump one step and then you jump three steps. One, two, three. That makes sense. Is there always going to be one solution?
Red Maelstrom: There could be multiple solution and you can like multiple ways of reaching in that many steps. Right. So basically, let's say, for example, it could also be possible that you had two here. One way was like to go to three and then to four. Otherwise you could go to two and then to four. But in both case, jumps are two. So you are just concerned about a number of jumps. So in terms of output, there is going to be always one possible output.
Wheedling Abacus: Yeah.
Red Maelstrom: But there is a possibility that you cannot reach to the last index. In that case, you can return minus one.
Wheedling Abacus: Return minus one if there is no solution. Okay, perfect. Okay. Think that covers everything. Okay, cool. I'll just go into approach. I'm going to think about it for a little bit. I guess starting from the zero th index, you're always going to start at the zero th index. So then you're only considering the. Could I use the whiteboard?
Red Maelstrom: Sure.
Wheedling Abacus: Cool. So you're only considering the indices you could reach from the zero th index initially, then. Interesting. It seed. I think this sounds like a dynamic programming problem, possibly where I guess we'd be keeping track of the number of jumps to the end and then updating that as we go. Sorry, iPad. So if we have example 2314. It. So we look at all the places reachable from two, and that's index one. And that's index two. And then we can consider each one. So if you go to index one, then you could definitely go to the end. And that's because the value at index one is greater than or equal to the length of the. I guess. Yeah, the end minus the index value at the index. Um, okay, so that's probably important. And then we could look at the next one and see that one is not greater than or equal to. What is this? Zero, one, two. So four minus two. Let me just write out these examples real quick. The value at one is greater than or equal to n minus one, which is 1234. Minus one is equal to three. Index two is greater than or equal to four minus two. And you see that one is not greater than two. Okay, so it seems that this is our condition. But let's see, that's only the condition to reach the end that doesn't consider any intermediary steps. So really hard problem. Um, let's, let's see. See, I haven't. I feel like this is a dynamic programming problem. I haven't really worked on dynamic programming questions. Okay, could I have a little hint about how that would work?
Red Maelstrom: I think you are right that this could be solved with dynamic programming problem. But there is other way to solve.
Wheedling Abacus: It using graph also, there are other ways using. Sorry.
Red Maelstrom: Yeah, you can solve it. Consider it as a graph problem.
Wheedling Abacus: Also as a graph problem. Okay, that's good to know. Okay, so we have a node zero represent. You it. So if we have nodes at every index. 01234. And then I guess the values would represent edges connecting from wherever you could reach. Like that. And so three means there'd be edges like that one is just. Okay, if this was a graph problem, what would be the problem? You'd want to get from point A to b, the minimum number of steps. So that's the minimum number of nodes visited and it. Sorry, just thinking about it.
Red Maelstrom: Okay. What are you thinking now? I'm just thinking you correctly modeled as a graph problem, right. And those edges would be directional. You can go from zero to one or zero to two, but not vice versa. You cannot come from one to zero or two to one. You can always go forward. Okay.
Wheedling Abacus: Only go forward. Yeah. I guess with that information then you can kind of make a sub problem once you trip.
Red Maelstrom: Are you aware about graph algorithms?
Wheedling Abacus: I like, yeah, but I don't think I could implement them like a star.
Red Maelstrom: Are you aware about traversal algorithm, graph traversals?
Wheedling Abacus: I'm aware of three traversals like DFs, bfs.
Red Maelstrom: Yeah. What do you think? Can one of them solve this? This is a tree, right? Because there is no cycle. It's always going forward.
Wheedling Abacus: Oh, you're right, that's very true. I believe that for search then, because you're trying to go to the end.
Red Maelstrom: Okay.
Wheedling Abacus: Yeah, that's so true. Okay. Maybe if I represent this as it, well, there are cycles, right? Yeah.
Red Maelstrom: But they are not directed cycles, right. You cannot start from node and come back to that node.
Wheedling Abacus: True. Yeah. Okay.
Red Maelstrom: So do you think you would be able to implement BFS webfast search or we should move to some different question?
Wheedling Abacus: Yeah, maybe a different question, I think.
Red Maelstrom: Okay.
Wheedling Abacus: I'm not sure.
Red Maelstrom: Sure.
Wheedling Abacus: Well, you said depth for search, right?
Red Maelstrom: Breadth for search.
Wheedling Abacus: Breadth for search.
Red Maelstrom: Yeah. Why do you think? Because you want smallest path, right. So get first search will give you smallest path wouldn't right? You go level by level. You want to reach as early as possible. With this, your index zero would be a source and you will stop your breath for search when you reach to the last index.
Wheedling Abacus: So breadth first search would be better because you hit the end of the.
Red Maelstrom: When you hit the first time. Yeah. You know that you can terminate in that first search. You don't know, right. Whether you have reached through shortest path or non shortest path.
Wheedling Abacus: Okay, I think I could give it a shot then BFS. Okay, so the algorithm is from the source, you would use BFs. And then once you hit the end node, once that's reached, then you terminate. Okay, it, I guess. How much time do we have left?
Red Maelstrom: We have around 20 minutes, 30 minutes.
Wheedling Abacus: Okay. 1234. So then this would be the three to four and it's also one to four as well. So it'd be like this. And then the BFs would travel there, then travel there, and then it will terminate in the implementation. I guess the first step would be to represent as a graph. I just use this and then run bfs. Given the graph representation, we can run bfs by, I believe it would be a queue. So we would have some queue. Um, so if I was doing, yeah, just write it to you. And then to, okay, so you would add the roots and then while there's elements in the queue, you would um, leave pop, and then add the children. So then add zero, you would pop zero, add the children one and two, and then you go back, pop one, add the child four, and then pop two, add the child three while the queue. And then we check the win condition if the value, okay, so how are we representing these, actually? So if the index, the values of each node only represent edges. And so that will be handled in our graph representation. What we care about is the index, which we could store as the. We could store as the value of the node. So if the node is equal to n minus one, then we have reached the end. Okay. So we need something to keep track of the distance. So for every path we take, it's going to be a new thing we'd want to keep track of. And it's not necessarily like a binary tree, obviously, it could be a bunch of different paths. So what would be a good data structure to keep track of paths? We can, so every time we pop from the queue we get, hold on, sorry. Okay, so we're at zero, then q dot, pop, zero comes out. Add one and two every time. Every child you add is a different path. I think that is always true. So we could do like when we're adding the children, that would be for child, in children you would, we don't necessarily have to keep track of all the paths because we just need the minimum path. So guess once you hit the end. Oh, okay. Yeah. So at every iteration we could just have, okay, min distance is equal to zero. And then every iteration we just increment because you're going by depth or you're going by levels. And so you would just increment this and then by the time you hit the end, it's going to be the minimum distance. So we'd want to just return the minimum distance there. So yeah, you don't have to keep track of paths or anything. That was kind of detour. So I think that's good for running BFs. As far as representing the graph given an array. 231414. Um, I guess you would construct a node, huh? I'm not sure what's the best way to represent a graph here in the code?
Red Maelstrom: I think you always don't need to represent a graph. Right. So you can go through this. What, you write a code, right. You just need to think about how would you identify all the children.
Wheedling Abacus: Okay. Yeah.
Red Maelstrom: You don't need to build a graph. Right. Yeah, this looks good. Maybe we can go back to text and write a code.
Wheedling Abacus: Okay, sounds good. All. It's my first time using this interface. Do I just write it here?
Red Maelstrom: Yeah.
Wheedling Abacus: Okay. Just copy. Okay, so it doesn't necessarily have to be like something executable. Yes, that's okay, I see. Okay. Um, well, we're given, it says we're given an array of integers. Can we just assume that we converted that into something that we could run this algorithm on or do we have to implement that as well?
Red Maelstrom: You have to assume it's as an input to be available as integer, array and another integer.
Wheedling Abacus: Okay, so it has to work with an array of integers.
Red Maelstrom: Yes.
Wheedling Abacus: Okay, well in that case, um, so I do need to somehow represent. Okay, add children. I'm going to do it in python. I don't know if there's like text highlighting, is that.
Red Maelstrom: Yeah, you can write in python.
Wheedling Abacus: Oh cool. While, so from collections import deck. Then you want function. What should we call it? Numbers minimum path that takes in an array of call it jumps, jumps array. And that's it. And then want to so is equal to. KQ wants to add something here first, but I believe it's pop up. I'm just not sure right now how exactly to represent it to add into the queue. But let's see. Okay, so if you're at the first index, say two. That means here's an edge from zero to one and zero to two, meaning the children from that node are indices one and indices two. So when you, okay, so when you add something to the queue, I think for now maybe, I'm not 100% sure. I'm thinking we add the index. So just add like zero, the first index.
Red Maelstrom: Okay, you add index. That makes sense. Yeah, you add an index. That makes sense.
Wheedling Abacus: Okay, cool. And then when you pop it, that's going to be the current. And then you look at all the possible places you could reach from that index. So that's going to be all the children and then you want to add those to the queue. So how would we do that? Programmatically we have Kerr, the value of Kerr is going to be nums, sorry. Jumps of curve. And then using that value, that's all the children. So four I in range value you're going to add, right? Because if it's two, then you have two edges. If it's three, you have three edges. And then you're going to be adding indices incrementally from there. So you do Q dot append I. I'm not sure if you brackets on.
Red Maelstrom: Not this I, right. It would be like current plus I plus one. Right. I will range from zero to Val.
Wheedling Abacus: You're right, current plus, so from zero. And then I is from zero to Val. So yeah, it would be current plus I plus one. Perfect. Okay. So you add those to the queue and then we're going to keep track of min distance here. And then if.
Red Maelstrom: Your main distance should be level, right, you should not count the number of nodes. I don't think you will be incrementing the main distance every time you reach any node. You pop any node from the queue, which won't give you a min distance. It will end up calculating number of nodes. Right. Maybe you can add min distance as a tuple in a queue. So you can add like zero comma zero, that to reach zero, you need zero distance and then use that to add the next one.
Wheedling Abacus: I see.
Red Maelstrom: And here your Q will also give two things, current and this, right, you will have like this plus one.
Wheedling Abacus: This plus one. Perfect.
Red Maelstrom: Yeah, perfect.
Wheedling Abacus: And then we have our win condition. If Kerr, I guess we could put this up here. So if Kerr, oh wait, no, cur is the index. If Kerr is equal to length of jumps minus one, then we've hit the end and then we would want to return distance there and then there's no way that distance wouldn't be the minimum distance because we're just building up. And so once you hit the end, it's going to be the minimum. If there's no solution, that won't be hit. And so we could return negative one here. And I don't know if this while would just go on forever. I think it wouldn't because if you add elements to the queue, you would just pop. So you hit the end and there's no cycles because the children that you add are always going to be greater than. You're not going to backtrack. Yeah, there shouldn't be any problem with this running forever. So, yeah, you just return negative one here. Cool. I think, yeah, let's run that with the example and see what happens. 23114. So is there a way I could do whiteboard and the coding environment. Is that possible?
Red Maelstrom: No, probably.
Wheedling Abacus: Okay, that's fine. So here we have our Q. We instantiate with a two pool with the zero th index and the zero distance. And then we pop, and then we see that the current is so length of jumps minus one is going to be four here. Current is zero. So we go on here, the val is jumps, this array is jumps, jump sub zero is two. So it's going to be two here. And then we increment through from range like zero and one. And then append curve which is zero plus I, which is zero plus one. So the first tuple is one and the distance is going to be incremented. The second tuple is going to be curve plus one plus one, which is two, one. So now if we have our q, currently we have eleven in there, and then we have two, one. So those are going to be in the queue. And then now we pop the next one. We can get rid of all this. And let's see. So next one is going to be eleven. We pop that. So we're working with, now, Kerr is not equal, it's not equal to four is one. So we move on to here. Val is jumps of curve, jumps of one is three. So we have three for Val. And then we append three different tuples, which are going to be. So ker is currently one. So we'd have one plus zero plus one is two. And then distance is currently one. So be two. That's the next tuple. Next tuple after that is going to be three, two, and then four, two. So yeah, we hit, yeah, you will.
Red Maelstrom: Hit, once you pop it out. You will hit it once you pop it out. What is the complexity of your solution?
Wheedling Abacus: Time complexity is, let's see, you're going through. So in the graph representation, go back to the whiteboard. Okay. BFs, I believe is B plus B plus e. Number of vertices plus number of edges.
Red Maelstrom: Okay, but here that would be the case when you visit every node once. Right. But here you are not maintaining any visited thing data structure for representing which nodes are already visited and skipping them.
Wheedling Abacus: Okay. So it would be faster because we're not.
Red Maelstrom: Yeah. So maybe, can you consider adding that? And what would be the right data structure to maintain that?
Wheedling Abacus: Sorry, could you repeat that?
Red Maelstrom: Can you somehow maintain the list of nodes or the array indexes which you already visited?
Wheedling Abacus: Maintain the list of nodes that I've already visited? Yes. We can have a, what's it called? We could have a dictionary. And then if we visit a node which we could do after we pop, if it exists, then we could just set something and then, sorry, what was the point of the visited tracker?
Red Maelstrom: So you should not end up visiting some nodes multiple times. Right. So for example, let's say this is a bigger array, right? Let's say this is kind of a bigger array. What will happen is you will reach this node, four from three jumps from here from three and one jumps from one also.
Wheedling Abacus: Right.
Red Maelstrom: So you might end up recalculating everything again.
Wheedling Abacus: I see. Computing. So by maintaining a visited, um, we could store the shortest path to that.
Red Maelstrom: No, you don't even need to store a sorted path. Right. You just need to ignore it. You don't need to add it back into the queue.
Wheedling Abacus: Right.
Red Maelstrom: If something has already been added into queue, you don't need to re add it. That's it.
Wheedling Abacus: Right. Okay. Yeah, that makes sense. So then you could look into our Q. So then we'll calculate our next index. It's going to be curve plus I plus one. If next index is not in visited and we add and we append it to the queue. Yeah. Then I guess we don't even need it. Yeah. If we just need to make it a set. Not really sure how you add to a set. No, it's fine. It could be a dictionary. I'm not sure how to.
Red Maelstrom: Cool. I think we almost finish over 45 minutes, so let's pause for feedback. I think you went through problem statement. You shared your understanding about a problem to make sure that you understand proper it properly. You clarified few things which were important, like will there always be one solution? And we discussed like there could be multiple optimal ways to reach the last index, but we just need to return the length and not the actual path. And we also discussed the possibility that it is possible not to reach the end of an array. And you were right that you mentioned that it looks like a dynamic programming problem and you were upfront about why it could not be solved with dynamic programming. Okay. But one thing which you could have done is at least you could have shared dynamic programming is nothing but an optimization of on a recursion. Right? E. So at least you could have shared a recursive approach and then you could have said that, okay, this is a recursion. And I know this could be optimized with dynamic programming, but I don't know about dynamic programming, but that could have been a better way, right? Yeah. So that would be something which you can consider. Then we discussed that it could be modeled as graph problem and you were good at modeling it as a graph problem, considering every index as a node and each being there, from that index to every index in the array to which you can reach. Yeah, I think you can reach. And then you needed some help to understand that this is very close to trees. So what this graph is called as directed or cyclic graph. So there are no directed cycles in the graph. You needed some help to understand why BFS is a better choice than DFS. But actually you were listening it properly and implementing it again, like you implemented a good code for taking care of basic DFS. But yeah, your initial implementation wasn't calculating the distance properly, it was calculating the number of nodes. We modified it and you understood it. And then I think you again needed some help to understand why visited needs to be there. I think you did show that you can learn the problem, but at least basic understanding about graph is something like what is normally expected. Maybe I will recommend you that practice some more graph problems.
Wheedling Abacus: Okay. Cool.
Red Maelstrom: I think that is the feedback from my side. Do you have any question for me?
Wheedling Abacus: Yeah. So overall, just better fundamental understanding, do you think like, I don't know, I think I was a little concerned about the amount of time I was taking just to think. I don't know, it just seemed pretty quiet. Do you think that would be a problem?
Red Maelstrom: I didn't understand the question.
Wheedling Abacus: Just like the amount of time that I was taking just thinking about the problem.
Red Maelstrom: No, I think that was okay. I think that was okay. Just about the gaps in the understanding about the basic algorithms, then that would be the only improvable area.
Wheedling Abacus: That would be the only one. Okay, so communication was good.
Red Maelstrom: Communication was superb. Even the problem solving was superb, because once I give you some hint, you were able to use that hint and modify your solution. So there is no issue on that implementation wise. Also, it was clean. But if you had understanding about how that algorithm works, you could have implemented it without need of any hint or something.
Wheedling Abacus: Okay, cool. And I guess, just curious, like if you were in charge of hiring, that.
Red Maelstrom: Would be leaning no higher.
Wheedling Abacus: That would be what?
Red Maelstrom: Leaning no higher medium?
Wheedling Abacus: No higher leaning.
Red Maelstrom: Leaning. So I would say that soft no higher. So basically it reflect as like candidate has potential, but based on this interview, he did not perform well. Either way of handling those things is if you have a good hiring, like you have showed a good problem solving algorithm in some other round, then you should be hired or you can also be considered for some follow up interview.
Wheedling Abacus: Okay, cool. Thank you for the candid feedback. Really appreciate you taking the time for this.
Red Maelstrom: No problem. Thank you all the best for your practice.
Wheedling Abacus: Yeah. Thank you so much.
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.
