The Staircase Problem

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

On our staircase the order of moves matters: going up 1 then 2 is a different climb from 2 then 1, and every climb lands exactly on the top stair. Return how many climbs reach the top of n stairs taking 1 or 2 steps at a time, where a staircase with no stairs (n of 0 or less) has no climbs at all.

One step or two, the choices add up.

Example 1

Input:

n = 3

Output:

3

Example 2

Input:

n = 5

Output:

8

Worked solution and explanation

Why this problem exists in real interviews

This is the Fibonacci sequence wearing a staircase costume. Everyone sees that the last move came from one stair below or two stairs below, so the count adds the two before it. What separates candidates is the edges: the seeds that make n = 1 come out right without a special case, and the guard that stops an empty staircase from quietly reporting one climb. Seed the rolling counts at 1 and skip the guard, and n = 0 returns 1 instead of 0.

Break down the requirements

Step 1: Guard the empty staircase, then seed

A staircase with no stairs has no climbs, so if n < 1: return 0 exits first. The main path then seeds prev2 and prev1 at 1 (the ground and the first stair). Those seeds would answer n = 0 with 1, which is exactly why the guard has to come before them; for n = 1 the loop never runs and the seed is the answer.

Step 2: Build up iteratively

Use two variables to track the previous two values and iterate from 2 to n. This avoids the exponential blowup of naive recursion.

The solution

Bottom-up Fibonacci with O(1) space
def count_ways(n: int) -> int:
    # An empty staircase has no climb to count; the seeds below would wrongly say 1.
    if n < 1:
        return 0
    # prev2: ways to reach the stair two below; prev1: ways to reach the stair one below.
    prev2 = 1
    prev1 = 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

The guard handles the empty staircase; the seeds already answer n = 1.

Common follow-up questions