Challenge - 5 Problems
Greedy Mastery
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Greedy Coin Change Algorithm
What is the output of the following Rust code that uses a greedy approach to make change with coins [25, 10, 5, 1] for amount 63?
DSA Rust
fn greedy_coin_change(mut amount: i32, coins: &[i32]) -> Vec<i32> {
let mut result = Vec::new();
for &coin in coins {
while amount >= coin {
amount -= coin;
result.push(coin);
}
}
result
}
fn main() {
let coins = [25, 10, 5, 1];
let change = greedy_coin_change(63, &coins);
println!("{:?}", change);
}Attempts:
2 left
💡 Hint
Think about how the greedy algorithm picks the largest coin first until it cannot anymore.
✗ Incorrect
The greedy algorithm picks the largest coin less than or equal to the remaining amount repeatedly. For 63, it picks two 25-cent coins (50), then one 10-cent coin (60), then three 1-cent coins (63).
🧠 Conceptual
intermediate2:00remaining
When Does Greedy Fail in Coin Change?
Given coin denominations [10, 6, 1], what is the minimum number of coins needed to make 12? Does the greedy algorithm find the minimum?
Attempts:
2 left
💡 Hint
Try running the greedy algorithm step by step for amount 12.
✗ Incorrect
Greedy picks 10 first, then two 1s, total 3 coins. But the minimum is two coins (6 + 6). So greedy fails here.
🔧 Debug
advanced2:00remaining
Identify the Bug in Greedy Interval Scheduling
What error does the following Rust code produce when trying to select maximum non-overlapping intervals using a greedy approach?
DSA Rust
fn max_non_overlapping_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
intervals.sort_by_key(|k| k.0); // sort by start time
let mut result = Vec::new();
let mut last_end = std::i32::MIN;
for interval in intervals {
if interval.0 >= last_end {
result.push(interval);
last_end = interval.1;
}
}
result
}
fn main() {
let intervals = vec![(1, 3), (2, 5), (4, 7)];
let selected = max_non_overlapping_intervals(intervals);
println!("{:?}", selected);
}Attempts:
2 left
💡 Hint
Check the sorting criteria for intervals in greedy scheduling.
✗ Incorrect
Greedy interval scheduling requires sorting by finish time, not start time. Sorting by start time can lead to a suboptimal number of selected intervals.
🚀 Application
advanced2:00remaining
Greedy Algorithm for Activity Selection Output
Given activities with start and end times [(0, 6), (1, 4), (3, 5), (5, 7), (8, 9), (5, 9)], what is the output of the greedy activity selection algorithm that picks activities by earliest finish time?
DSA Rust
fn activity_selection(mut activities: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
activities.sort_by_key(|k| k.1); // sort by finish time
let mut selected = Vec::new();
let mut last_finish = std::i32::MIN;
for activity in activities {
if activity.0 >= last_finish {
selected.push(activity);
last_finish = activity.1;
}
}
selected
}
fn main() {
let activities = vec![(0, 6), (1, 4), (3, 5), (5, 7), (8, 9), (5, 9)];
let result = activity_selection(activities);
println!("{:?}", result);
}Attempts:
2 left
💡 Hint
Remember to pick activities that start after or when the last selected activity finishes.
✗ Incorrect
Sorted by finish time: (1,4), (3,5), (0,6), (5,7), (5,9), (8,9). Pick (1,4), then (5,7), then (8,9).
🧠 Conceptual
expert3:00remaining
Why Greedy Algorithm Guarantees Optimality in Huffman Coding
Why does the greedy approach of combining two least frequent nodes at each step guarantee an optimal prefix code in Huffman coding?
Attempts:
2 left
💡 Hint
Think about how frequency affects code length in prefix codes.
✗ Incorrect
Huffman coding's greedy step ensures that less frequent symbols have longer codes and more frequent symbols have shorter codes, minimizing the total weighted path length.