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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following Go code that uses a greedy approach to make change for 30 cents with coin denominations 25, 10, and 1?

DSA Go

package main
import "fmt"
func main() {
    coins := []int{25, 10, 1}
    amount := 30
    result := []int{}
    for _, coin := range coins {
        for amount >= coin {
            amount -= coin
            result = append(result, coin)
        }
    }
    fmt.Println(result)
}

A [25 5]

B [25 10]

C [10 10 10]

D [25 1 1 1 1 1]

💡 Hint

Think about how the greedy algorithm picks the largest coin first and then moves to smaller coins.

The greedy algorithm picks the largest coin less than or equal to the remaining amount. For 30 cents, it picks 25 once, then uses five 1-cent coins to make the remaining 5 cents.

🧠 Conceptual

intermediate

When Does Greedy Fail in Interval Scheduling?

In interval scheduling, which greedy strategy can fail to find the maximum number of non-overlapping intervals?

A Always pick the interval with the shortest duration

B Always pick the interval with the earliest finish time

C Always pick the interval that starts earliest

D Always pick the interval with the latest start time

💡 Hint

Consider which strategy might select intervals that block many others.

Picking the shortest interval first can block many other intervals, leading to fewer total intervals selected. The correct greedy strategy is to pick intervals by earliest finish time.

🔧 Debug

advanced

Identify the Error in Greedy Activity Selector Code

What error does the following Go code produce when trying to select maximum activities using a greedy approach based on earliest finish time?

DSA Go

package main
import "fmt"
func main() {
    start := []int{1, 3, 0, 5, 8, 5}
    finish := []int{2, 4, 6, 7, 9, 9}
    n := len(start)
    selected := []int{0}
    last := 0
    for i := 1; i < n; i++ {
        if start[i] >= finish[last] {
            selected = append(selected, i)
            last = i
        }
    }
    fmt.Println(selected)
}

A Output: [0 2 4]

B Output: [0 1 3 4]

C Index out of range runtime error

D Output: [0 1 2 3 4 5]

💡 Hint

Check if the intervals are sorted by finish time before selection.

The code assumes intervals are sorted by finish time, but they are not. However, the given input is already sorted by finish time, so the code runs correctly and outputs [0 1 3 4].

🚀 Application

advanced

Greedy Algorithm Failure in Fractional Knapsack Variant

Given items with weights and values, which greedy approach fails to find the optimal solution in the 0/1 knapsack problem?

A Pick items with highest value first

B Pick items with lowest weight first

C Pick items with highest value-to-weight ratio first

D Pick items randomly

💡 Hint

Greedy by value-to-weight ratio works for fractional knapsack but not always for 0/1 knapsack.

The greedy approach picking items by highest value-to-weight ratio works for fractional knapsack but can fail for 0/1 knapsack because it cannot take fractions and may miss better combinations.

🧠 Conceptual

expert

Why Greedy Algorithms Guarantee Optimality in Matroid Problems

Which property of matroids ensures that a greedy algorithm always finds the optimal solution?

A The hereditary property and the exchange property

B The presence of cycles in the structure

C The ability to sort elements by weight

D The existence of a unique maximum spanning tree

💡 Hint

Matroids have special properties that allow greedy choices to be extended to optimal solutions.

Matroids have the hereditary property (subsets of independent sets are independent) and the exchange property (elements can be exchanged to maintain independence), which guarantee greedy algorithms find optimal solutions.

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 and picks the best one

C. Because it makes the best choice at each step hoping for a global optimum

D. Because it uses recursion to explore all paths

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm makes the best local choice at each step, aiming for a global best solution.

2. Step 2: Differentiate from exhaustive search

   Unlike trying all solutions or recursion, greedy does not explore all paths but relies on local optimality.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option C

4. Quick Check:

   Greedy choice property = Because it makes the best choice at each step hoping for a global optimum [OK]

Hint: Greedy picks best local choice, not all possibilities [OK]

Common Mistakes:

• Confusing greedy with exhaustive search
• Thinking greedy always tries all solutions
• Assuming sorting alone makes greedy correct

2. Which of the following Go code snippets correctly implements a greedy step to pick the largest number from a slice?

easy

A. max := nums[0]
for _, v := range nums {
if v > max {
max = v
}
}

B. max := 0
for i := 1; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

C. max := nums[0]
for i := 0; i < len(nums); i++ {
if nums[i] < max {
max = nums[i]
}
}

D. max := nums[0]
for _, v := range nums {
if v < max {
max = v
}
}

Solution

1. Step 1: Identify correct max initialization and comparison

   Initialize max with first element and update if current value is greater.

2. Step 2: Check loop and condition correctness

   max := nums[0] for _, v := range nums { if v > max { max = v } } uses correct range loop and updates max when v > max.

3. Final Answer:

   Option A correctly finds the largest number -> Option A

4. Quick Check:

   Correct max update condition = max := nums[0] for _, v := range nums { if v > max { max = v } } [OK]

Hint: Update max only if current value is greater [OK]

Common Mistakes:

• Using '<' instead of '>' to find max
• Initializing max to zero instead of first element
• Comparing incorrectly inside loop

3. What will be the output of the following Go code that tries to select intervals greedily by earliest finish time?

package main
import "fmt"
func main() {
  intervals := [][]int{{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}}
  selected := [][]int{}
  lastEnd := 0
  for _, interval := range intervals {
    if interval[0] >= lastEnd {
      selected = append(selected, interval)
      lastEnd = interval[1]
    }
  }
  fmt.Println(selected)
}

medium

A. [[1 4] [5 7] [8 9]]

B. [[1 4] [3 5] [5 7] [8 9]]

C. [[0 6] [8 9]]

D. [[1 4] [5 9]]

Solution

1. Step 1: Understand greedy selection by earliest finish time

   Intervals are checked in given order; select if start >= last selected end.

2. Step 2: Trace selection step-by-step

   Selected intervals: [1,4] (lastEnd=4), skip [3,5], skip [0,6], select [5,7] (lastEnd=7), select [8,9].

3. Final Answer:

   [[1 4] [5 7] [8 9]] -> Option A

4. Quick Check:

   Greedy interval selection = [[1 4] [5 7] [8 9]] [OK]

Hint: Pick intervals starting after last end time [OK]

Common Mistakes:

• Not updating lastEnd correctly
• Selecting overlapping intervals
• Assuming input is sorted by finish time

4. The following Go code tries to solve the coin change problem greedily but sometimes fails. What is the bug?

package main
import "fmt"
func main() {
  coins := []int{25, 10, 5, 1}
  amount := 30
  count := 0
  for _, coin := range coins {
    count += amount / coin
    amount = amount % coin
  }
  fmt.Println(count)
}

medium

A. The coins slice is not sorted in ascending order

B. The greedy approach fails for some coin sets, but code logic is correct

C. The code does not update amount correctly inside the loop

D. The count variable should be reset inside the loop

Solution

1. Step 1: Analyze greedy coin change logic

   The code picks largest coins first, counting how many fit, updating amount correctly.

2. Step 2: Understand greedy failure cases

   Greedy works for US coins but fails for some coin sets; code logic is correct but approach can fail.

3. Final Answer:

   The greedy approach fails for some coin sets, but code logic is correct -> Option B

4. Quick Check:

   Greedy correctness depends on coin set = The greedy approach fails for some coin sets, but code logic is correct [OK]

Hint: Greedy coin change fails on non-canonical coin sets [OK]

Common Mistakes:

• Thinking code has syntax or logic error
• Assuming coin order must be ascending
• Resetting count inside loop incorrectly

5. You want to schedule the maximum number of non-overlapping meetings from a list of start and end times. Which greedy strategy guarantees the optimal solution?

hard

A. Always pick the meeting with the latest start time

B. Always pick the meeting with the shortest duration

C. Always pick the meeting with the earliest start time

D. Always pick the meeting with the earliest finish time

Solution

1. Step 1: Recall interval scheduling greedy strategy

   The proven greedy method is to pick meetings finishing earliest to maximize remaining time.

2. Step 2: Compare other strategies

   Picking earliest start or shortest duration can cause overlaps and miss optimal count.

3. Final Answer:

   Always pick the meeting with the earliest finish time -> Option D

4. Quick Check:

   Earliest finish time strategy = Always pick the meeting with the earliest finish time [OK]

Hint: Pick meetings finishing earliest to maximize schedule [OK]

Common Mistakes:

• Choosing earliest start time instead of finish time
• Picking shortest duration meetings incorrectly
• Assuming latest start time works best