# The Additive Chain

> Each value is the sum of the two before it - no calls to itself allowed.

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

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given non-negative integer n, return the first n Fibonacci numbers starting with 0, 1, 1, 2, 3, 5, ... Use iteration, not recursion. Return [] when n = 0.

## Worked solution and explanation

### Why this problem exists in real interviews

Generating the Fibonacci sequence iteratively tests **state management** with two rolling variables. It checks whether you avoid recursion (exponential time) in favor of linear iteration.

---

### Break down the requirements

#### Step 1: Handle n = 0, 1, 2 as base cases

Return empty list, `[0]`, or `[0, 1]` respectively.

#### Step 2: Iterate and compute each term from the previous two

Maintain two variables for the last two values and append their sum.

---

### The solution

**Iterative generation with rolling state variables**

```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) with a single linear pass.
> 
> **Space:** O(n) for the result list.

> **Interviewers Watch For**
>
> Using iteration instead of recursion. Naive recursive Fibonacci is O(2^n) and will time out for n above 30.

> **Common Pitfall**
>
> Starting the sequence at `[1, 1]` instead of `[0, 1]`. The prompt specifies starting with 0 and 1.

---

## Common follow-up questions

- How would you compute just the n-th Fibonacci number without storing the full list? _(Tests using two rolling variables instead of a list, reducing space to O(1).)_
- What about very large n where integer overflow matters? _(Tests that Python handles arbitrary-precision integers natively, so overflow is not a concern.)_
- Can you compute Fibonacci in O(log n) time? _(Tests knowledge of matrix exponentiation: [[1,1],[1,0]]^n gives the n-th Fibonacci number.)_

## Related

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