# The Step Counter

> You can hop one step or two - how many ways to reach the top?

Canonical URL: <https://datadriven.io/problems/the_step_counter>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given non-negative integer n, return the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. (Fibonacci-like.)

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **dynamic programming** fundamentals. It is the same Fibonacci-style recurrence as the classic staircase problem, probing whether a candidate recognizes the pattern and avoids exponential recursion.

---

### Break down the requirements

#### Step 1: Recognize the Fibonacci recurrence

The number of paths to step n is the sum of paths to step n-1 and step n-2, since you can arrive from either.

#### Step 2: Use iterative bottom-up computation

Track two variables for the previous two values and iterate forward. No recursion or array needed.

---

### The solution

**Iterative Fibonacci with constant space**

```python
def count_paths(n: int) -> int:
    if n <= 1:
        return 1
    prev2 = 1
    prev1 = 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    result = prev1
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) for a single linear pass.
> 
> **Space:** O(1). Two variables replace the need for a full DP array.

> **Interviewers Watch For**
>
> Can you explain the base cases clearly? `f(0) = 1` means there is one way to stay at the start (do nothing), which often trips candidates up.

> **Common Pitfall**
>
> Using recursion without memoization leads to O(2^n) time. For n = 45, this takes over a billion calls.

---

## Common follow-up questions

- What if the user could also skip 3 steps at a time? _(Tests extending to a three-term recurrence.)_
- How would you handle very large n (e.g., n = 10^6)? _(Tests that the iterative approach already handles this; mentions modular arithmetic if overflow is a concern.)_
- What if some steps were disabled? _(Tests conditionally zeroing out certain positions in the DP computation.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_step_counter)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.