Frog on a grid

What this constrained-path-counting interview question tests

This is a hard combinatorics problem that sits at the intersection of counting, dynamic programming, and constraint satisfaction. It asks you to count lattice paths under a non-trivial restriction—forbidding three consecutive moves in the same direction—a constraint that rules out simple combinatorial formulas and demands careful state tracking.

Solving it requires building a recurrence relation that respects the constraint, typically by encoding not just position but also recent move history (the last one or two steps). This tests whether you can translate a constraint into state, design a DP table that captures it, and execute without off-by-one errors or missed cases. Quant firms value this skill because real problems—portfolio constraints, risk limits, market microstructure rules—often impose similar structural restrictions on what counts as a valid solution.

• State-space design for constrained counting problems
• Dynamic programming with multi-dimensional state
• Careful boundary and transition logic