The Never-Ending Sequence

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
L5
Asked in
Allen Institute

Problem

The retry-delay table we build from the Fibonacci series always comes back with at least two entries, even for jobs allowed one retry or none. Return exactly the first n terms of the series, starting from 0.

Sequence that keeps going. Follow it.

Example 1

Input:

n = 6

Output:

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

Example 2

Input:

n = 1

Output:

[0]

Worked solution and explanation

This is a length-contract problem in a Fibonacci costume. Everyone knows the recurrence, so writing it proves nothing. The real test is whether your output holds exactly `n` terms when n is smaller than the two-term seed the recurrence needs to get started. The trap is writing result = [0, 1] first and looping after it. That returns [0, 1] for both n = 0 and n = 1, so two of the three examples on screen fail before the loop even runs.

Where the seed leaks

Step 1: Answer n = 0 before anything exists

A job with no retries needs no delays. Returning [] up front means nothing has been allocated yet that could leak into the result. If you leave this case to the loop, the seed still comes back.

Step 2: Answer n = 1 with the first term alone

The recurrence needs two priming terms, but the caller asked for one. [0] is the only correct answer here. Truncating result[:n] at the end also works, but you are then building output you immediately throw away.

Step 3: Seed two terms, then extend from index 2

With n >= 2 guaranteed, [0, 1] is a valid prefix. range(2, n) adds exactly n - 2 more terms, each being result[i - 1] + result[i - 2]. For n = 2 the range is empty and the seed is the whole answer, which is what the hidden case checks.

Guard the short lengths, then extend the seed
def the_never_ending_sequence(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
Seed first
result = [0, 1] followed by the loop. It is correct for n >= 2, but it returns [0, 1] for n = 0 and n = 1 because the seed is emitted no matter what was asked.
Guard first
Return [] and [0] for the two lengths the seed cannot fit, then seed and extend. The output length equals n for every valid input.

Common follow-up questions