Jobs

Interviews

Discussions

Generate Fibonacci Sequence

Easy

Asked by:

25 views

Topics:

Recursion

Write a generator function that returns a generator object which yields the fibonacci sequence.

The fibonacci sequence is defined by the relation X_n = X_n-1 + X_n-2.

The first few numbers of the series are 0, 1, 1, 2, 3, 5, 8, 13.

Example 1:

Input: callCount = 5
Output: [0,1,1,2,3]
Explanation:
const gen = fibGenerator();
gen.next().value; // 0
gen.next().value; // 1
gen.next().value; // 1
gen.next().value; // 2
gen.next().value; // 3

Example 2:

Input: callCount = 0
Output: []
Explanation: gen.next() is never called so nothing is outputted

Constraints:

0 <= callCount <= 50

Try coding it in LeetCode

Generate Fibonacci Sequence

Easy

Asked by:

25 views

Topics:

Recursion

Write a generator function that returns a generator object which yields the fibonacci sequence.

The fibonacci sequence is defined by the relation X_n = X_n-1 + X_n-2.

The first few numbers of the series are 0, 1, 1, 2, 3, 5, 8, 13.

Example 1:

Input: callCount = 5
Output: [0,1,1,2,3]
Explanation:
const gen = fibGenerator();
gen.next().value; // 0
gen.next().value; // 1
gen.next().value; // 1
gen.next().value; // 2
gen.next().value; // 3

Example 2:

Input: callCount = 0
Output: []
Explanation: gen.next() is never called so nothing is outputted

Constraints:

0 <= callCount <= 50

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What range of numbers can the input 'n' fall within, and should I expect it to always be a non-negative integer?
Should the Fibonacci sequence start with 0 or 1, or should I consider the user's choice via an argument?
What should the function return if n is 0 or 1? Should I return an empty list, a list with a single element, or follow the typical Fibonacci sequence definition?
Should I return the Fibonacci sequence as a list of integers, or is there a different desired data structure (e.g., a string representation)?
Do you want me to print the Fibonacci sequence to the console, or return it as the output of the function?

Brute Force Solution

Approach

The Fibonacci sequence starts with 0 and 1. The brute force approach calculates each number in the sequence by directly using the definition: each number is the sum of the two preceding numbers.

Here's how the algorithm would work step-by-step:

To find the first Fibonacci number, it's already given as 0, so we know it.
To find the second Fibonacci number, it's also given as 1, so we know it.
To find the third Fibonacci number, add the first and second Fibonacci numbers (0 + 1), which gives us 1.
To find the fourth Fibonacci number, add the second and third Fibonacci numbers (1 + 1), which gives us 2.
Keep repeating this process. To find any Fibonacci number, simply add the two Fibonacci numbers that came right before it.
Continue this addition until you've found all the Fibonacci numbers up to the number you're trying to find.

Code Implementation

def generate_fibonacci_sequence_brute_force(number_of_terms):
    fibonacci_sequence = []

    if number_of_terms <= 0:
        return fibonacci_sequence

    # First Fibonacci number is 0
    fibonacci_sequence.append(0)

    if number_of_terms == 1:
        return fibonacci_sequence

    # Second Fibonacci number is 1
    fibonacci_sequence.append(1)

    if number_of_terms == 2:
        return fibonacci_sequence

    # Need to calculate subsequent numbers based on previous two
    for i in range(2, number_of_terms):

        # Sum the prior two elements
        next_fibonacci_number = fibonacci_sequence[i - 1] + fibonacci_sequence[i - 2]

        # Add number to sequence
        fibonacci_sequence.append(next_fibonacci_number)

    return fibonacci_sequence

Big(O) Analysis

Time Complexity

O(n) – The provided explanation describes an iterative approach to generate the Fibonacci sequence up to the nth number. The core operation is summing the two preceding Fibonacci numbers to calculate the next one. This operation is performed repeatedly within a single loop that iterates from 2 up to n. Therefore, the time complexity is directly proportional to the input size n, resulting in a linear time complexity of O(n).

Space Complexity

O(N) – The problem description explains generating Fibonacci numbers sequentially up to a given number. This implies storing each calculated Fibonacci number in a data structure, such as a list or array. The size of this data structure grows linearly with the input number N, where N is the number of Fibonacci numbers to generate. Therefore, the auxiliary space used to store the Fibonacci sequence is proportional to N, making the space complexity O(N).

Optimal Solution

Approach

The most efficient way to generate the Fibonacci sequence avoids recalculating values. Instead, we remember the last two numbers in the sequence to quickly compute the next one. This process builds the sequence one number at a time using values that were already computed.

Here's how the algorithm would work step-by-step:

Start with the first two Fibonacci numbers: 0 and 1.
To get the next number, simply add the previous two numbers together.
After calculating the next number, update your 'previous two numbers' to include the newest number you just calculated. This is done by discarding the oldest and including the most recent.
Repeat the addition and update steps until you have generated the desired number of Fibonacci numbers.

Code Implementation

def generate_fibonacci_sequence(number_of_terms):
    fibonacci_sequence = []
    if number_of_terms <= 0:
        return fibonacci_sequence

    previous_number = 0
    current_number = 1
    fibonacci_sequence.append(previous_number)

    if number_of_terms == 1:
        return fibonacci_sequence

    fibonacci_sequence.append(current_number)

    # Start from 2 since we already have the first two terms.
    for i in range(2, number_of_terms):
        # Calculate the next Fibonacci number.
        next_number = previous_number + current_number

        fibonacci_sequence.append(next_number)

        # Update the last two numbers for the next iteration.
        previous_number = current_number

        current_number = next_number

    return fibonacci_sequence

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates n times, where n is the desired number of Fibonacci numbers. Inside the loop, it performs a constant number of operations: adding the previous two numbers and updating the variables to store the sequence's last two values. Because the number of operations within each iteration of the loop remains constant, the time complexity is directly proportional to n, resulting in a time complexity of O(n).

Space Complexity

O(1) – The algorithm described only stores the two most recent Fibonacci numbers to calculate the next. This requires a fixed amount of extra memory, specifically two variables to hold these numbers. The space used does not depend on the number of Fibonacci numbers to be generated (N). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Negative input n	Return an empty list or raise an IllegalArgumentException, as the Fibonacci sequence is typically defined for non-negative integers.
Zero input n	Return a list containing only [0] or an empty list based on specific requirements, as F(0) = 0.
Input n = 1	Return a list containing [0, 1] or just [0] and [1], depending if starting from zero is desired.
Large input n leading to integer overflow	Use a data type with larger capacity like 'long' in Java/C++ or consider using arbitrary-precision arithmetic libraries to handle very large Fibonacci numbers accurately.
Extremely large n causing excessive memory allocation	Use iterative approach that stores only the last two Fibonacci numbers, avoiding storing the entire sequence in memory.
n is not an integer	Cast the input to an integer or throw IllegalArgumentException if the algorithm expects only integers.
Input n as a very large number as string	Convert string representation of n to numeric type using appropriate libraries.
Requesting a Fibonacci sequence starting from an arbitrary point (not 0)	Adjust the iterative process to begin calculating the Fibonacci sequence from the desired index, and ensure correct handling of indices.

Negative input n

How to Handle:

Return an empty list or raise an IllegalArgumentException, as the Fibonacci sequence is typically defined for non-negative integers.

Zero input n

How to Handle:

Return a list containing only [0] or an empty list based on specific requirements, as F(0) = 0.

Input n = 1

How to Handle:

Return a list containing [0, 1] or just [0] and [1], depending if starting from zero is desired.

Large input n leading to integer overflow

How to Handle:

Use a data type with larger capacity like 'long' in Java/C++ or consider using arbitrary-precision arithmetic libraries to handle very large Fibonacci numbers accurately.

Extremely large n causing excessive memory allocation

How to Handle:

Use iterative approach that stores only the last two Fibonacci numbers, avoiding storing the entire sequence in memory.

n is not an integer

How to Handle:

Cast the input to an integer or throw IllegalArgumentException if the algorithm expects only integers.

Input n as a very large number as string

How to Handle:

Convert string representation of n to numeric type using appropriate libraries.

Requesting a Fibonacci sequence starting from an arbitrary point (not 0)

How to Handle:

Adjust the iterative process to begin calculating the Fibonacci sequence from the desired index, and ensure correct handling of indices.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What range of numbers can the input 'n' fall within, and should I expect it to always be a non-negative integer?
Should the Fibonacci sequence start with 0 or 1, or should I consider the user's choice via an argument?
What should the function return if n is 0 or 1? Should I return an empty list, a list with a single element, or follow the typical Fibonacci sequence definition?
Should I return the Fibonacci sequence as a list of integers, or is there a different desired data structure (e.g., a string representation)?
Do you want me to print the Fibonacci sequence to the console, or return it as the output of the function?

Brute Force Solution

Approach

The Fibonacci sequence starts with 0 and 1. The brute force approach calculates each number in the sequence by directly using the definition: each number is the sum of the two preceding numbers.

Here's how the algorithm would work step-by-step:

To find the first Fibonacci number, it's already given as 0, so we know it.
To find the second Fibonacci number, it's also given as 1, so we know it.
To find the third Fibonacci number, add the first and second Fibonacci numbers (0 + 1), which gives us 1.
To find the fourth Fibonacci number, add the second and third Fibonacci numbers (1 + 1), which gives us 2.
Keep repeating this process. To find any Fibonacci number, simply add the two Fibonacci numbers that came right before it.
Continue this addition until you've found all the Fibonacci numbers up to the number you're trying to find.

Code Implementation

def generate_fibonacci_sequence_brute_force(number_of_terms):
    fibonacci_sequence = []

    if number_of_terms <= 0:
        return fibonacci_sequence

    # First Fibonacci number is 0
    fibonacci_sequence.append(0)

    if number_of_terms == 1:
        return fibonacci_sequence

    # Second Fibonacci number is 1
    fibonacci_sequence.append(1)

    if number_of_terms == 2:
        return fibonacci_sequence

    # Need to calculate subsequent numbers based on previous two
    for i in range(2, number_of_terms):

        # Sum the prior two elements
        next_fibonacci_number = fibonacci_sequence[i - 1] + fibonacci_sequence[i - 2]

        # Add number to sequence
        fibonacci_sequence.append(next_fibonacci_number)

    return fibonacci_sequence

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first two Fibonacci numbers: 0 and 1.
To get the next number, simply add the previous two numbers together.
After calculating the next number, update your 'previous two numbers' to include the newest number you just calculated. This is done by discarding the oldest and including the most recent.
Repeat the addition and update steps until you have generated the desired number of Fibonacci numbers.

Code Implementation

def generate_fibonacci_sequence(number_of_terms):
    fibonacci_sequence = []
    if number_of_terms <= 0:
        return fibonacci_sequence

    previous_number = 0
    current_number = 1
    fibonacci_sequence.append(previous_number)

    if number_of_terms == 1:
        return fibonacci_sequence

    fibonacci_sequence.append(current_number)

    # Start from 2 since we already have the first two terms.
    for i in range(2, number_of_terms):
        # Calculate the next Fibonacci number.
        next_number = previous_number + current_number

        fibonacci_sequence.append(next_number)

        # Update the last two numbers for the next iteration.
        previous_number = current_number

        current_number = next_number

    return fibonacci_sequence

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative input n	Return an empty list or raise an IllegalArgumentException, as the Fibonacci sequence is typically defined for non-negative integers.
Zero input n	Return a list containing only [0] or an empty list based on specific requirements, as F(0) = 0.
Input n = 1	Return a list containing [0, 1] or just [0] and [1], depending if starting from zero is desired.
Large input n leading to integer overflow	Use a data type with larger capacity like 'long' in Java/C++ or consider using arbitrary-precision arithmetic libraries to handle very large Fibonacci numbers accurately.
Extremely large n causing excessive memory allocation	Use iterative approach that stores only the last two Fibonacci numbers, avoiding storing the entire sequence in memory.
n is not an integer	Cast the input to an integer or throw IllegalArgumentException if the algorithm expects only integers.
Input n as a very large number as string	Convert string representation of n to numeric type using appropriate libraries.
Requesting a Fibonacci sequence starting from an arbitrary point (not 0)	Adjust the iterative process to begin calculating the Fibonacci sequence from the desired index, and ensure correct handling of indices.

Negative input n

How to Handle:

Return an empty list or raise an IllegalArgumentException, as the Fibonacci sequence is typically defined for non-negative integers.

Zero input n

How to Handle:

Return a list containing only [0] or an empty list based on specific requirements, as F(0) = 0.

Input n = 1

How to Handle:

Return a list containing [0, 1] or just [0] and [1], depending if starting from zero is desired.

Large input n leading to integer overflow

How to Handle:

Use a data type with larger capacity like 'long' in Java/C++ or consider using arbitrary-precision arithmetic libraries to handle very large Fibonacci numbers accurately.

Extremely large n causing excessive memory allocation

How to Handle:

Use iterative approach that stores only the last two Fibonacci numbers, avoiding storing the entire sequence in memory.

n is not an integer

How to Handle:

Cast the input to an integer or throw IllegalArgumentException if the algorithm expects only integers.

Input n as a very large number as string

How to Handle:

Convert string representation of n to numeric type using appropriate libraries.

Requesting a Fibonacci sequence starting from an arbitrary point (not 0)

How to Handle:

Adjust the iterative process to begin calculating the Fibonacci sequence from the desired index, and ensure correct handling of indices.