Memoized Fibonacci Practice Problem

This data science coding problem helps you practice Functions & Scope, memoized fibonacci, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Functions & Scope.

• Problem ID: 83
• Problem key: 83-memoized-fibonacci
• URL: https://datacrack.app/solve/83-memoized-fibonacci
• Difficulty: medium
• Topic: Functions & Scope
• Module: Python Fundamentals

Problem Statement

# 🧩 Memoized Fibonacci

---

### 🎯 Goal
Naive recursive Fibonacci is exponentially slow — `fib(35)` makes over 29 million recursive calls. **Memoization** fixes this by caching results you've already computed. This is your introduction to the **space-time tradeoff** — a concept fundamental to efficient algorithms and ML system design.

---

### 🔍 The Problem with Naive Recursion

```
fib(5)
├── fib(4)
│   ├── fib(3)      ← computed twice!
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)      ← computed twice!
└── fib(3)          ← computed twice!
    ├── fib(2)
    └── fib(1)
```

With memoization, each sub-problem is computed **exactly once** and cached.

---

### 💻 Task
Implement `memoized_fibonacci(n)` using a dictionary as a cache.

---

### 📥 Input
- `n`: int — compute the nth Fibonacci number (0-indexed: fib(0) = 0, fib(1) = 1)

### 📤 Output
- int — the nth Fibonacci number

---

### 🧩 Starter Code
```python
def memoized_fibonacci(n, cache=None):
    """
    Compute the nth Fibonacci number using memoization.

    Args:
        n (int): Index of the Fibonacci number to compute
        cache (dict): Memoization cache (created automatically)

    Returns:
        int: The nth Fibonacci number
    """
    if cache is None:
        cache = {}

    # 🧠 TODO: Handle base cases (n == 0 returns 0, n == 1 returns 1)
    # 🧠 TODO: Check if n is already in cache — if so, return cache[n]
    # 🧠 TODO: Compute fib(n-1) + fib(n-2), store in cache, return it
    pass
```

---

### 💡 Example
```python
memoized_fibonacci(10)   # Expected: 55
memoized_fibonacci(30)   # Expected: 832040
memoized_fibonacci(35)   # Expected: 9227465  (fast with memoization!)
```

---

### 🔑 Key Concepts
- Cache (dict) stores: `{n: fib(n)}` for each computed value
- Default mutable arguments (`cache=None` + `if cache is None`) — avoid `def f(cache={})` which shares state
- This is **dynamic programming** — top-down style

Starter Code

def memoized_fibonacci(n, cache=None):
    """
    Compute the nth Fibonacci number using memoization.

    Args:
        n (int): Index of the Fibonacci number to compute
        cache (dict): Memoization cache (created automatically)

    Returns:
        int: The nth Fibonacci number
    """
    if cache is None:
        cache = {}

    # 🧠 TODO: Handle base cases (n == 0 returns 0, n == 1 returns 1)
    # 🧠 TODO: Check if n is already in cache — if so, return cache[n]
    # 🧠 TODO: Compute fib(n-1) + fib(n-2), store in cache, return it
    pass