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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to select the next item with the highest value-to-weight ratio in the greedy algorithm for the fractional knapsack problem.

DSA C

int selectNextItem(float values[], float weights[], int n) {
    int maxIndex = 0;
    float maxRatio = values[0] / weights[0];
    for (int i = 1; i < n; i++) {
        float ratio = values[i] / weights[i];
        if (ratio [1] maxRatio) {
            maxRatio = ratio;
            maxIndex = i;
        }
    }
    return maxIndex;
}

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

A>

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes the algorithm to pick the lowest ratio item.

Using '==' will never update maxRatio after initialization.

The greedy choice is to pick the item with the highest value-to-weight ratio, so the comparison must be '>' to update maxRatio.

2fill in blank

medium

Complete the code to check if the greedy algorithm fails for the coin change problem with arbitrary coin denominations.

DSA C

int canMakeChange(int coins[], int n, int amount) {
    int count = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    if (amount [1] 0) {
        return count;
    } else {
        return -1; // Cannot make exact change
    }
}

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

A==

B<

C>

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if amount > 0 instead of == 0 leads to incorrect success.

Using '!=' causes the function to return count even when change is not exact.

The greedy algorithm succeeds only if the remaining amount is exactly zero after using coins.

3fill in blank

hard

Fix the error in the greedy interval scheduling algorithm that selects intervals with earliest finish time.

DSA C

void greedyIntervalScheduling(int start[], int finish[], int n) {
    int count = 1;
    int lastFinish = finish[0];
    for (int i = 1; i < n; i++) {
        if (start[i] [1] lastFinish) {
            count++;
            lastFinish = finish[i];
        }
    }
    printf("Maximum intervals: %d\n", count);
}

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

A<

B>

C<=

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' causes incorrect counting of overlapping intervals.

Using '<' or '>=' may include intervals that overlap or just touch.

We select the next interval only if its start time is strictly greater than the last finish time to avoid overlap.

4fill in blank

hard

Fill both blanks to complete the greedy algorithm for activity selection that sorts intervals by finish time and selects compatible activities.

DSA C

void activitySelection(int start[], int finish[], int n) {
    // Assume intervals are sorted by finish time
    int count = 1;
    int lastSelected = 0;
    for (int i = 1; i < n; i++) {
        if (start[i] [1] finish[lastSelected]) {
            count++;
            lastSelected = [2];
        }
    }
    printf("Number of activities selected: %d\n", count);
}

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

A>=

B>

Ci

DlastSelected

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '>=' may exclude activities that start exactly at the finish time.

Not updating lastSelected to i causes incorrect tracking of selected activities.

We select the next activity if its start time is greater or equal to the last selected finish time, and update lastSelected to the current index i.

5fill in blank

hard

Fill all three blanks to implement a greedy approach that builds a solution by choosing the locally optimal option at each step.

DSA C

void greedySolution(int arr[], int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] [1] 0) {
            result += arr[i] [2] 1;
        } else {
            result [3] arr[i];
        }
    }
    printf("Result: %d\n", result);
}

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

A>

B+=

C=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' reverses the condition logic.

Using '=' instead of '+=' causes loss of accumulated result.

We check if arr[i] > 0, then add 1 to result; else assign result to arr[i]. This shows a greedy choice and accumulation.