Overlapping Subproblems and Optimal Substructure in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the nth Fibonacci number using recursion.

DSA C

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

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

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting to return the sum.

The Fibonacci number is the sum of the two previous Fibonacci numbers, so we add fib(n-1) and fib(n-2).

2fill in blank

medium

Complete the code to memoize the Fibonacci function using an array.

DSA C

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

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

A*

B-

C/

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operators in the sum.

Not storing the result in memo[n].

Memoization stores the sum of fib(n-1) and fib(n-2) to avoid repeated calculations.

3fill in blank

hard

Fix the error in the code to correctly compute the minimum cost path in a grid using recursion.

DSA C

#include <limits.h>
int minCostPath(int cost[][], int m, int n) {
    if (m == 0 && n == 0) {
        return cost[0][0];
    }
    if (m < 0 || n < 0) {
        return [1];
    }
    int left = minCostPath(cost, m, n - 1);
    int up = minCostPath(cost, m - 1, n);
    return cost[m][n] + (left < up ? left : up);
}

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

Acost[m][n]

B-1

CINT_MAX

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 for invalid indices which can incorrectly lower the cost.

Returning negative values causing wrong minimum calculations.

Returning INT_MAX for invalid indices ensures those paths are not chosen as minimum.

4fill in blank

hard

Fill both blanks to create a bottom-up dynamic programming solution for the Fibonacci sequence.

DSA C

int fibDP(int n) {
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i [1] 1] [2] dp[i - 2];
    }
    return dp[n];
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction for the index.

Using wrong operators for combining previous values.

We subtract 1 to get the previous index and add dp[i-1] and dp[i-2] to get the current Fibonacci number.

5fill in blank

hard

Fill all three blanks to implement a memoized recursive solution for the Longest Common Subsequence (LCS).

DSA C

int lcsMemo(char *X, char *Y, int m, int n, int memo[][100]) {
    if (m == 0 || n == 0) {
        return 0;
    }
    if (memo[m][n] != -1) {
        return memo[m][n];
    }
    if (X[m - 1] [1] Y[n - 1]) {
        memo[m][n] = 1 + lcsMemo(X, Y, m - 1, n - 1, memo);
    } else {
        memo[m][n] = (lcsMemo(X, Y, m - 1, n, memo) [2] lcsMemo(X, Y, m, n - 1, memo));
    }
    return memo[m][n];
}

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

A==

B!=

Cmax

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' instead of '==' for character comparison.

Using '+' instead of max to combine subsequences.

We check if characters are equal with '=='. If not equal, we take the max of the two recursive calls. The last 'A' is for the first blank.