Quick Overview

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 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.

Overview: 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

  1. Maintain two variables a and b; yield a then update a, b = b, a + b
  2. Use a while True loop to create an infinite generator and take only n values
  3. Edge case: when n is 0, return an empty list

Loading coding console...

Show the approach

Approach

The inner generator fib_gen maintains state in variables a and b. Each call to next(gen) yields the current value a and then advances the state to the next pair (b, a+b). This is lazy: numbers are computed only when next is called. The outer function calls next exactly n times and collects the results into a list.

Time complexity:
O(n)
Space complexity:
O(1) extra (excluding the output list)