โ† Goldman Sachs questions

Staircase jump combinations

Filed under Goldman Sachs

Free read 1 of 3

Verify 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

  1. Verify if step sizes are restricted to 1, 2, and 3, and discuss constraints on N.

Solution

O(N) time, O(1) space

Python
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.