# The Never-Ending Sequence

> Sequence that keeps going. Follow it.

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

Domain: Python · Difficulty: easy · Seniority: L5

## Problem

Given non-negative integer n, return the first n Fibonacci numbers (starting 0, 1, 1, 2, 3, 5, ...) using iteration.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **iterative computation** and the ability to generate a well-known sequence without recursion. Interviewers use Fibonacci as a baseline to check loop mechanics, variable swapping, and edge case handling for n=0 and n=1.

---

### Break down the requirements

#### Step 1: Handle small n values

If n is 0, return an empty list. If n is 1, return `[0]`.

#### Step 2: Seed the first two values

The sequence starts with 0 and 1.

#### Step 3: Iterate and build the rest

For each subsequent position, compute the sum of the previous two values and append it.

---

### The solution

**Iterative generation with two-variable swap**

```python
def fibonacci(n):
    if n == 0:
        return []
    if n == 1:
        return [0]
    result = [0, 1]
    for i in range(2, n):
        next_val = result[i - 1] + result[i - 2]
        result.append(next_val)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) for generating n values.
> 
> **Space:** O(n) for the output list.

> **Interviewers Watch For**
>
> Do you avoid recursion? Recursive Fibonacci without memoization is O(2^n), which is catastrophically slow. The iterative approach is O(n) and signals practical engineering sense.

> **Common Pitfall**
>
> Off-by-one on the sequence definition. The problem says 'starting with 0, 1', so `fibonacci(5)` should return `[0, 1, 1, 2, 3]`, not `[1, 1, 2, 3, 5]`.

---

## Common follow-up questions

- How would you compute just the nth Fibonacci number in O(1) space? _(Tests the two-variable rolling approach without storing the whole list.)_
- What if n were very large (e.g., 10^6)? _(Tests awareness that Python handles big integers natively but other languages would overflow.)_
- Can you compute the nth Fibonacci in O(log n) time? _(Tests matrix exponentiation or the fast doubling method.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_never_ending_sequence)
- [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.