🏷️ Category: Algorithms / Dynamic Programming  |  🎯 Difficulty: Easy  |  🔥 Frequency: ★★★★★

📋 Problem Statement

Return the nth Fibonacci Sequence number. The sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21…

📥 Input  → n = 6    📤 Output → 8
📥 Input  → n = 10   📤 Output → 55
📥 Input  → n = 0    📤 Output → 0

📥 Input  → n = 6    📤 Output → 8
📥 Input  → n = 10   📤 Output → 55
📥 Input  → n = 0    📤 Output → 0

🧠 What the Interviewer is Testing

⚠️ Never give just the naive recursive solution. Always show iterative or memoized version.

💡 Approach

❌ Naive Recursion   → O(2^n)  — exponential, very slow
✅ Iterative        → O(n)    — simple and efficient
✅ Memoized         → O(n)    — recursive with caching
✅ Matrix / Math    → O(logn) — advanced

❌ Naive Recursion   → O(2^n)  — exponential, very slow
✅ Iterative        → O(n)    — simple and efficient
✅ Memoized         → O(n)    — recursive with caching
✅ Matrix / Math    → O(logn) — advanced

✅ Solution 1 — Iterative (Best for interviews)

def fib_iterative(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# ── Test Cases ─────────────────────────────────
print(fib_iterative(6))    # ✅ 8
print(fib_iterative(10))   # ✅ 55
print(fib_iterative(0))    # ✅ 0

def fib_iterative(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# ── Test Cases ─────────────────────────────────
print(fib_iterative(6))    # ✅ 8
print(fib_iterative(10))   # ✅ 55
print(fib_iterative(0))    # ✅ 0

✅ Solution 2 — Memoized Recursive

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(10))   # ✅ 55

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(10))   # ✅ 55

❌ Naive Recursion (for reference — avoid)

# O(2^n) — DO NOT use this in interviews without optimizing
def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# O(2^n) — DO NOT use this in interviews without optimizing
def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

📊 Complexity Analysis

┌──────────────────┬────────────┬──────────────────────────┐
│ Approach         │ Time       │ Space                    │
├──────────────────┼────────────┼──────────────────────────┤
│ Naive Recursive  │ O(2^n)     │ O(n) call stack          │
│ Iterative ✅     │ O(n)       │ O(1)                     │
│ Memoized ✅      │ O(n)       │ O(n) cache               │
└──────────────────┴────────────┴──────────────────────────┘

🎤 How to Explain in the Interview

“The naive recursive solution is O(2^n) because it recalculates the same values repeatedly. The iterative approach is O(n) time and O(1) space — just track the previous two values. With lru_cache, we can keep the recursive style while making it O(n) through memoization.”

“The naive recursive solution is O(2^n) because it recalculates the same values repeatedly. The iterative approach is O(n) time and O(1) space — just track the previous two values. With lru_cache, we can keep the recursive style while making it O(n) through memoization.”

🔁 Common Follow-up Questions

Q1 → Print entire Fibonacci sequence up to n?

def fib_sequence(n: int) -> list:
    if n <= 0: return [0]
    seq = [0, 1]
    while len(seq) <= n:
        seq.append(seq[-1] + seq[-2])
    return seq[:n+1]

def fib_sequence(n: int) -> list:
    if n <= 0: return [0]
    seq = [0, 1]
    while len(seq) <= n:
        seq.append(seq[-1] + seq[-2])
    return seq[:n+1]

Q2 → Using a generator?

def fib_gen(n: int):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

def fib_gen(n: int):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

📁 Set 1 of 4 — Python Interview Prep Series — devprepguide.com