Fibonacci Number
Asked at Meta
Problem
Given n, calculate the nth Fibonacci number where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
How to Think About It
Brute force recursive: fib(n) = fib(n-1) + fib(n-2) with base cases F(0)=0, F(1)=1. Time is O(2^n) due to repeated subproblems.
Memoization: store computed values in a HashMap or array to avoid recomputation. Time becomes O(n), space is O(n).
Bottom-up DP: iterate from 0 to n, storing only the last two values. Time is O(n), space is O(1).
The iterative approach with two variables a and b is the most space-efficient. At each step, compute c = a + b, then shift: a = b, b = c.
Matrix exponentiation can solve it in O(log n) time using the identity [[1,1],[1,0]]^n, but the iterative approach is sufficient for interviews.
Example: fib(6). Steps: a=0,b=1 -> c=1 -> a=1,b=1 -> c=2 -> a=1,b=2 -> c=3 -> a=2,b=3 -> c=5 -> a=3,b=5 -> c=8. Answer is 8.
Optimal Approach
Step 1: Handle base cases: if n <= 1, return n.
Step 2: Initialize two variables: a = 0 (F(0)), b = 1 (F(1)).
Step 3: Loop from 2 to n (inclusive). In each iteration, compute c = a + b, then update a = b, b = c.
Step 4: After the loop, return b (which holds F(n)).
Step 5: Example walkthrough for n = 6:
Start: a=0, b=1
i=2: c=0+1=1, a=1, b=1
i=3: c=1+1=2, a=1, b=2
i=4: c=1+2=3, a=2, b=3
i=5: c=2+3=5, a=3, b=5
i=6: c=3+5=8, a=5, b=8
Return 8.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Writing the naive recursive solution without memoization. It has O(2^n) time and will timeout for n > 35.
Using a full DP array when only two variables are needed. This wastes space unnecessarily.
Off-by-one errors in the loop bounds. Make sure to iterate exactly n-1 times for the two-variable approach.
Forgetting the base cases F(0) = 0 and F(1) = 1. Always clarify the base cases with the interviewer.
Trying to use the closed-form Binet formula with floating point. It loses precision for n > 70 due to floating point limitations.
Solution Code
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bFrequently Asked Questions
What is the Fibonacci Number problem?
Given n, calculate the nth Fibonacci number where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.
How do you solve Fibonacci Number?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Fibonacci Number?
Fibonacci Number is asked at Meta. It is a easy difficulty problem.
What are common mistakes on Fibonacci Number?
- Writing the naive recursive solution without memoization. It has `O(2^n)` time and will timeout for n > 35.
- Using a full DP array when only two variables are needed. This wastes space unnecessarily.
- Off-by-one errors in the loop bounds. Make sure to iterate exactly n-1 times for the two-variable approach.
- Forgetting the base cases F(0) = 0 and F(1) = 1. Always clarify the base cases with the interviewer.
- Trying to use the closed-form Binet formula with floating point. It loses precision for n > 70 due to floating point limitations.