Why Greedy Works and When It Fails in DSA Java - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to select the next activity with the earliest finish time.

DSA Java

int selectNextActivity(List<Activity> activities) {
    int n = activities.size();
    int lastFinish = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (activities.get(i).start >= [1]) {
            count++;
            lastFinish = activities.get(i).finish;
        }
    }
    return count;
}

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

An

Bcount

ClastFinish

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the count variable instead of lastFinish.

Using the loop index i instead of lastFinish.

Comparing with the total number of activities n.

The greedy choice is to pick the next activity that starts after the last selected activity finishes. So we compare the current activity's start time with lastFinish.

2fill in blank

medium

Complete the code to sort activities by their finish time before selecting them.

DSA Java

Collections.sort(activities, (a, b) -> a.[1] - b.[1]);

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

Afinish

Bstart

Cduration

Dpriority

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of finish time.

Sorting by duration or priority which may not guarantee optimality.

Sorting activities by their finish time allows the greedy algorithm to pick the earliest finishing activity first, which leads to an optimal solution.

3fill in blank

hard

Fix the error in the greedy coin change algorithm that fails for certain coin sets.

DSA Java

int minCoins(int[] coins, int amount) {
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= [1]) {
            amount -= coins[i];
            count++;
        }
    }
    return amount == 0 ? count : -1;
}

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

Acoins[i]

Bamount

Ccount

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing amount with itself or other variables instead of the coin value.

Using count or index i in the condition which causes wrong behavior.

The condition should check if the remaining amount is at least the value of the current coin coins[i] before subtracting it.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that filters words longer than 3 letters and maps them to their lengths.

DSA Java

Map<String, Integer> lengths = words.stream()
    .filter(word -> word.length() [1] 3)
    .collect(Collectors.toMap(word -> word, word -> word.[2]()));

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

A>

Blength

C<

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the filter condition.

Using 'size()' which is not a String method.

Using incorrect method names for length.

The filter keeps words with length greater than 3, and the map stores each word with its length using word.length().

5fill in blank

hard

Fill all three blanks to create a map comprehension that uppercases keys, keeps values, and filters values greater than 0.

DSA Java

Map<String, Integer> result = data.entrySet().stream()
    .filter(e -> e.getValue() [1] 0)
    .collect(Collectors.toMap(e -> e.getKey().[2](), e -> e.[3]()));

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

A>

BgetValue

CtoUpperCase

DgetKey

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the filter condition which reverses logic.

Using 'getKey()' instead of 'getValue()' for values.

Not uppercasing keys correctly.

The filter keeps entries with values greater than 0, so the operator should be '>' to exclude non-positive values. The keys are uppercased with toUpperCase(), and values are accessed with getValue().

Practice

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

easy

A. Because it uses recursion to explore all paths

B. Because it tries all possible solutions and picks the best

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

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm chooses the best option available at each step without reconsidering previous choices.

2. Step 2: Connect greedy choice to global optimum

   This local best choice leads to a global optimum only if the problem has the greedy choice property.

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 now, not all possibilities [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting alone makes greedy correct

2. Which of the following is the correct syntax to start a greedy algorithm loop in Java to process an array arr of length n?

easy

A. foreach (int i : arr)

B. for i in range(0, n):

C. while (i <= n) { i++; }

D. for (int i = 0; i < n; i++)

Solution

1. Step 1: Identify Java loop syntax

   Java uses for loops with initialization, condition, and increment: for (int i = 0; i < n; i++)

2. Step 2: Check options for Java correctness

   for (int i = 0; i < n; i++) matches Java syntax; B is Python, C is incomplete and incorrect, D is incorrect syntax for array iteration.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option D

4. Quick Check:

   Java for loop syntax = for (int i = 0; i < n; i++) [OK]

Hint: Java for loops use int i=0; i

Common Mistakes:

• Using Python syntax in Java
• Incorrect loop conditions
• Misusing foreach syntax

3. Consider the following Java code snippet for selecting intervals greedily by earliest finish time:

int[][] intervals = {{1,3},{2,5},{4,7}};
Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int count = 0, end = 0;
for (int[] interval : intervals) {
  if (interval[0] >= end) {
    count++;
    end = interval[1];
  }
}
System.out.println(count);

What is the output?

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals by end time: {1,3}, {2,5}, {4,7}

2. Step 2: Select intervals greedily

   Select {1,3} first (count=1, end=3). Next {2,5} starts at 2 < 3, skip. Next {4,7} starts at 4 >= 3, select (count=2).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Greedy interval selection = 2 [OK]

Hint: Pick intervals by earliest finish time [OK]

Common Mistakes:

• Not sorting intervals
• Selecting overlapping intervals
• Counting all intervals without check

4. The following Java code attempts to solve the coin change problem using a greedy approach:

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
System.out.println(count);

What is the output and what is the problem with this approach?

medium

A. 3; Greedy fails because it doesn't find minimum coins

B. 3; Greedy always finds minimum coins

C. 6; Code has syntax error

D. 0; Code does not run

Solution

1. Step 1: Trace greedy coin selection

   Start with coin 4: amount=6>=4, subtract 4 (amount=2), count=1. Next coin 3: amount=2<3 skip. Next coin 1: amount=2>=1 subtract twice, count=3 total coins.

2. Step 2: Check minimum coins possible

   Minimum coins for 6 are 2 (3+3), but greedy picks 3 coins (4+1+1). Greedy fails here.

3. Final Answer:

   3; Greedy fails because it doesn't find minimum coins -> Option A

4. Quick Check:

   Greedy coin change fails = 3; Greedy fails because it doesn't find minimum coins [OK]

Hint: Greedy may fail if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Confusing output count with amount

5. You want to schedule the maximum number of non-overlapping meetings in one room. Meetings are given as int[][] meetings = {{0, 30}, {5, 10}, {15, 20}, {25, 35}}. Which greedy strategy will always give the optimal solution and why?

hard

A. Select meetings by earliest finish time because it leaves room for more meetings

B. Select meetings by shortest duration because shorter meetings fit more

C. Select meetings by latest start time because it prioritizes recent meetings

D. Select meetings by earliest start time because it schedules more meetings

Solution

1. Step 1: Understand meeting scheduling problem

   Goal is to maximize non-overlapping meetings in one room.

2. Step 2: Analyze greedy strategies

   Choosing earliest finish time frees room earliest, allowing more meetings after.

3. Step 3: Check other strategies

   Earliest start or shortest duration can cause overlaps or miss optimal sets.

4. Final Answer:

   Select meetings by earliest finish time because it leaves room for more meetings -> Option A

5. Quick Check:

   Earliest finish time = optimal scheduling [OK]

Hint: Pick meetings finishing earliest to fit more [OK]

Common Mistakes:

• Choosing earliest start time
• Picking shortest duration meetings
• Ignoring finish times