DP vs Recursion vs Greedy Choosing the Right Tool in DSA Java - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci with Memoization

What is the output of the following Java code that uses recursion with memoization to calculate Fibonacci numbers?

DSA Java

import java.util.*;
public class FibMemo {
    static Map<Integer, Integer> memo = new HashMap<>();
    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }
    public static void main(String[] args) {
        System.out.println(fib(6));
    }
}

A 8

B 13

C 21

D 5

💡 Hint

Remember Fibonacci sequence starts with 0,1 and each next number is sum of previous two.

The Fibonacci sequence is 0,1,1,2,3,5,8,... fib(6) is the 6th Fibonacci number starting from 0 index, which is 8.

🧠 Conceptual

intermediate

Choosing Greedy vs DP Approach

Which of the following problem characteristics best indicates that a greedy algorithm is the right choice over dynamic programming?

A The problem has overlapping subproblems and optimal substructure.

B The problem has no optimal substructure and requires backtracking.

C The problem has optimal substructure and the greedy choice property.

D The problem requires exploring all possible combinations to find the best solution.

💡 Hint

Greedy algorithms work when making local optimal choices leads to a global optimum.

Greedy algorithms work well when the problem has both optimal substructure and the greedy choice property, meaning local choices lead to global optimum.

🔧 Debug

advanced

Why Does This Recursive Solution Cause Stack Overflow?

Consider this recursive Java method to calculate factorial: public static int factorial(int n) { if (n == 0) return 1; return n * factorial(n - 1); } What is the main reason this code might cause a stack overflow error for large n?

A It uses deep recursion which exhausts the call stack for large n.

B It lacks a base case to stop recursion.

C It uses an incorrect multiplication operator.

D It uses recursion without memoization causing repeated calculations.

💡 Hint

Think about how recursion uses the call stack and what happens with large inputs.

Deep recursion calls add stack frames; for large n, this can exceed stack size causing overflow.

❓ Predict Output

advanced

Output of Greedy Interval Scheduling

What is the output of this Java code that selects the maximum number of non-overlapping intervals using a greedy approach?

DSA Java

import java.util.*;
public class IntervalScheduling {
    static class Interval implements Comparable<Interval> {
        int start, end;
        Interval(int s, int e) { start = s; end = e; }
        public int compareTo(Interval other) { return this.end - other.end; }
    }
    public static int maxIntervals(Interval[] intervals) {
        Arrays.sort(intervals);
        int count = 0, lastEnd = Integer.MIN_VALUE;
        for (Interval i : intervals) {
            if (i.start >= lastEnd) {
                count++;
                lastEnd = i.end;
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Interval[] intervals = {
            new Interval(1, 3),
            new Interval(2, 5),
            new Interval(4, 7),
            new Interval(6, 9),
            new Interval(8, 10)
        };
        System.out.println(maxIntervals(intervals));
    }
}

A 5

B 2

C 4

D 3

💡 Hint

Greedy interval scheduling picks intervals by earliest finish time without overlap.

The selected intervals are (1,3), (4,7), (8,10). (2,5) overlaps with (1,3), (6,9) overlaps with (4,7) so not chosen. Maximum count is 3.

🧠 Conceptual

expert

When to Prefer Dynamic Programming Over Greedy

Which scenario best explains when dynamic programming is necessary instead of a greedy approach?

A When the problem can be solved by sorting and selecting elements greedily.

B When local optimal choices do not guarantee a global optimum solution.

C When the problem has optimal substructure but no overlapping subproblems.

D When the problem size is small and recursion is simple.

💡 Hint

Think about when greedy fails to find the best solution and you need to consider all possibilities.

Dynamic programming is needed when greedy choices can lead to suboptimal solutions because local choices don't guarantee global optimum.

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