Greedy vs DP How to Know Which to Apply in DSA C# - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the problem has optimal substructure property.

DSA C#

bool HasOptimalSubstructure(int[] arr) {
    // Optimal substructure means the problem can be broken into [1] subproblems
    return arr.Length > 1;
}

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

Adependent

Bindependent

Coverlapping

Dirrelevant

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing overlapping subproblems with optimal substructure.

Thinking subproblems must overlap for optimal substructure.

Optimal substructure means the problem can be divided into smaller independent subproblems whose solutions combine to solve the original problem.

2fill in blank

medium

Complete the code to identify if subproblems overlap for DP application.

DSA C#

bool HasOverlappingSubproblems(int n) {
    // Overlapping subproblems means the same subproblem is solved [1] times
    return n > 1;
}

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

Arandomly

Bonce

Cnever

Dmultiple

Attempts:

3 left

💡 Hint

Common Mistakes

Assuming subproblems are solved only once in DP.

Confusing overlapping with independent subproblems.

Overlapping subproblems means the same smaller problem appears multiple times, which is why DP stores results to avoid repeated work.

3fill in blank

hard

Fix the error in the greedy choice property check code.

DSA C#

bool HasGreedyChoiceProperty(int[] arr) {
    // Greedy choice means a local optimal choice leads to global optimal
    for (int i = 0; i < arr.Length - 1; i++) {
        if (arr[i] [1] arr[i + 1]) {
            return false;
        }
    }
    return true;
}

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

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' causes wrong greedy checks.

Using equality '==' does not verify greedy property.

The greedy choice property often requires that choosing the smaller or equal element locally leads to a global optimum, so we check if arr[i] < arr[i+1].

4fill in blank

hard

Fill both blanks to complete the DP memoization dictionary initialization and lookup.

DSA C#

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

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

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

An

Bn-1

Cn+1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using different keys for ContainsKey and dictionary access.

Using incorrect keys like n-1 or n+1.

We check if the memo dictionary contains the key 'n' and return memo[n] if it exists to avoid repeated calculations.

5fill in blank

hard

Fill all three blanks to complete the greedy algorithm for activity selection.

DSA C#

List<(int start, int end)> SelectActivities(List<(int start, int end)> activities) {
    activities.Sort((a, b) => a.end [1] b.end);
    List<(int start, int end)> selected = new List<(int, int)>();
    int lastEnd = 0;
    foreach (var activity in activities) {
        if (activity.start [2] lastEnd) {
            selected.Add(activity);
            lastEnd = activity.end;
        }
    }
    return selected;
}

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

A-

B<=

C>=

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting with incorrect comparator like addition.

Using wrong comparison operator in if condition.

We sort activities by their end time using subtraction (a.end - b.end). Then we select an activity if its start time is greater or equal to the last selected activity's end time.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem has the greedy choice property and optimal substructure

B. When the problem requires checking all possible solutions

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

D. When the problem is about sorting large datasets

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Check optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option A

4. Quick Check:

   Greedy choice + optimal substructure = Greedy algorithm [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Thinking sorting problems always need DP

2. Which of the following C# code snippets correctly initializes a DP array for a problem with 5 states?

easy

A. int dp = new int[5];

B. int[] dp = new int[5];

C. int[] dp = int[5];

D. int dp[] = new int(5);

Solution

1. Step 1: Check correct array declaration syntax in C#

   Arrays are declared with type[], variable = new type[size]; so int[] dp = new int[5]; is correct.

2. Step 2: Identify errors in other options

   int dp = new int[5]; misses [] for array type, C uses wrong syntax, D uses parentheses instead of brackets.

3. Final Answer:

   int[] dp = new int[5]; -> Option B

4. Quick Check:

   C# array syntax = type[] var = new type[size]; [OK]

Hint: Remember C# arrays use [] and new keyword [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using parentheses instead of brackets for arrays
• Confusing array initialization syntax

3. Consider the following C# code for a problem that can be solved by greedy or DP. What is the output?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Trace the greedy coin counting

   Start with coins = {1,3,4}, amount = 6. - i=2 (coin=4): count += 6/4 = 1, amount = 6%4 = 2 - i=1 (coin=3): count += 2/3 = 0, amount = 2%3 = 2 - i=0 (coin=1): count += 2/1 = 2, amount = 2%1 = 0 Total count = 1 + 0 + 2 = 3.

2. Step 2: Confirm output

   The Console.WriteLine prints 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Greedy coin count = 3 [OK]

Hint: Trace loops step-by-step to find output [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Miscomputing division or modulo
• Ignoring order of coins in loop

4. The following code tries to solve the coin change problem using DP but has a bug. What is the error?

int[] coins = {1, 3, 4};
int amount = 6;
int[] dp = new int[amount + 1];
dp[0] = 0;
for (int i = 1; i <= amount; i++)
{
    dp[i] = int.MaxValue;
    foreach (int coin in coins)
    {
        if (i - coin >= 0)
        {
            dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
        }
    }
}
Console.WriteLine(dp[amount]);

medium

A. int.MaxValue causes overflow when adding 1

B. dp array is not initialized properly for base case

C. Coins array is not sorted

D. Loop indices are incorrect

Solution

1. Step 1: Understand dp initialization and update

   dp[i] is set to int.MaxValue initially. When dp[i - coin] is int.MaxValue, adding 1 causes overflow.

2. Step 2: Identify overflow problem

   Adding 1 to int.MaxValue wraps around to negative, causing wrong minimum calculation.

3. Final Answer:

   int.MaxValue causes overflow when adding 1 -> Option A

4. Quick Check:

   Adding 1 to int.MaxValue overflows [OK]

Hint: Avoid adding to int.MaxValue directly [OK]

Common Mistakes:

• Ignoring overflow from int.MaxValue + 1
• Assuming coin order matters in DP
• Not initializing dp[0] correctly

5. You want to find the minimum number of coins to make amount 6 using coins {1, 3, 4}. Which approach is better and why?

// Greedy approach
int count = 0;
int amount = 6;
int[] coins = {4, 3, 1};
for (int i = 0; i < coins.Length; i++)
{
    count += amount / coins[i];
    amount %= coins[i];
}
Console.WriteLine(count);

Choose the best answer.

hard

A. Greedy works because coins are sorted descending

B. Neither approach works for this problem

C. Both greedy and DP give same result here

D. Greedy fails; DP is better due to overlapping subproblems

Solution

1. Step 1: Test greedy approach output

   Greedy picks 4 once (6/4=1), remainder 2, picks 3 (2/3=0), remainder 2, picks 1 (2/1=2), total coins = 3.

2. Step 2: Check if greedy is optimal

   DP finds minimum coins: 2 (4 + 2 coins). Greedy gives 3, suboptimal.

3. Step 3: Consider general case

   Greedy can fail for some amounts; DP handles overlapping subproblems and finds true minimum.

4. Final Answer:

   Greedy fails; DP is better due to overlapping subproblems -> Option D

5. Quick Check:

   Overlapping subproblems need DP, greedy may fail [OK]

Hint: Use DP if greedy might miss optimal solution [OK]

Common Mistakes:

• Assuming greedy always works if coins sorted
• Ignoring overlapping subproblems in coin change
• Thinking greedy and DP always match