Staircase jump combinations
Filed under Goldman Sachs
Free read 1 of 3Verify if step sizes are restricted to 1, 2, and 3, and discuss constraints on N.
The question
Calculate the number of ways to reach the Nth stair if you can jump 1, 2, or 3 steps at a time.
Constraints
- N is an integer between 1 and 30.
Examples
- Input
- n = 3
- Output
- 4
- Why
- Ways are: (1,1,1), (1,2), (2,1), (3).
Approach
Verify if step sizes are restricted to 1, 2, and 3, and discuss constraints on N.
Recursive function branching into 3 calls per step, resulting in O(3^N) time complexity.
Use iterative dynamic programming keeping track of only the last 3 results to reduce space complexity to O(1).
N = 1, N = 2, and N = 3 base cases.
Solution
O(N) time, O(1) space
def tribonacci_stairs(n: int) -> int:
if n <= 0: return 0
if n == 1: return 1
if n == 2: return 2
if n == 3: return 4
a, b, c = 1, 2, 4
for _ in range(4, n + 1):
a, b, c = b, c, a + b + c
return c
Tips
- What they are testing: Test with small inputs (1, 2, 3) and check base cases to avoid off-by-one errors.
- Common mistake: Using pure recursion without memoization, leading to redundant calculations and TLE.
Follow-ups
- Explain how recursion is handled in memory
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.