Overlapping Subproblems and Optimal Substructure in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following JavaScript code that calculates Fibonacci numbers using memoization?

DSA Javascript

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

A 13

B 10

C 8

D 5

💡 Hint

Remember that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5...

The Fibonacci sequence for n=5 is 5. The function uses memoization to avoid repeated calculations.

🧠 Conceptual

intermediate

Identifying Overlapping Subproblems

Which of the following problems best demonstrates the concept of overlapping subproblems?

A Finding the shortest path in a graph using Dijkstra's algorithm

B Computing Fibonacci numbers using recursion without memoization

C Sorting an array using quicksort

D Calculating factorial of a number using recursion

💡 Hint

Overlapping subproblems means the same smaller problems are solved multiple times.

Computing Fibonacci numbers recursively without memoization solves the same subproblems repeatedly, showing overlapping subproblems.

❓ Predict Output

advanced

Output of Coin Change Problem with Memoization

What is the output of the following JavaScript code that finds the minimum number of coins needed to make change?

DSA Javascript

function minCoins(coins, amount, memo = {}) {
  if (amount === 0) return 0;
  if (amount < 0) return Infinity;
  if (memo[amount]) return memo[amount];
  let min = Infinity;
  for (let coin of coins) {
    const res = minCoins(coins, amount - coin, memo);
    if (res !== Infinity && res + 1 < min) {
      min = res + 1;
    }
  }
  memo[amount] = min;
  return min;
}
console.log(minCoins([1, 3, 4], 6));

A 4

B 3

C 2

D Infinity

💡 Hint

Try to find the fewest coins that sum to 6 using coins 1, 3, and 4.

The minimum coins to make 6 are 2 (e.g., 3 + 3).

🔧 Debug

advanced

Identify the Error in Memoized Fibonacci

What error does the following code produce when run?

DSA Javascript

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2);
  return memo[n];
}
console.log(fib(5));

A 5

B TypeError: Cannot read property 'n' of undefined

C ReferenceError: memo is not defined

D NaN

💡 Hint

Check if all recursive calls pass the memo object.

No runtime error occurs and the code outputs 5. However, the fib(n - 2) call misses the memo argument, so it uses a new memo object instead of the shared one.

🧠 Conceptual

expert

Optimal Substructure in Dynamic Programming

Which statement best describes the property of optimal substructure in dynamic programming?

A A problem exhibits optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.

B Optimal substructure means the problem can be solved without breaking it into smaller subproblems.

C Optimal substructure requires that subproblems do not overlap.

D Optimal substructure means the problem has only one unique solution.

💡 Hint

Think about how solutions to smaller parts help build the full solution.

Optimal substructure means the best solution to a problem can be made from best solutions of smaller parts.

Practice

1. Which of the following best describes the overlapping subproblems property in dynamic programming?

easy

A. The problem can be broken down into smaller subproblems that are solved multiple times.

B. The problem has a unique solution without repeating any subproblems.

C. The problem requires sorting before solving.

D. The problem can only be solved using recursion without memoization.

Solution

1. Step 1: Understand overlapping subproblems

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

2. Step 2: Match with options

   The problem can be broken down into smaller subproblems that are solved multiple times. correctly states that subproblems repeat and can be reused to save time.

3. Final Answer:

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

4. Quick Check:

   Overlapping subproblems = repeated smaller problems [OK]

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

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Thinking sorting is required for all DP problems
• Assuming recursion alone solves overlapping subproblems

2. Which of the following JavaScript function definitions correctly implements memoization for a Fibonacci function?

easy

A. function fib(n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

B. const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; }

C. function fib(n) { let result = 0; for(let i=0; i

D. function fib(n) { return n * fib(n-1); }

Solution

1. Step 1: Identify memoization pattern

   Memoization stores results in a cache object to avoid repeated calculations.

2. Step 2: Check each option

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } uses an object 'memo' to store and reuse Fibonacci results correctly.

3. Final Answer:

   const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } -> Option B

4. Quick Check:

   Memoization uses cache object = const memo = {}; function fib(n) { if (n in memo) return memo[n]; if (n <= 1) return n; memo[n] = fib(n-1) + fib(n-2); return memo[n]; } [OK]

Hint: Look for cache object usage to store computed results [OK]

Common Mistakes:

• Not using a cache to store results
• Incorrect base case handling
• Using loops instead of recursion for memoization

3. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 3

B. 8

C. 5

D. Undefined

Solution

1. Step 1: Trace fib(5) calls with memo

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc.

2. Step 2: Calculate Fibonacci values

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5,8... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Miscounting base cases

4. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(0));

medium

A. 0

B. 1

C. undefined

D. Infinite recursion

Solution

1. Step 1: Trace fib(0)

   fib(0): n = 0 <= 1, so return 0 immediately. Memo check and recursion not reached.

2. Step 2: Output

   console.log(0) prints 0.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   fib(0) = 0 [OK]

Hint: Base case n <= 1 executes before memo check [OK]

Common Mistakes:

• Thinking memo[n] check runs for base cases n <= 1
• Believing falsy memo[0] causes undefined return
• Forgetting base case includes n = 0

5. You want to find the minimum cost path in a grid from top-left to bottom-right, moving only right or down. Which property allows using dynamic programming to solve this efficiently?

hard

A. Greedy choice: Always pick the cell with the smallest immediate cost.

B. Overlapping subproblems: Each cell's cost is unique and never reused.

C. Divide and conquer: Solve each half of the grid independently.

D. Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells.

Solution

1. Step 1: Understand minimum cost path problem

   The cost to reach a cell depends on the best path to its neighbors (top or left).

2. Step 2: Identify optimal substructure

   The problem can be solved by combining optimal solutions of smaller subproblems (cells).

3. Final Answer:

   Optimal substructure: The minimum cost path to a cell depends on minimum cost paths to adjacent cells. -> Option D

4. Quick Check:

   Optimal substructure enables DP for grid path [OK]

Hint: Look for problems where solutions build from smaller optimal solutions [OK]

Common Mistakes:

• Confusing overlapping subproblems with unique subproblems
• Assuming greedy always works for grid path
• Ignoring dependency between subproblems