Generate Fibonacci Sequence

Generate Fibonacci Sequence

What is this problem about?

The Generate Fibonacci Sequence interview question asks you to implement a function (often a generator in JavaScript or Python) that yields the Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent number is the sum of the previous two ($0, 1, 1, 2, 3, 5, 8, \dots$). You are typically asked to generate the sequence indefinitely or up to a certain $n$.

Why is this asked in interviews?

Google and Bloomberg use this "Easy" problem to test your understanding of Generators and basic iterative logic. It evaluation whether you know how to maintain state across function calls without using global variables. While simple, it often serves as a warm-up before moving on to more complex questions involving memoization or dynamic programming optimizations.

Algorithmic pattern used

This problem uses a simple Iterative pattern or a Generator pattern.

1. Initialize two variables, a = 0 and b = 1.
2. In an infinite loop (or up to $n$):
   • Yield (or return) the current value of a.
   • Update the variables: the new a becomes the old b, and the new b becomes the sum of the old a and b. This approach uses $O(1)$ space and $O(n)$ time.

Example explanation

1. Initial: a = 0, b = 1. Yield 0.
2. Update: a = 1, b = 0 + 1 = 1. Yield 1.
3. Update: a = 1, b = 1 + 1 = 2. Yield 1.
4. Update: a = 2, b = 1 + 2 = 3. Yield 2.
5. Update: a = 3, b = 2 + 3 = 5. Yield 3.

Common mistakes candidates make

• Recursive Implementation: Using naive recursion f(n) = f(n-1) + f(n-2) without memoization, which leads to $O(2^n)$ complexity.
• Starting values: Forgetting that the sequence starts with 0, not 1.
• Memory usage: Storing the entire sequence in an array when only the last two values are needed to generate the next one.

Interview preparation tip

Understand the difference between a "function" and a "generator." Generators are memory-efficient because they produce values on the fly (lazy evaluation) rather than computing everything upfront.