Jobs

Interviews

Discussions

Fibonacci Number

Easy

Spotify

0 views

Topics:

RecursionDynamic Programming

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

Fibonacci Number

Easy

Spotify

0 views

Topics:

RecursionDynamic Programming

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30

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 is the expected range for the input integer n? Is there a maximum value I should be aware of?
Should I assume n will always be a non-negative integer?
For very large values of n, should I be concerned about integer overflow? If so, what should I return?
Is there a specific time complexity I should aim for?
Should I optimize for space complexity as well?

Brute Force Solution

Approach

The Fibonacci sequence starts with 0 and 1. To find the nth Fibonacci number using a brute force approach, we'll calculate all the Fibonacci numbers leading up to it by repeatedly adding the previous two.

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, add the previous two numbers together.
Repeat this process, always adding the two most recent numbers to get the next one in the sequence.
Continue until you have calculated the nth number in the sequence. That is your answer.

Code Implementation

def fibonacci_brute_force(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1

    # Initialize the first two Fibonacci numbers.
    previous_fibonacci = 0
    current_fibonacci = 1

    # Iterate to calculate the nth Fibonacci number.
    for _ in range(2, n + 1):

        # Calculate the next Fibonacci number
        # from the sum of the previous two.
        next_fibonacci = previous_fibonacci + current_fibonacci

        # Update previous and current Fibonacci numbers.
        # Necessary to move sequence forward
        previous_fibonacci = current_fibonacci

        current_fibonacci = next_fibonacci

    return current_fibonacci

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The provided solution calculates the nth Fibonacci number by iteratively adding the previous two numbers until it reaches the nth position. This involves a single loop that iterates from 2 up to n. Therefore, the number of operations is directly proportional to n, making the time complexity O(n).

Space Complexity

O(1) – The brute force Fibonacci calculation described only stores the two most recent Fibonacci numbers to calculate the next one. This involves a constant number of variables, such as those holding the previous two numbers and the current number being calculated. The amount of memory required does not scale with the input 'n'. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

To efficiently find a specific Fibonacci number, we avoid recalculating previously computed values. We use a technique where we store and reuse results, allowing us to build up to the desired number directly.

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

Recognize that each Fibonacci number is the sum of the two preceding ones.
Start with the first two Fibonacci numbers, which are both 1.
To find the next number, add the previous two together, and remember the result.
Repeat this process, always adding the last two numbers calculated to get the next one.
Continue calculating and storing these numbers until you reach the Fibonacci number you're looking for.
Since you've been storing all the intermediate calculations, you can simply return the final result without having to recompute anything.

Code Implementation

def fibonacci_number(n):
    if n <= 0:
        return 0

    if n == 1:
        return 1

    previous_fibonacci_number = 1
    current_fibonacci_number = 1

    # Iterate to build Fibonacci sequence
    for _ in range(2, n):
        next_fibonacci_number = previous_fibonacci_number + current_fibonacci_number

        # Update values for next iteration
        previous_fibonacci_number = current_fibonacci_number

        # Store the next fib number
        current_fibonacci_number = next_fibonacci_number

        # Cache results for optimization

    return current_fibonacci_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm calculates the nth Fibonacci number by iteratively computing Fibonacci numbers from the base cases (1 and 1) up to the nth number. The core operation is summing the previous two Fibonacci numbers in each step. This process repeats n times, where n is the input, to arrive at the nth Fibonacci number. Therefore, the number of operations grows linearly with the input n, making the time complexity O(n).

Space Complexity

O(1) – The plain English explanation details an iterative process where only the two most recently calculated Fibonacci numbers are stored to compute the next. This requires keeping track of a fixed number of variables (two numbers and potentially a loop counter), irrespective of the input N, which is the index of the desired Fibonacci number. Since the amount of auxiliary space does not scale with the input, the space complexity is constant.

Edge Cases

Case	How to Handle
Negative input n	Define behavior; either throw an exception, return an error code, or define F(n) for negative n mathematically.
n = 0	Return 0 as per the definition of the Fibonacci sequence F(0) = 0.
n = 1	Return 1 as per the definition of the Fibonacci sequence F(1) = 1.
Large n leading to potential integer overflow	Use a data type capable of holding large Fibonacci numbers (e.g., long or BigInteger) or throw an error if overflow is unavoidable.
Very large n causing stack overflow in recursive implementations	Use an iterative approach or memoization with dynamic programming to avoid excessive recursion depth.
n exceeding available memory for memoization (very large n)	Consider space-optimized dynamic programming (only storing the two previous Fibonacci numbers) or limit the input n.
Input is not an integer (e.g., float, string)	Type-check input n and either cast to integer (if appropriate and safe) or throw an error if non-integer input is not allowed.
n is a very large number but the required value is zero (Modulo arithmetic would cause this result).	Check for this condition and appropriately handle it based on specifications, potentially using approximation to find the correct answer

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 is the expected range for the input integer n? Is there a maximum value I should be aware of?
Should I assume n will always be a non-negative integer?
For very large values of n, should I be concerned about integer overflow? If so, what should I return?
Is there a specific time complexity I should aim for?
Should I optimize for space complexity as well?

Brute Force 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, add the previous two numbers together.
Repeat this process, always adding the two most recent numbers to get the next one in the sequence.
Continue until you have calculated the nth number in the sequence. That is your answer.

Code Implementation

def fibonacci_brute_force(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1

    # Initialize the first two Fibonacci numbers.
    previous_fibonacci = 0
    current_fibonacci = 1

    # Iterate to calculate the nth Fibonacci number.
    for _ in range(2, n + 1):

        # Calculate the next Fibonacci number
        # from the sum of the previous two.
        next_fibonacci = previous_fibonacci + current_fibonacci

        # Update previous and current Fibonacci numbers.
        # Necessary to move sequence forward
        previous_fibonacci = current_fibonacci

        current_fibonacci = next_fibonacci

    return current_fibonacci

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Recognize that each Fibonacci number is the sum of the two preceding ones.
Start with the first two Fibonacci numbers, which are both 1.
To find the next number, add the previous two together, and remember the result.
Repeat this process, always adding the last two numbers calculated to get the next one.
Continue calculating and storing these numbers until you reach the Fibonacci number you're looking for.
Since you've been storing all the intermediate calculations, you can simply return the final result without having to recompute anything.

Code Implementation

def fibonacci_number(n):
    if n <= 0:
        return 0

    if n == 1:
        return 1

    previous_fibonacci_number = 1
    current_fibonacci_number = 1

    # Iterate to build Fibonacci sequence
    for _ in range(2, n):
        next_fibonacci_number = previous_fibonacci_number + current_fibonacci_number

        # Update values for next iteration
        previous_fibonacci_number = current_fibonacci_number

        # Store the next fib number
        current_fibonacci_number = next_fibonacci_number

        # Cache results for optimization

    return current_fibonacci_number

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative input n	Define behavior; either throw an exception, return an error code, or define F(n) for negative n mathematically.
n = 0	Return 0 as per the definition of the Fibonacci sequence F(0) = 0.
n = 1	Return 1 as per the definition of the Fibonacci sequence F(1) = 1.
Large n leading to potential integer overflow	Use a data type capable of holding large Fibonacci numbers (e.g., long or BigInteger) or throw an error if overflow is unavoidable.
Very large n causing stack overflow in recursive implementations	Use an iterative approach or memoization with dynamic programming to avoid excessive recursion depth.
n exceeding available memory for memoization (very large n)	Consider space-optimized dynamic programming (only storing the two previous Fibonacci numbers) or limit the input n.
Input is not an integer (e.g., float, string)	Type-check input n and either cast to integer (if appropriate and safe) or throw an error if non-integer input is not allowed.
n is a very large number but the required value is zero (Modulo arithmetic would cause this result).	Check for this condition and appropriately handle it based on specifications, potentially using approximation to find the correct answer