Memoization to Optimize Recursion in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memoization map for caching results.

DSA C++

std::unordered_map<int, int> [1];

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

Amemo

Bcache

Cvisited

Dresults

Attempts:

3 left

💡 Hint

Common Mistakes

Using a variable name that is not descriptive or common for memoization.

Forgetting to declare the map before using it.

The memoization map is commonly named 'memo' to store computed results for reuse.

2fill in blank

medium

Complete the code to check if the result for 'n' is already computed in memo.

DSA C++

if ([1].find(n) != [1].end()) return [1][n];

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

Acache

Bmemo

Cvisited

Dresults

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different variable name than the memo map.

Not checking for the key before accessing the map.

We check the 'memo' map to see if 'n' has a cached result to avoid recomputation.

3fill in blank

hard

Fix the error in the recursive Fibonacci function by adding memoization storage.

DSA C++

int fib(int n, std::unordered_map<int, int>& memo) {
    if (n <= 1) return n;
    if (memo.find(n) != memo.end()) return memo[n];
    memo[n] = fib(n - 1, [1]) + fib(n - 2, memo);
    return memo[n];
}

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

Acache

Bresults

Cvisited

Dmemo

Attempts:

3 left

💡 Hint

Common Mistakes

Passing a different variable name or not passing the memo map at all.

Not storing the computed result in the memo map.

The recursive calls must pass the same memo map to store and reuse results.

4fill in blank

hard

Fill both blanks to complete the memoized factorial function.

DSA C++

int factorial(int n, std::unordered_map<int, int>& memo) {
    if (n <= 1) return 1;
    if (memo.find(n) != memo.end()) return memo[n];
    memo[n] = n [1] factorial([2], memo);
    return memo[n];
}

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

A*

Bn - 1

Cn + 1

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication.

Using 'n + 1' instead of 'n - 1' in recursion.

Factorial is n multiplied by factorial of (n - 1).

5fill in blank

hard

Fill all three blanks to create a memoized function that returns the nth Tribonacci number.

DSA C++

int tribonacci(int n, std::unordered_map<int, int>& memo) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    if (memo.find(n) != memo.end()) return memo[n];
    memo[n] = tribonacci(n [1], memo) + tribonacci(n [2], memo) + tribonacci(n [3], memo);
    return memo[n];
}

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

A- 1

B- 2

C- 3

D+ 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in indices.

Using wrong indices like '+ 1' which causes infinite recursion.

Tribonacci is sum of previous three numbers: n-1, n-2, and n-3.

Practice

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

easy

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

B. To avoid using any variables inside the function

C. To convert recursion into iteration automatically

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

Solution

1. Step 1: Understand what memoization does

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

2. Step 2: Identify the effect on performance

   This reuse of results reduces repeated work and speeds up the function.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed recursion [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with converting recursion to loops
• Believing memoization removes all variables

2. Which of the following is the correct way to declare a memoization cache for a Fibonacci function in C++?

easy

A. std::unordered_map<int> memo;

B. std::vector<int> memo(100, -1);

C. int memo[];

D. map<int> memo;

Solution

1. Step 1: Identify suitable container for memoization

   We need a container that can store integer results indexed by integer keys. std::vector<int> initialized with -1 is common for fixed size memoization.

2. Step 2: Check syntax correctness

   std::vector<int> memo(100, -1); correctly declares a vector of size 100 with all values -1, which can be used to check if a value is computed.

3. Final Answer:

   std::vector<int> memo(100, -1); -> Option B

4. Quick Check:

   Vector with size and default value = Correct memo cache [OK]

Hint: Use vector with size and default -1 for memo cache [OK]

Common Mistakes:

• Using incomplete or wrong container syntax
• Not initializing memo with default values
• Using map without specifying key and value types

3. What will be the output of the following C++ code snippet?

int fib(int n, std::vector<int>& memo) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

int main() {
  std::vector<int> memo(6, -1);
  std::cout << fib(5, memo);
  return 0;
}

medium

A. Error: vector index out of range

B. 8

C. 5

D. 3

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) calculates Fibonacci number at position 5 using memo to avoid repeated calls.

2. Step 2: Calculate fib(5)

   Fibonacci sequence: 0,1,1,2,3,5,... fib(5) = 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: fib(5) = 5 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Assuming vector size too small causes error
• Ignoring memoization effect on output

4. Consider this recursive function with memoization in C++:

int factorial(int n, std::vector<int>& memo) {
  if (n == 0) return 1;
  if (memo[n] != -1) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}

int main() {
  std::vector<int> memo(5, -1);
  std::cout << factorial(5, memo);
  return 0;
}

What is the error in this code?

medium

A. Vector size is too small causing out-of-range access

B. Base case condition is incorrect

C. Memoization check is missing

D. Factorial calculation formula is wrong

Solution

1. Step 1: Check vector size for memoization

   The vector memo has size 5, so valid indices are 0 to 4. But factorial(5) tries to access memo[5], which is out of range.

2. Step 2: Identify consequence of out-of-range access

   Accessing memo[5] causes undefined behavior or runtime error.

3. Final Answer:

   Vector size is too small causing out-of-range access -> Option A

4. Quick Check:

   Memo vector size < n causes error [OK]

Hint: Memo vector size must be >= n+1 to avoid errors [OK]

Common Mistakes:

• Ignoring vector size and indexing
• Thinking base case is wrong
• Assuming memo check is missing

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 applies to this problem in C++?

hard

A. Use a vector<int> memo(n+1, -1) and store results for each stair count

int ways(int n, std::vector<int>& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
if (memo[n] != -1) return memo[n];
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

B. Use a vector<int> memo(n, 0) and store results only for even stairs

int ways(int n, std::vector<int>& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
if (memo[n] != 0) return memo[n];
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

C. Use a map memo and store results only for odd stairs

int ways(int n, std::map& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
if (memo.count(n)) return memo[n];
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

D. Use a vector<int> memo(n+1, 0) but do not check memo before recursive calls

int ways(int n, std::vector<int>& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

Solution

1. Step 1: Understand memoization requirements

   Memo must store results for all n from 0 to n, so vector size n+1 with default -1 is correct.

2. Step 2: Check memo usage in recursion

   Before recursive calls, check if memo[n] is computed (not -1). If yes, return memo[n]. Otherwise, compute and store.

3. Step 3: Analyze options

   Use a vector<int> memo(n+1, -1) and store results for each stair count int ways(int n, std::vector<int>& memo) { if (n == 0) return 1; if (n < 0) return 0; if (memo[n] != -1) return memo[n]; memo[n] = ways(n-1, memo) + ways(n-2, memo); return memo[n]; } correctly implements memoization with vector size n+1, default -1, and memo check before recursion.

4. Final Answer:

   Option A code correctly applies memoization for climbing stairs problem -> Option A

5. Quick Check:

   Memo vector size n+1 and check before recursion = Correct [OK]

Hint: Memo vector size n+1 with -1 and check before recursion [OK]

Common Mistakes:

• Using wrong vector size causing out-of-range errors
• Not checking memo before recursive calls
• Storing results only for some stairs (odd/even)