Why Greedy Works and When It Fails in DSA Python - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following code that uses a greedy approach to make change with coins [25, 10, 5, 1] for amount 30?

DSA Python

def greedy_coin_change(coins, amount):
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

coins = [25, 10, 5, 1]
change = greedy_coin_change(coins, 30)
print(change)

A [25, 5]

B [25, 1, 1, 1, 1, 1]

C [10, 10, 10]

D [5, 5, 5, 5, 5, 5]

💡 Hint

Think about how the greedy algorithm picks the largest coin first and subtracts it from the amount.

The greedy algorithm picks the largest coin less than or equal to the remaining amount. For 30, it picks 25 once, then 5 once, totaling 30.

🧠 Conceptual

intermediate

Why Greedy Fails for Certain Coin Sets

Why does the greedy coin change algorithm fail to find the minimum number of coins for the coin set [25, 10, 1] and amount 40?

A Because the greedy algorithm only works for amounts divisible by the largest coin.

B Because the greedy algorithm always picks the largest coin first, it misses the optimal combination of smaller coins.

C Because the greedy algorithm cannot handle coin sets with more than three coins.

D Because the greedy algorithm sorts coins incorrectly, causing wrong picks.

💡 Hint

Consider how greedy picks coins and if that always leads to the fewest coins.

Greedy picks 25 first, then 10, then 1 five times, totaling 7 coins, but optimal is 4 coins (10 + 10 + 10 + 10).

🔧 Debug

advanced

Identify the Error in Greedy Interval Scheduling

What error does the following code produce when trying to schedule maximum non-overlapping intervals using a greedy approach?

DSA Python

intervals = [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]

intervals.sort(key=lambda x: x[0])

result = []
end = 0
for interval in intervals:
    if interval[0] >= end:
        result.append(interval)
        end = interval[1]

print(result)

A The code produces incorrect scheduling because intervals are sorted by start time, not finish time.

B The code raises a TypeError due to incorrect tuple unpacking.

C The code produces an empty list because end is initialized to 0.

D The code raises an IndexError due to accessing out-of-range elements.

💡 Hint

Think about which sorting key is needed for greedy interval scheduling.

Greedy interval scheduling requires sorting intervals by their finish time, not start time. Sorting by start time leads to suboptimal results.

❓ Predict Output

advanced

Output of Fractional Knapsack Greedy Algorithm

What is the output of the following code that uses a greedy approach to solve the fractional knapsack problem?

DSA Python

def fractional_knapsack(values, weights, capacity):
    ratio = [(v/w, v, w) for v, w in zip(values, weights)]
    ratio.sort(key=lambda x: x[0], reverse=True)
    total_value = 0
    for r, v, w in ratio:
        if capacity >= w:
            capacity -= w
            total_value += v
        else:
            total_value += r * capacity
            break
    return round(total_value, 2)

values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(fractional_knapsack(values, weights, capacity))

A 180.0

B 220.0

C 240.0

D 200.0

💡 Hint

Calculate value/weight ratio and pick items greedily until capacity is full.

The ratios are 6.0, 5.0, and 4.0. Pick 10 weight of first item (60 value), then 20 weight of second (100 value), then 20 weight fraction of third (4.0 * 20 = 80). Total = 60 + 100 + 80 = 240.

🧠 Conceptual

expert

When Does Greedy Algorithm Guarantee Optimal Solution?

Which condition below guarantees that a greedy algorithm will always produce an optimal solution?

A The problem can be solved by brute force in polynomial time.

B The problem has overlapping subproblems and uses dynamic programming.

C The problem has a single solution with no alternatives.

D The problem exhibits the greedy-choice property and optimal substructure.

💡 Hint

Think about the properties that allow greedy to work correctly.

Greedy algorithms work optimally only if the problem has the greedy-choice property (local optimal choices lead to global optimum) and optimal substructure (optimal solution contains optimal subsolutions).

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it sorts the input data before processing

B. Because it tries all possible solutions exhaustively

C. Because it uses recursion to explore all paths

D. Because making the best local choice leads to a globally optimal solution

Solution

1. Step 1: Understand greedy algorithm principle

   A greedy algorithm makes the best choice at each step without reconsidering previous choices.

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices add up to the best overall solution.

3. Final Answer:

   Because making the best local choice leads to a globally optimal solution -> Option D

4. Quick Check:

   Greedy = best local choice leads to global optimum [OK]

Hint: Greedy picks best now, works if global best follows [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting always means greedy

2. Which of the following is the correct syntax to pick the next item greedily from a sorted list items in Python?

easy

A. next_item = items.pop(0)

B. next_item = items[0]

C. next_item = items.pop()

D. next_item = items.remove(0)

Solution

1. Step 1: Understand list methods for greedy selection

   To pick and remove the first item, pop(0) removes and returns it.

2. Step 2: Check other options

   items[0] only accesses without removing; pop() removes last; remove(0) removes first occurrence of value 0, not index.

3. Final Answer:

   next_item = items.pop(0) -> Option A

4. Quick Check:

   pop(0) removes first item [OK]

Hint: pop(0) removes and returns first item [OK]

Common Mistakes:

• Using items[0] without removing
• Using pop() removes last item
• Confusing remove() with pop()

3. Consider the following code that tries to select intervals greedily by earliest finish time:

intervals = [(1,4), (2,3), (3,5), (7,8)]
intervals.sort(key=lambda x: x[1])
selected = []
end = 0
for start, finish in intervals:
    if start >= end:
        selected.append((start, finish))
        end = finish
print(selected)

What is the output?

medium

A. [(2, 3), (7, 8)]

B. [(1, 4), (7, 8)]

C. [(2, 3), (3, 5), (7, 8)]

D. [(1, 4), (3, 5), (7, 8)]

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: (2,3), (1,4), (3,5), (7,8)

2. Step 2: Select intervals greedily

   Start with end=0. (2,3) start=2 >=0, select it, end=3. Next (1,4) start=1<3 skip. Next (3,5) start=3>=3 select, end=5. Next (7,8) start=7>=5 select, end=8.

3. Step 3: Final selected intervals

   [(2,3), (3,5), (7,8)]

4. Final Answer:

   [(2, 3), (3, 5), (7, 8)] -> Option C

5. Quick Check:

   Greedy interval selection by finish time = [(2,3),(3,5),(7,8)] [OK]

Hint: Sort by finish time, pick intervals starting after last end [OK]

Common Mistakes:

• Not sorting by finish time
• Selecting overlapping intervals
• Updating end incorrectly

4. The following code tries to solve the coin change problem greedily but has a bug:

coins = [25, 10, 5, 1]
amount = 30
result = []
for coin in coins:
    while amount >= coin:
        result.append(coin)
        amount -= coin
print(result)

What is the bug in this greedy approach?

medium

A. It does not sort coins before using them

B. It fails for some coin sets where greedy is not optimal

C. It uses while instead of if

D. It does not handle zero amount correctly

Solution

1. Step 1: Understand greedy coin change approach

   The code picks largest coin repeatedly until amount is zero.

2. Step 2: Identify when greedy fails

   Greedy works for US coins but fails for some sets (e.g., coins=[10,6,1], amount=12 greedy picks 10+1+1=3 coins but optimal is 6+6=2 coins).

3. Final Answer:

   It fails for some coin sets where greedy is not optimal -> Option B

4. Quick Check:

   Greedy coin change fails on some coin sets [OK]

Hint: Greedy coin change fails if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Thinking sorting is missing
• Confusing while and if usage

5. You want to select the minimum number of intervals to cover a timeline from 0 to 10. Intervals are: [(0,3), (2,6), (5,10), (7,10), (1,4)]. Which greedy strategy will fail to find the minimum set and why? Options: A) Always pick the interval with earliest start time B) Always pick the interval with shortest length C) Always pick the interval with earliest finish time D) Always pick the interval covering the largest uncovered part Choose the failing strategy and explain why.

hard

A. Always picking shortest length fails because it may need many intervals to cover timeline

B. Always picking earliest start fails because it may pick small intervals leaving gaps

C. Always picking earliest finish time works correctly here

D. Always picking largest uncovered part always finds minimum intervals

Solution

1. Step 1: Analyze shortest length strategy

   Picking shortest intervals first may cover small parts, requiring many intervals to cover entire timeline.

2. Step 2: Compare with other strategies

   Earliest finish time is classic greedy that works for interval covering. Largest uncovered part is a complex greedy that can work. Earliest start can fail but less obviously here.

3. Final Answer:

   Always picking shortest length fails because it may need many intervals to cover timeline -> Option A

4. Quick Check:

   Shortest length greedy fails for minimum interval cover [OK]

Hint: Shortest intervals first often leads to many intervals needed [OK]

Common Mistakes:

• Assuming earliest start always works
• Thinking largest uncovered part is always greedy
• Confusing shortest length with earliest finish