Memoization to Optimize Recursion in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memo array for storing computed Fibonacci values.

DSA C

int memo[[1]];

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

A0

B-1

C10

D1000

Attempts:

3 left

💡 Hint

Common Mistakes

Using size 0 or negative size for the array.

Using too small size that can't hold needed Fibonacci numbers.

We declare the memo array with size 1000 to store Fibonacci values up to index 999.

2fill in blank

medium

Complete the code to initialize the memo array with -1 to indicate uncomputed values.

DSA C

for (int i = 0; i < 1000; i++) {
    memo[i] = [1];
}

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

A0

B-1

C1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 0 which is a valid Fibonacci number.

Not initializing the memo array at all.

We use -1 to mark that the Fibonacci value at that index is not yet computed.

3fill in blank

hard

Fix the error in the recursive Fibonacci function to use memoization correctly.

DSA C

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != [1]) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

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

A-1

B1

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of -1.

Not returning memo[n] when already computed.

We check if memo[n] is not -1 to know if the value was computed before.

4fill in blank

hard

Fill both blanks to complete the memoized Fibonacci function with proper base case and memo check.

DSA C

int fib(int n) {
    if (n [1] 1) return n;
    if (memo[n] != [2]) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

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

A<=

B<

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '<=' for base case.

Checking memo[n] against 0 instead of -1.

The base case is when n is less than or equal to 1, and memo[n] is checked against -1 for uncomputed.

5fill in blank

hard

Fill all three blanks to complete the memoized Fibonacci function with initialization, base case, and memo check.

DSA C

void init_memo() {
    for (int i = 0; i < 1000; i++) {
        memo[i] = [1];
    }
}

int fib(int n) {
    if (n [2] 1) return n;
    if (memo[n] != [3]) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

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

A-1

B<=

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of -1 for initialization or memo check.

Using '<' instead of '<=' for base case.

Initialize memo with -1, base case is n <= 1, and memo check is against -1.