Overlapping Subproblems and Optimal Substructure in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the Fibonacci number at position n using recursion.

DSA C#

public int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) [1] Fibonacci(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 sequence is defined as the sum of the two previous numbers, so we add Fibonacci(n - 1) and Fibonacci(n - 2).

2fill in blank

medium

Complete the code to store computed Fibonacci values in a dictionary to avoid repeated calculations.

DSA C#

private Dictionary<int, int> memo = new Dictionary<int, int>();

public int FibonacciMemo(int n) {
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];
    memo[n] = FibonacciMemo(n - 1) [1] FibonacciMemo(n - 2);
    return memo[n];
}

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

A-

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Not adding the two recursive calls.

Not storing the result in the dictionary.

We add the results of FibonacciMemo(n - 1) and FibonacciMemo(n - 2) and store it in memo to avoid recalculations.

3fill in blank

hard

Fix the error in the recursive factorial function to correctly compute factorial of n.

DSA C#

public int Factorial(int n) {
    if (n == 0) return 1;
    return n [1] Factorial(n - 1);
}

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

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of multiplication.

Forgetting the base case.

Factorial is the product of n and factorial of (n-1), so we use the multiplication operator '*'.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that stores squares of numbers from 1 to 5 only if the number is even.

DSA C#

var squares = new Dictionary<int, int>();
for (int i = 1; i <= 5; i++) {
    if (i [1] 2 == 0) {
        squares[i] = i [2] i;
    }
}

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

A%

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '-' instead of '%' for even check.

Using '+' instead of '*' for squaring.

We use '%' to check if i is even (remainder 0) and '*' to compute the square of i.

5fill in blank

hard

Fill all three blanks to create a dictionary that stores uppercase keys and their values only if the value is greater than 10.

DSA C#

var filteredDict = new Dictionary<string, int>();
foreach (var kvp in data) {
    if (kvp.Value [1] 10) {
        filteredDict[kvp.Key.[2]()] = kvp.[3];
    }
}

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

A<

B>

CValue

DToUpper

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for comparison.

Using 'Key' instead of 'Value' for dictionary value.

Not converting key to uppercase.

We check if value is greater than 10 using '>', convert key to uppercase with 'ToUpper', and access value with 'Value'.

Practice

1. Which of the following best describes the concept of Overlapping Subproblems in dynamic programming?

easy

A. The problem has a unique solution that can be found without recursion.

B. The problem can be broken down into smaller subproblems which are solved multiple times.

C. The problem requires sorting before solving.

D. The problem can only be solved using greedy algorithms.

Solution

1. Step 1: Understand Overlapping Subproblems

   Overlapping subproblems means the same smaller problems appear multiple times during the solution process.

2. Step 2: Match with options

   The problem can be broken down into smaller subproblems which are solved multiple times. correctly states that subproblems are solved multiple times, which is the key idea behind overlapping subproblems.

3. Final Answer:

   The problem can be broken down into smaller subproblems which are solved multiple times. -> Option B

4. Quick Check:

   Overlapping Subproblems = The problem can be broken down into smaller subproblems which are solved multiple times. [OK]

Hint: Look for repeated smaller problems solved multiple times [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking greedy algorithms always apply
• Ignoring recursion or repeated calculations

2. Which of the following C# method signatures correctly represents a memoized Fibonacci function using recursion?

easy

A. string Fib(int n, Dictionary memo)

B. void Fib(int n)

C. int Fib(int n, int[] memo)

D. int Fib(int n, Dictionary memo)

Solution

1. Step 1: Identify correct return type and parameters

   The Fibonacci function returns an integer and uses a dictionary to store computed values for memoization.

2. Step 2: Check options for matching signature

   int Fib(int n, Dictionary memo) returns int and takes an int and a Dictionary for memo, which is correct for memoized recursion.

3. Final Answer:

   int Fib(int n, Dictionary memo) -> Option D

4. Quick Check:

   Memoized Fib signature = int Fib(int n, Dictionary memo) [OK]

Hint: Memoized functions usually take a cache parameter like Dictionary [OK]

Common Mistakes:

• Using void return type instead of int
• Using wrong data structure for memo
• Returning string instead of int

3. What is the output of the following C# code?

static int Fib(int n, int[] memo) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = Fib(n - 1, memo) + Fib(n - 2, memo);
  return memo[n];
}

static void Main() {
  int n = 5;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Understand Fibonacci calculation for n=5

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

2. Step 2: Trace memoized calls

   Memo array caches results to avoid repeated calls, final result printed is Fib(5) = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence values for small n [OK]

Common Mistakes:

• Confusing Fib(5) with Fib(6)
• Ignoring memoization effect
• Assuming zero-based indexing for output

4. Identify the error in the following C# code implementing a memoized Fibonacci function:

static int Fib(int n, 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];
}

static void Main() {
  int n = 4;
  int[] memo = new int[n + 1];
  Console.WriteLine(Fib(n, memo));
}

medium

A. The memo array is not initialized with -1, so memo[n] != -1 check fails.

B. The base case should return 0 instead of n.

C. The function should return void instead of int.

D. The memo array size is too large.

Solution

1. Step 1: Check memo array initialization

   The memo array is created but not initialized to -1, so all values default to 0.

2. Step 2: Analyze memo[n] != -1 condition

   Since memo[n] starts at 0, the condition memo[n] != -1 is always true for n>0, causing incorrect memo hits.

3. Final Answer:

   The memo array is not initialized with -1, so memo[n] != -1 check fails. -> Option A

4. Quick Check:

   Uninitialized memo array causes wrong memo check [OK]

Hint: Initialize memo with sentinel values matching your check [OK]

Common Mistakes:

• Not initializing memo array properly
• Incorrect base case return values
• Wrong return type for recursive function

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. The cost grid is:

int[,] cost = {
  {1, 3, 5, 8},
  {4, 2, 1, 7},
  {4, 3, 2, 3}
};

Which approach best uses Overlapping Subproblems and Optimal Substructure to solve this efficiently?

hard

A. Calculate all paths and pick the minimum cost path at the end.

B. Use a greedy approach picking the minimum cost neighbor at each step.

C. Use recursion with memoization to store minimum cost for each cell.

D. Use a stack to store all possible paths and backtrack.

Solution

1. Step 1: Understand problem structure

   The minimum cost path problem has overlapping subproblems because many paths share subpaths, and optimal substructure because the best path to a cell depends on best paths to neighbors.

2. Step 2: Choose efficient approach

   Recursion with memoization stores results of subproblems to avoid recomputation, efficiently solving the problem.

3. Final Answer:

   Use recursion with memoization to store minimum cost for each cell. -> Option C

4. Quick Check:

   Memoized recursion fits overlapping subproblems and optimal substructure [OK]

Hint: Memoize subproblem results to avoid repeated calculations [OK]

Common Mistakes:

• Using greedy approach which may fail for this problem
• Trying all paths causing exponential time
• Using stack/backtracking without memoization