Count Grid Paths with No Three Equal Moves
Company: Sig
Role: Data Scientist
Category: Statistics & Math
Difficulty: easy
Interview Round: Online Assessment
# Count Grid Paths with No Three Equal Moves
A frog moves from `(0, 0)` to `(5, 5)`. Every step is either one unit right or one unit up. The frog refuses to make three moves in the same direction consecutively.
How many valid paths are there? Derive the count without enumerating all `C(10, 5)` paths one by one.
### What a Strong Answer Covers
- Translation into strings with five right moves and five up moves.
- A restriction that every run of equal moves has length one or two.
- Correct counting of bounded compositions and alternating run sequences.
- Coverage of equal and unequal counts of direction runs.
### Follow-up Questions
- How would a dynamic program count paths to a general point `(m, n)`?
- What changes if at most three consecutive moves in one direction are allowed?
Overview: Count lattice paths from `(0, 0)` to `(5, 5)` that never use three identical directions consecutively. The solution converts paths into alternating runs of length one or two, counts bounded compositions for equal and unequal run totals, and derives 84 valid paths.
Read the full Sig Data Scientist interview experience this question came from