Memoization to Optimize Recursion in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a mutable HashMap for memoization.

DSA Rust

let mut memo: std::collections::HashMap<u32, u32> = [1];

Drag options to blanks, or click blank then click option'

ABTreeMap::new()

BHashMap::new()

CHashSet::new()

DVec::new()

Attempts:

3 left

💡 Hint

Common Mistakes

Using Vec or HashSet instead of HashMap.

We use HashMap::new() to create an empty map for memoization.

2fill in blank

medium

Complete the code to check if the result for n is already memoized.

DSA Rust

if let Some(&result) = memo.[1](&n) {
    return result;
}

Drag options to blanks, or click blank then click option'

Acontains_key

Bremove

Cinsert

Dget

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert or contains_key which do not return the value.

We use get to check if n is in the memo map.

3fill in blank

hard

Fix the error in inserting the computed result into the memo map.

DSA Rust

memo.[1](n, result);

Drag options to blanks, or click blank then click option'

Ainsert

Bget

Cremove

Dcontains_key

Attempts:

3 left

💡 Hint

Common Mistakes

Using get or contains_key which do not insert values.

Use insert to add the computed result to the memo map.

4fill in blank

hard

Fill both blanks to complete the recursive Fibonacci function with memoization.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Aget

Binsert

Cremove

Dcontains_key

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping get and insert methods.

Use get to check memo and insert to store the result.

5fill in blank

hard

Fill all three blanks to create a memoized factorial function.

DSA Rust

fn factorial(n: u32, memo: &mut std::collections::HashMap<u32, u32>) -> u32 {
    if n <= 1 {
        return 1;
    }
    if let Some(&result) = memo.[1](&n) {
        return result;
    }
    let result = n * factorial(n [2] 1, memo);
    memo.[3](n, result);
    result
}

Drag options to blanks, or click blank then click option'

Aget

B-

Cinsert

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - in recursion.

Swapping insert and get.

Use get to check memo, subtract 1 in recursion, and insert to store result.

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