The Additive Chain

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

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Antra

Problem

Our retry scheduler spaces attempts by the Fibonacci sequence 0, 1, 1, 2, 3, 5, ..., and a job configured for n retries needs exactly the first n of those delays. Jobs with retries switched off still call it, with n of 0.

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

Example

Input:

n = 7

Output:

[0,1,1,2,3,5,8]

Worked solution and explanation

This is an off-by-one problem wearing a Fibonacci costume. Everyone knows each term is the sum of the previous two. What separates candidates is whether the list holds exactly `n` values at the bottom of the range. The reflex is to seed [0, 1] and loop range(2, n). For n of 0 or 1 that loop never runs, and the seed leaks out unchanged. A job with retries switched off gets two delays, and a single-retry job also gets two.

Walk the boundary first

Step 1: Settle n of 0 and 1 before seeding

Return [] when n <= 0 and [0] when n == 1. These two inputs are exactly the ones the two-value seed cannot represent, so they have to exit before [0, 1] exists.

Step 2: Grow each term from the last two

With [0, 1] in hand, every new value is sequence[i - 1] + sequence[i - 2]. Starting at index 2 means the loop appends exactly n - 2 values.

Step 3: Check the length against n

Trace the edges out loud. For n of 2, range(2, 2) is empty and you return the seed: two values, correct. For n of 7, five appends on top of two seeds give seven. Saying this trace is what convinces an interviewer the boundaries are handled on purpose.

Guard the short cases, then build forward
def fibonacci_iterative(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]
    sequence = [0, 1]
    for i in range(2, n):
        next_value = sequence[i - 1] + sequence[i - 2]
        sequence.append(next_value)
    return sequence
Seed, then loop
sequence = [0, 1] followed by for i in range(2, n). This is right for n of 2 and up, but n of 0 and 1 both return [0, 1] because an empty loop never trims the seed.
Guard, then seed
Return [] for n <= 0 and [0] for n == 1 first. Only then seed [0, 1], so the loop adds n - 2 values and the length always equals n.

Common follow-up questions