DP vs Recursion vs Greedy Choosing the Right Tool in DSA Java - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to implement a simple recursive factorial function.

DSA Java

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial([1]);
}

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

An - 1

Bn + 1

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Returning 1 always ignores recursion.

The factorial function calls itself with n - 1 to reduce the problem size until it reaches 0.

2fill in blank

medium

Complete the code to implement memoization for Fibonacci numbers.

DSA Java

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

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

A1

Bn - 2

Cn + 1

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n - 2 twice misses fib(n-1).

Using n + 1 causes index errors.

The Fibonacci number at n is the sum of fib(n-1) and fib(n-2). Memoization stores results to avoid repeated work.

3fill in blank

hard

Fix the error in the greedy coin change algorithm to pick the largest coin first.

DSA Java

int coinChange(int amount, int[] coins) {
    int count = 0;
    for (int i = 0; i < coins.length; i++) {
        while (amount >= coins[[1]]) {
            amount -= coins[[1]];
            count++;
        }
    }
    return count;
}

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

Ai

B0

Ccoins.length - 1 - i

Dcoins.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using i accesses coins from smallest to largest.

Using 0 or coins.length causes index errors.

To pick the largest coin first, iterate coins in reverse order using coins.length - 1 - i.

4fill in blank

hard

Fill both blanks to create a dynamic programming solution for the 0/1 knapsack problem.

DSA Java

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i - 1] <= w) {
            dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][[1]] + values[i - 1]);
        } else {
            dp[i][w] = dp[i - 1][[2]];
        }
    }
}

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

Aw - weights[i - 1]

Bw + weights[i - 1]

Cw

Dw - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Adding weights instead of subtracting.

Using wrong indices causing errors.

The dp table stores max value for weight w. When including item i, subtract its weight from w. Otherwise, keep previous value at w.

5fill in blank

hard

Fill all three blanks to implement a bottom-up DP solution for the Longest Common Subsequence (LCS).

DSA Java

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            dp[i][j] = dp[[1]][[2]] + 1;
        } else {
            dp[i][j] = Math.max(dp[[3]][j], dp[i][j - 1]);
        }
    }
}

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

Ai - 1

Bj - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices causing off-by-one errors.

Mixing up i and j in dp access.

When characters match, add 1 to dp[i-1][j-1]. Otherwise, take max of dp[i-1][j] and dp[i][j-1].

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion

D. Brute Force

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems means the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller parts.

2. Step 2: Match approach to properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization
• Confusing optimal substructure with greedy choice property

2. Which of the following Java method signatures correctly represents a recursive function to compute factorial?

easy

A. public static int factorial(int n) { if (n == 1) return 0; else return n + factorial(n - 1); }

B. public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); }

C. public static int factorial(int n) { for (int i = 1; i <= n; i++) return i; }

D. public static int factorial(int n) { while (n > 0) n = n - 1; return n; }

Solution

1. Step 1: Check base case correctness

   Factorial base case is 0! = 1, so if (n == 0) return 1 is correct.

2. Step 2: Check recursive call and calculation

   Factorial(n) = n * factorial(n-1) is correct recursive formula.

3. Final Answer:

   public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive multiplication = public static int factorial(int n) { if (n == 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Factorial recursion multiplies n by factorial(n-1) with base n=0 [OK]

Common Mistakes:

• Wrong base case (e.g., returning 0 instead of 1)
• Using loops instead of recursion
• Returning addition instead of multiplication

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

public class Test {
  public static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 3

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2). fib(3) = fib(2) + fib(1), fib(2) = fib(1) + fib(0).

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1, so fib(2)=1+0=1, fib(3)=1+1=2, fib(4)=2+1=3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Fibonacci(4) = 3 by adding previous two Fibonacci numbers [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Adding wrong recursive results
• Assuming fib(4) = 5 (fibonacci(5))

4. Identify the error in this greedy algorithm code snippet for coin change problem:

public static int minCoins(int[] coins, int amount) {
  int count = 0;
  for (int coin : coins) {
    while (amount >= coin) {
      amount -= coin;
      count++;
    }
  }
  return count;
}

medium

A. Missing base case for amount = 0

B. Should use recursion instead of loops

C. Coins array must be sorted in descending order

D. Count variable should be reset inside the loop

Solution

1. Step 1: Understand greedy coin change logic

   Greedy picks largest coin first to minimize count. Coins must be sorted descending for this to work.

2. Step 2: Check code for sorting

   Code does not sort coins, so if coins are unsorted, greedy picks smaller coins first, leading to wrong answer.

3. Final Answer:

   Coins array must be sorted in descending order -> Option C

4. Quick Check:

   Greedy coin change needs descending sorted coins [OK]

Hint: Sort coins descending for greedy coin change to work correctly [OK]

Common Mistakes:

• Not sorting coins before greedy selection
• Using recursion unnecessarily
• Resetting count inside loop causing wrong count

5. You want to find the minimum number of jumps to reach the end of an array where each element represents max jump length at that position. Which approach is best and why?

int[] arr = {2,3,1,1,4};

hard

A. Use Dynamic Programming to store minimum jumps for each index

B. Use simple recursion to try all jump combinations

C. Use Brute Force to check every path

D. Use Greedy approach to jump to the farthest reachable index

Solution

1. Step 1: Analyze problem nature

   Minimum jumps problem can be solved efficiently by greedy because at each step, jumping to the farthest reachable index reduces total jumps.

2. Step 2: Compare approaches

   Recursion or DP works but are slower. Greedy gives optimal solution in linear time for this problem.

3. Final Answer:

   Use Greedy approach to jump to the farthest reachable index -> Option D

4. Quick Check:

   Minimum jumps = Greedy farthest jump [OK]

Hint: Jump farthest reachable index greedily for minimum jumps [OK]

Common Mistakes:

• Using recursion causing timeouts
• Overcomplicating with DP when greedy suffices
• Ignoring problem constraints for greedy validity