Frog Paths Without Long Runs
Updated
Problem statement
A frog starts at point (0, 0) and wants to reach point (x, y). Each jump moves it exactly one unit: either right, which adds 1 to its first coordinate, or up, which adds 1 to its second coordinate.
The frog gets bored easily. It never makes more than r jumps in a row in the same direction.
Return the number of different jump sequences that take the frog from (0, 0) to (x, y).
Function
countFrogPaths(x: int, y: int, r: int) → longExamples
Example 1
x = 5y = 4r = 2return = 45This is the interview case: no three jumps in a row in the same direction means r = 2. Without the rule there would be C(9, 4) = 126 paths.
Cut the path into runs: groups of jumps in the same direction. Each run has length 1 or 2. The 5 right jumps can form 3 runs in 3 ways, 4 runs in 4 ways, or 5 runs in 1 way. The 4 up jumps can form 2 runs in 1 way, 3 runs in 3 ways, or 4 runs in 1 way.
Right runs and up runs take turns, so their counts differ by at most one. When the counts are equal, the path can start with either direction. The total is 3*1 + 2*3*3 + 3*1 + 4*3 + 2*4*1 + 1*1 = 45.
Example 2
x = 2y = 2r = 1return = 2With r = 1, the frog must switch direction after every jump. The only paths are right, up, right, up and up, right, up, right. The answer is 2.
Example 3
x = 0y = 3r = 2return = 0The only way to reach (0, 3) is three up jumps in a row. That is more than r = 2, so no path is allowed. The answer is 0.
Constraints
0 <= x, y <= 25x + y >= 11 <= r <= 50
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · Seen Nov 2026
- Bold Play to Reach a GoalOA · Seen Nov 2026
- Cats, Truth and Who Has MoreOA · Seen Nov 2026
- Counting Cows by Their LegsOA · Seen Nov 2026
- Enough Muffins for the LineOA · Seen Nov 2026
- Expected Consecutive Pairs Among Chosen NumbersOA · Seen Nov 2026
- Four-by-Four Boundary GridOA · Seen Nov 2026
- Higher Roll, or Lose the SumOA · Seen Nov 2026
- Is a Popular Story Fake?OA · Seen Nov 2026
- Knights, Knaves and Their StatementsOA · Seen Nov 2026
Similar questions at other companies
- Count Shipment SchedulesMorgan Stanley · OAMorgan Stanley interview questions
- Find Encrypted NumberAmazon · OA
- Valid PasswordsMathWorks · OAMathWorks interview questions
- Coloring HousesSnowflake · OASnowflake interview questions
- Find Maximum Number of StringsMoveworks · OAMoveworks interview questions
- Count Distinct Binary Search TreesC3.ai · OAC3.ai interview questions
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions
- Stable Workload Redistribution TreesTower Research Capital · OA
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Count Permutations Without Three Equal Parities in a RowGoogle · OAGoogle interview questions