Frog Paths With Direction Constraint | Dataford Interview Questions

A Susquehanna International Group path simulator moves from the origin to a target grid point. Each move is exactly one unit up or one unit right. The simulator rejects any path containing three consecutive moves in the same direction.

Given nonnegative integers rows and cols, count the valid paths from (0, 0) to (rows, cols). Return the result modulo 1_000_000_007.

A path may end with a run of one or two identical moves, but never three or more. The first move has no previous direction or run length.

Formal Specification

Implement count_valid_paths(rows, cols), where both inputs are integers. Return an integer representing the number of valid paths modulo 1_000_000_007.

Constraints

0 <= rows, cols <= 1000
The destination is (rows, cols)
Only up and right moves are permitted
Three consecutive moves in the same direction are forbidden
Return the result modulo 1_000_000_007

Function Signature

def count_valid_paths(rows, cols):

Your question is Frog Paths With Direction Constraint. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem