Fibonacci Number

Fibonacci Number

What is this problem about?

The Fibonacci Number interview question asks you to calculate the $n^{th}$ number in the Fibonacci sequence. The sequence is defined as $F(0) = 0, F(1) = 1$, and $F(n) = F(n-1) + F(n-2)$ for $n > 1$. It's the most common entry point for learning about recursion and optimization.

Why is this asked in interviews?

This is a baseline question asked by almost every company, from J.P. Morgan to Meta. It evaluates your knowledge of Dynamic Programming interview pattern and your ability to optimize an exponential recursion $O(2^N)$ into a linear $O(N)$ or even logarithmic $O(\log N)$ solution. It's often used to see if a candidate understands the concept of "memoization" or "space optimization."

Algorithmic pattern used

There are three main levels of solution for this:

1. Recursion (Inefficient): Call fib(n-1) + fib(n-2). Complexity: O(2^N).
2. Memoization / Iterative DP: Use an array or variables to store previously computed values. Complexity: O(N) time, O(1) space if using variables.
3. Matrix Exponentiation (Advanced): Using the property $\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n$. Complexity: O(log N).

Example explanation

Find $F(4)$:

1. $F(0) = 0$
2. $F(1) = 1$
3. $F(2) = F(1) + F(0) = 1 + 0 = 1$
4. $F(3) = F(2) + F(1) = 1 + 1 = 2$
5. $F(4) = F(3) + F(2) = 2 + 1 = 3$ Result: 3.

Common mistakes candidates make

• Basic Recursion: Implementing the naive recursive solution for $n=30+$, which results in very slow execution.
• Space Usage: Using a full array dp[n+1] when only the previous two numbers are needed.
• Data Types: Not handling cases where the result might exceed 32-bit integer limits (though for standard Fibonacci problems, $n$ is usually small).

Interview preparation tip

Always start with the iterative $O(N)$ solution with $O(1)$ space. It is the most practical and efficient for most interview contexts. If you want to impress, mention the closed-form "Binet's Formula" or the Matrix Exponentiation approach.