Implement Infinite Fibonacci Generator Using Lazy Evaluation
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Scenario
Testing understanding of Python lazy evaluation and generators.
##### Question
Explain what lazy evaluation means in Python and implement a generator using "yield" that produces an infinite Fibonacci sequence.
##### Hints
Show how state is preserved between yields and why values are computed only when requested.
Quick Answer: This question evaluates understanding of lazy evaluation and Python generator semantics, testing a candidate's ability to work with iterative sequence production and manage state across iterations.
Implement lazy_fibonacci(n) that returns a list of the first n Fibonacci numbers starting at 0. Internally, use a generator with yield that produces an infinite Fibonacci sequence and collect only the first n values. The sequence must be 0, 1, 1, 2, 3, ...
Constraints
- 0 <= n <= 100000
- Use a generator with yield to produce Fibonacci numbers lazily
- Do not use recursion
- Time complexity must be O(n)
- Extra space complexity must be O(1) besides the output list
- Python integers can grow arbitrarily large
Hints
- Maintain two variables a and b; yield a then update a, b = b, a + b
- Use a while True loop to create an infinite generator and take only n values
- Edge case: when n is 0, return an empty list