Write a generator that yields the first n Fibonacci numbers.
Keep two variables a and b, yield a, then update them with a, b = b, a + b, repeating n times. The generator produces one value at a time, uses O(1) memory and does O(n) additions in total.
Explain it simply
Fibonacci numbers start 0, 1, and each next number is the sum of the previous two. A generator suits this because we can produce numbers lazily and never need the whole list in memory.
Line by line
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
yield a
a, b = b, a + b
print(list(fibonacci(8))) # Output: [0, 1, 1, 2, 3, 5, 8, 13]
gen = fibonacci(3)
print(next(gen)) # Output: 0
print(next(gen)) # Output: 1
print(next(gen)) # Output: 1
print(sum(fibonacci(10))) # Output: 88
print(list(fibonacci(0))) # Output: []After each yield, the function pauses with a and b intact, and it resumes at the next next(). For n = 10 the numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, which add up to 88.
Complexity
Time O(n) additions (big integers grow, so the largest ones cost more). Space O(1), apart from the values you choose to collect.
What to say in the interview
"I use a generator with two running variables, so I never build the list. a, b = b, a + b updates both at once without a temp. If the caller needs only a few terms, it computes only those, and an infinite version just replaces the for loop with while True."