Memoization to Optimize Recursion in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of this Rust code that calculates Fibonacci numbers using memoization?

DSA Rust

use std::collections::HashMap;

fn fib(n: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    if let Some(&val) = memo.get(&n) {
        return val;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    let result = fib(10, &mut memo);
    println!("{}", result);
}

A 89

B 55

C 34

D 144

💡 Hint

Recall that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

The 10th Fibonacci number (starting from 0) is 55. The memoization stores intermediate results to avoid repeated calculations.

❓ Predict Output

intermediate

Memoized Factorial Calculation Output

What is printed by this Rust program that uses memoization to compute factorial?

DSA Rust

use std::collections::HashMap;

fn factorial(n: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    if n == 0 {
        return 1;
    }
    if let Some(&val) = memo.get(&n) {
        return val;
    }
    let result = n as u64 * factorial(n - 1, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    let result = factorial(5, &mut memo);
    println!("{}", result);
}

A 720

B 24

C 120

D 60

💡 Hint

Factorial of 5 is 5 * 4 * 3 * 2 * 1.

The factorial of 5 is 120. Memoization caches intermediate factorial values to avoid repeated calculations.

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

This Rust code attempts to compute Fibonacci numbers with memoization but causes a runtime error. What is the error?

DSA Rust

use std::collections::HashMap;

fn fib(n: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    if n <= 1 {
        return n as u64;
    }
    if memo.contains_key(&n) {
        return memo[&n];
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    let result = fib(50, &mut memo);
    println!("{}", result);
}

A Panic due to integer overflow

B Borrow checker error due to mutable and immutable borrow conflict

C No error, prints 12586269025

D Stack overflow due to deep recursion

💡 Hint

Consider the recursion depth and Rust's default stack size.

Even with memoization, the recursion depth for fib(50) is large and can cause stack overflow in Rust without tail recursion optimization.

🧠 Conceptual

advanced

Memoization vs Tabulation

Which statement correctly describes the difference between memoization and tabulation in dynamic programming?

A Memoization uses recursion with caching, tabulation uses iteration without recursion

B Memoization solves subproblems bottom-up, tabulation solves top-down with caching

C Memoization requires more memory than tabulation always

D Tabulation cannot be used for Fibonacci sequence calculation

💡 Hint

Think about recursion and iteration approaches.

Memoization is top-down recursion with caching results; tabulation is bottom-up iteration building solutions from smaller subproblems.

🚀 Application

expert

Memoization to Optimize Grid Path Counting

Consider a grid of size 3x3. You can move only right or down from the top-left corner to the bottom-right corner. Using memoization, how many unique paths are there?

A 6

B 9

C 12

D 15

💡 Hint

Number of unique paths in an m x n grid is (m+n-2) choose (m-1).

For a 3x3 grid, unique paths = C(4,2) = 6. Memoization helps avoid recomputing paths for subgrids.

Practice

1. What is the main purpose of using memoization in recursive functions?

easy

A. To store results of expensive function calls and reuse them

B. To make the function run slower by adding extra steps

C. To avoid using recursion altogether

D. To increase the memory usage without any benefit

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so that if the same inputs occur again, the saved result is used instead of recalculating.

2. Step 2: Identify the benefit in recursion

   This avoids repeated calculations in recursive calls, making the function faster and more efficient.

3. Final Answer:

   To store results of expensive function calls and reuse them -> Option A

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated work by caching results [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with avoiding recursion
• Believing memoization always increases memory without benefit

2. Which of the following Rust code snippets correctly declares a memoization cache using a HashMap for a recursive function?

easy

A. let mut memo = Vec::new();

B. let memo = HashMap;

C. let memo: HashMap = new HashMap();

D. let mut memo: HashMap = HashMap::new();

Solution

1. Step 1: Check correct HashMap initialization syntax

   In Rust, to create a mutable HashMap, you use let mut memo: HashMap<u32, u32> = HashMap::new();.

2. Step 2: Identify incorrect options

   Vec::new() uses the wrong type. let memo = HashMap<u32, u32>; misses mut and HashMap::new(). let memo: HashMap = new HashMap(); has invalid syntax.

3. Final Answer:

   let mut memo: HashMap<u32, u32> = HashMap::new(); -> Option D

4. Quick Check:

   Correct HashMap init = let mut memo: HashMap<u32, u32> = HashMap::new(); [OK]

Hint: Use HashMap::new() with mut for memo cache [OK]

Common Mistakes:

• Forgetting to make the HashMap mutable
• Using Vec instead of HashMap for memoization
• Missing the ::new() method call

3. What will be the output of the following Rust code?

use std::collections::HashMap;

fn fib(n: u32, memo: &mut HashMap) -> u32 {
    if n <= 1 {
        return n;
    }
    if let Some(&val) = memo.get(&n) {
        return val;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    println!("{}", fib(5, &mut memo));
}

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand the Fibonacci function with memoization

   The function returns the nth Fibonacci number. fib(0)=0, fib(1)=1, fib(5) = fib(4)+fib(3).

2. Step 2: Calculate fib(5)

   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5. The memo cache stores intermediate results to avoid repeated calls.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect on performance
• Misreading base cases as 1 instead of 0

4. Identify the bug in this Rust recursive function using memoization:

use std::collections::HashMap;

fn factorial(n: u32, memo: &mut HashMap) -> u32 {
    if n == 0 {
        return 1;
    }
    if memo.contains_key(&n) {
        return *memo[&n];
    }
    let result = n * factorial(n - 1, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    println!("{}", factorial(5, &mut memo));
}

medium

A. Using memo[&n] causes a panic if key is missing

B. Base case should be n == 1 instead of n == 0

C. Missing mutable borrow for memo in recursive call

D. Factorial function does not use memoization

Solution

1. Step 1: Check how memo is accessed

   Using memo[&n] directly can panic if the key is missing. Better to use memo.get(&n) or unwrap safely.

2. Step 2: Verify base case and memo usage

   Base case n==0 is correct for factorial. Memo is passed mutably correctly. Memoization is used properly except for unsafe access.

3. Final Answer:

   Using memo[&n] causes a panic if key is missing -> Option A

4. Quick Check:

   Unsafe HashMap access = Using memo[&n] causes a panic if key is missing [OK]

Hint: Use memo.get() to safely access HashMap keys [OK]

Common Mistakes:

• Assuming memo[&n] never panics
• Changing correct base case unnecessarily
• Forgetting to pass memo mutably

5. You want to optimize a recursive function that calculates the number of ways to climb n stairs, taking 1 or 2 steps at a time. Which memoization approach below correctly implements this in Rust?

medium

A. Use a global variable to count calls without storing intermediate results

B. Use a vector without initializing it with default values

C. Use a mutable HashMap to store results keyed by stair number and check before recursive calls

D. Recompute all values each time without caching

Solution

1. Step 1: Understand the problem and memoization need

   Calculating ways to climb stairs with 1 or 2 steps is a classic recursion problem that benefits from memoization to avoid repeated calculations.

2. Step 2: Identify correct memoization method

   Using a mutable HashMap keyed by stair number to store and reuse results before recursive calls is the correct approach. Other options either do not store results or do not initialize storage properly.

3. Final Answer:

   Use a mutable HashMap to store results keyed by stair number and check before recursive calls -> Option C

4. Quick Check:

   Memoize with HashMap keyed by input = Use a mutable HashMap to store results keyed by stair number and check before recursive calls [OK]

Hint: Cache results keyed by input to avoid recomputation [OK]

Common Mistakes:

• Not storing intermediate results
• Using global counters instead of memo
• Using uninitialized vectors for memo