DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA Typescript

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) [1] fib(n - 2);
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting base cases for n <= 1.

Fibonacci numbers are calculated by adding the two previous numbers, so the operator must be '+'.

2fill in blank

medium

Complete the code to use memoization in Fibonacci calculation to avoid repeated work.

DSA Typescript

function fibMemo(n: number, memo: number[] = []): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n - 1, memo) [1] fibMemo(n - 2, memo);
  return memo[n];
}

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

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operator in combining recursive calls.

Not storing the result in memo array.

Memoization stores results of fib(n) to avoid repeated addition of previous two Fibonacci numbers.

3fill in blank

hard

Fix the error in this greedy approach to coin change problem that tries to minimize coins used.

DSA Typescript

function minCoins(coins: number[], amount: number): number {
  coins.sort((a, b) => b - a);
  let count = 0;
  for (let coin of coins) {
    while (amount >= coin) {
      amount [1] coin;
      count++;
    }
  }
  return amount === 0 ? count : -1;
}

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

A*=

B+=

C-=

D/=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+=' which increases amount causing infinite loop.

Using '*=' or '/=' which are incorrect for subtraction.

To reduce the amount by the coin value, we must subtract coin from amount using '-=' operator.

4fill in blank

hard

Fill both blanks to complete the bottom-up dynamic programming solution for Fibonacci numbers.

DSA Typescript

function fibDP(n: number): number {
  if (n <= 1) return n;
  let dp: number[] = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - [1]] [2] dp[i - 2];
  }
  return dp[n];
}

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

A1

B2

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices like i-2 and i-3.

Using subtraction instead of addition.

We calculate dp[i] by adding dp[i-1] and dp[i-2], so blanks are '1' and '+'.

5fill in blank

hard

Fill all three blanks to complete the greedy algorithm for activity selection problem.

DSA Typescript

function maxActivities(start: number[], end: number[]): number {
  let n = start.length;
  let activities = start.map((s, i) => ({ start: s, end: end[i] }));
  activities.sort((a, b) => a.[1] - b.[2]);
  let count = 1;
  let lastEnd = activities[0].end;
  for (let i = 1; i < n; i++) {
    if (activities[i].start >= [3]) {
      count++;
      lastEnd = activities[i].end;
    }
  }
  return count;
}

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

Astart

Bend

ClastEnd

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of end time.

Comparing start with count or start instead of lastEnd.

We sort activities by their end time (end), and select next activity if its start >= lastEnd.