Sig·Software Engineer·Technical Phone Screen·Junior

Junior

Jun 2026

Summary

SIG quant researcher interview with a combinatorics path-counting problem that looks straightforward until you actually try to count it. The constraint makes it way harder than a standard grid walk.

Questions Asked (1)

A frog moves from (0,0) to (4,6) on a grid, taking steps either right or up one unit at a time. It cannot take three consecutive steps in the same direction. How many valid paths exist?

Algorithms & Data Structures

Author's notes

My first instinct was to just write out the recursion and I kept second-guessing my base cases.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as counting sequences of R and U moves with exactly 4 R's and 6 U's, subject to the constraint that no three consecutive moves are the same. Use dynamic programming with state (r, u, last_move, consecutive_count) to count valid paths efficiently.

Pro tip: After deriving the DP, mention that you can optimize space by only keeping the previous layer, and that the constraint is local so DP is ideal. Also, verify with small cases to ensure correctness.

1. Understand the problem

Recognize that the frog must take exactly 4 right steps and 6 up steps, and that the constraint forbids any run of 3 or more identical steps. The total number of unrestricted paths is C(10,4)=210, but many are invalid.

2. Define DP state

Let dp[r][u][last][k] be the number of valid paths reaching (r,u) where the last move was 'last' (R or U) and it has been repeated k times consecutively (k=1 or 2). Initialize by considering first move.

3. Establish transitions

From a state, you can move in the same direction only if k<2, incrementing k; or switch direction, resetting k to 1. Only allow moves that stay within bounds (r≤4, u≤6).

4. Compute and return result

Iterate over r from 0 to 4 and u from 0 to 6, filling the DP table. The answer is the sum of dp[4][6][R][1] + dp[4][6][R][2] + dp[4][6][U][1] + dp[4][6][U][2].

Key Points to Mention

Dynamic programming with state including last move and consecutive count
Time complexity O(4*6*2*2) = O(1) for fixed grid, but generally O(m*n)
Space optimization possible by only keeping previous row/column
Alternative combinatorial approach using inclusion-exclusion (more complex)
Verification with smaller grids to ensure DP correctness
Edge cases: when one dimension is zero, or when constraint makes path impossible

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.