Course launching November 17, 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
You are developing a game where players can move 1, 2, or 3 steps. The board is a straight line, and you want to know the total number of ways you can reach the final spot for any combination of jumps.
Write a function
countTotalMoves that calculates the total ways to reach the last spot in a board using any combination of 1, 2, and 3 jumps.
The input for the function is the length of the board.
NOTE: If the board length is 0 or 1, you can assume it is still 1 total move in both cases. This is an intentional decision by the interviewer which will allow you focus on the logic of the solution. With 0, there is only 1 way for your piece to piece to exist and that is by staying at the starting location. With 1, the only move to go from the starting position to the final square is a hop of 1. If we instead said for a board length of 0 that the total moves is 0, it complicates the base cases. There is an argument for length 0 to be either 0 or 1 moves with no "right answer", so we are opting for the simpler path.
const boardLength = 4; countTotalMoves(boardLength); // Answer: 7 // Moves: // 1,1,1,1 // 1,1,2 // 1,2,1 // 2,1,1 // 2,2 // 1,3 // 3,1
Validate My Answer
A top-down approach is very elegant here. Think how to break this into subproblems and what your stopping conditions would be.
Ensure you handle all case for negative, zero, and positive board lengths.
There is a lot of repeated work for a brute force recursive solution. Find a way to remove this to get a O(n) time and space solution.