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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

intervals.sort((a, b) => a.end [1] b.end);

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in the sort comparator.

Sorting by start time instead of end time.

Sorting intervals by their end time requires subtracting b.end from a.end to get ascending order.

2fill in blank

medium

Complete the code to check if the current interval starts after the last selected interval ends.

DSA Typescript

if (interval.start [1] lastSelectedEnd) { selected.push(interval); lastSelectedEnd = interval.end; }

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

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= instead of >, which allows overlapping intervals.

Using < or <=, which is incorrect for this condition.

We select the interval only if it starts after the last selected interval ends, so interval.start > lastSelectedEnd.

3fill in blank

hard

Fix the error in the greedy coin change algorithm that fails for non-standard coin sets.

DSA Typescript

function greedyChange(amount: number, coins: number[]): number[] {
  coins.sort((a, b) => b - a);
  const result: number[] = [];
  for (const coin of coins) {
    while (amount [1] coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}

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

A>=

B<=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of >= causes missing exact matches.

Using < or <= causes infinite loops or no coins used.

The loop should run while amount is greater than or equal to the coin value to use that coin.

4fill in blank

hard

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

DSA Typescript

const lengths = { [1]: [2] for (const word of words) if (word.length > 3) };

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

Aword

Bword.length

Cword.toUpperCase()

Dword.length > 3

Attempts:

3 left

💡 Hint

Common Mistakes

Using the condition as a key or value.

Using uppercase words as keys instead of original words.

The key is the word itself, and the value is its length.

5fill in blank

hard

Fill all three blanks to create a map filtering entries with positive values and mapping keys to uppercase.

DSA Typescript

const filteredMap = new Map(Object.entries(data)
  .filter(([[1], [2]]) => [2] > 0)
  .map(([[1], [2]]) => [[3], [2]])
);

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

Akey

Bvalue

Ckey.toUpperCase()

Dvalue.toUpperCase()

Attempts:

3 left

💡 Hint

Common Mistakes

Using value.toUpperCase() which is invalid if value is a number.

Mixing up key and value in filter or map.

We destructure entries into key and value, filter by value > 0, and map keys to uppercase with their values.

Practice

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

easy

A. Because it tries all possible solutions and picks the best one

B. Because it uses recursion to explore all paths

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 picks the best local option at each step without reconsidering previous choices.

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices lead to the overall best solution, which is why greedy works.

3. Final Answer:

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

4. Quick Check:

   Greedy = best local choice each step [OK]

Hint: Greedy picks best now, hoping for best overall [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 start a greedy algorithm loop in TypeScript to process an array arr?

easy

A. for (let i = 0; i < arr.length; i++) { /* greedy step */ }

B. while (arr.length) { /* greedy step */ }

C. for (const i in arr) { /* greedy step */ }

D. do { /* greedy step */ } while (arr.length)

Solution

1. Step 1: Identify standard for loop syntax

   The standard way to iterate over an array with index in TypeScript is using for (let i = 0; i < arr.length; i++).

2. Step 2: Check other options for correctness

   while (arr.length) { /* greedy step */ } and D use while/do-while but lack index control; for (const i in arr) { /* greedy step */ } uses for...in which iterates keys but is less common and can cause issues.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) { /* greedy step */ } -> Option A

4. Quick Check:

   Standard for loop = for (let i = 0; i < arr.length; i++) { /* greedy step */ } [OK]

Hint: Use for(let i=0; i

Common Mistakes:

• Using for...in for arrays causing unexpected keys
• Missing loop condition causing infinite loops
• Using while without index control

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

const intervals = [[1,4],[3,5],[0,6],[5,7],[8,9],[5,9]];
intervals.sort((a,b) => a[1] - b[1]);
let count = 0;
let end = -Infinity;
for (const [start, finish] of intervals) {
  if (start >= end) {
    count++;
    end = finish;
  }
}
console.log(count);

What is the output?

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [1,4], [3,5], [0,6], [5,7], [8,9], [5,9]

2. Step 2: Select intervals greedily

   Start with end = -Infinity.
   Pick [1,4] (start 1 >= -Infinity), count=1, end=4.
   Next [3,5] start 3 < 4 skip.
   Next [0,6] start 0 < 4 skip.
   Next [5,7] start 5 >= 4 pick, count=2, end=7.
   Next [8,9] start 8 >= 7 pick, count=3, end=9.
   Next [5,9] start 5 < 9 skip.

3. Step 3: Count total selected intervals

   Total count = 3

4. Final Answer:

   3 -> Option B

5. Quick Check:

   Greedy interval count = 3 [OK]

Hint: Sort by finish time, pick non-overlapping intervals [OK]

Common Mistakes:

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

4. The following code attempts to solve the coin change problem greedily by always picking the largest coin first:

const coins = [25, 10, 5, 1];
function greedyChange(amount: number): number {
  let count = 0;
  for (const coin of coins) {
    count += Math.floor(amount / coin);
    amount %= coin;
  }
  return count;
}
console.log(greedyChange(30));

What is the output and what is the bug if any?

medium

A. 6; Bug: code does not reduce amount correctly

B. 3; Bug: greedy fails for some coin sets

C. Error; Syntax mistake in code

D. 2; No bug, greedy works for US coins

Solution

1. Step 1: Trace greedyChange(30)

   Coins: 25,10,5,1
   25 fits once (30/25=1), count=1, amount=30%25=5
   10 fits zero times (5/10=0), count=1, amount=5
   5 fits once (5/5=1), count=2, amount=0
   1 fits zero times, count=2

2. Step 2: Check if greedy works here

   For US coins, greedy always gives minimum coins. So output is 2 and no bug here.

3. Final Answer:

   2; No bug, greedy works for US coins -> Option D

4. Quick Check:

   Greedy coin change = 2 [OK]

Hint: Greedy coin works for standard US coins [OK]

Common Mistakes:

• Assuming greedy always fails coin change
• Miscomputing amount after division
• Confusing output count with amount

5. You want to select activities from a list with start and end times to maximize the number of activities chosen. However, the activities have a penalty cost if chosen consecutively. Which approach best solves this problem?

hard

A. Use dynamic programming to consider penalties and maximize total benefit

B. Use brute force to try all subsets without pruning

C. Sort activities by start time and pick all that fit ignoring penalties

D. Use a greedy algorithm selecting earliest finishing activities ignoring penalties

Solution

1. Step 1: Understand problem constraints

   Activities have penalties if chosen consecutively, so simple greedy ignoring penalties may fail.

2. Step 2: Choose algorithm considering penalties

   Dynamic programming can track choices and penalties to find maximum benefit, unlike greedy which only looks locally.

3. Final Answer:

   Use dynamic programming to consider penalties and maximize total benefit -> Option A

4. Quick Check:

   Penalties require DP, not greedy [OK]

Hint: Penalties break greedy; use DP for best solution [OK]

Common Mistakes:

• Ignoring penalties and using greedy
• Assuming sorting by start time is enough
• Trying brute force without pruning