Google | L4 | Phonescreen

Round 1

Questions: You are given an n×m grid and start from the bottom-left corner with the goal of reaching the bottom-right corner. The allowed moves are only to the right, diagonally up-right, and diagonally down-right. The task is to determine the total number of unique paths that can lead you from the starting point to the destination while adhering to these movement rules.

Follow-Up Questions:

1. A list of specific checkpoints within the grid is now introduced. In this variation, you are required to count only those paths that pass through each of these checkpoints once before reaching the bottom-right corner.
2. The order of visiting these checkpoints is now specified. For example, if the checkpoints are labeled 1, 2, and 3, any valid path must encounter checkpoint 1 first, then checkpoint 2, and finally checkpoint 3, in that exact sequence, on its way to the destination.