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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci number using simple recursion.

DSA Javascript

function fib(n) {
  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 to return the sum.

The Fibonacci number is the sum of the two previous Fibonacci numbers, so we add fib(n - 1) and fib(n - 2).

2fill in blank

medium

Complete the code to implement memoization for Fibonacci to avoid repeated calculations.

DSA Javascript

function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) 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

Not storing the result in memo.

Using wrong operators instead of addition.

Memoization stores results of fib(n - 1) and fib(n - 2) and adds them to avoid repeated work.

3fill in blank

hard

Fix the error in the greedy approach to select maximum number of activities that don't overlap.

DSA Javascript

function maxActivities(activities) {
  activities.sort((a, b) => a.end [1] b.end);
  let count = 1;
  let lastEnd = activities[0].end;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      count++;
      lastEnd = activities[i].end;
    }
  }
  return count;
}

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

A>

B+

C<

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition in sort comparator causing wrong order.

Sorting by start time instead of end time.

To sort activities by their end time ascending, we subtract b.end from a.end.

4fill in blank

hard

Fill in the blank to create a dynamic programming table for the 0/1 Knapsack problem.

DSA Javascript

function knapsack(weights, values, W) {
  const n = weights.length;
  const dp = Array(n + 1).fill(null).map(() => Array(W + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i - 1] [1] w) {
        dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][W];
}

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

A<

B>=

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators causing incorrect table filling.

Mixing up indices in dp array.

We check if the current item's weight is less than or equal to the current capacity (w) to decide inclusion. The Math.max compares excluding and including the item.

5fill in blank

hard

Fill all three blanks to implement a greedy algorithm for coin change problem (minimum coins).

DSA Javascript

function minCoins(coins, amount) {
  coins.sort((a, b) => b [1] a);
  let count = 0;
  let i = 0;
  while (amount > 0 && i < coins.length) {
    if (coins[i] [2] amount) {
      count += Math.floor(amount [3] coins[i]);
      amount = amount % coins[i];
    }
    i++;
  }
  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

Sorting coins ascending instead of descending.

Using wrong comparison operators in if condition.

Using multiplication instead of division to count coins.

Sort coins descending (b - a). Check if coin value is less than or equal to amount. Use division (/) to find how many coins fit.

Practice

1. Which approach is best suited when a problem can be broken down into overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand overlapping subproblems and optimal substructure

   Dynamic Programming is designed for problems where subproblems repeat and solutions build on smaller solutions.

2. Step 2: Compare with other approaches

   Greedy algorithms do not always consider overlapping subproblems, recursion without memoization repeats work, and brute force is inefficient.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Look for repeated subproblems and optimal substructure [OK]

Common Mistakes:

• Confusing greedy with DP for overlapping subproblems
• Ignoring memoization in recursion
• Choosing brute force for efficiency

2. Which of the following is the correct syntax to define a recursive function in JavaScript?

easy

A. function factorial(n) { while(n > 0) return n * factorial(n - 1); }

B. function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); }

C. function factorial(n) { for(let i=0; i

D. function factorial(n) { if (n === 0) return 0; return n + factorial(n - 1); }

Solution

1. Step 1: Check base case correctness

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } returns 1 when n is 0, which is correct for factorial.

2. Step 2: Check recursive call and return statement

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } correctly multiplies n by factorial(n-1). Others have incorrect loops or wrong base cases.

3. Final Answer:

   function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } -> Option B

4. Quick Check:

   Correct base case and recursive call = function factorial(n) { if (n === 0) return 1; return n * factorial(n - 1); } [OK]

Hint: Base case must stop recursion; recursive call must reduce problem size [OK]

Common Mistakes:

• Using loops inside recursion incorrectly
• Wrong base case value
• Returning addition instead of multiplication for factorial

3. What will be the output of the following JavaScript code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 8

B. 3

C. 5

D. 13

Solution

1. Step 1: Understand the Fibonacci function with memoization

   fib(5) calculates the 5th Fibonacci number using memo to avoid repeated work.

2. Step 2: Calculate fib(5) step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 with memoization [OK]

Hint: Memoization caches results to speed recursion [OK]

Common Mistakes:

• Confusing Fibonacci index with value
• Ignoring memo object causing slow recursion
• Mixing up base cases

4. Find the error in this greedy algorithm code snippet for coin change problem:

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

medium

A. Return statement should always return count

B. Missing base case for amount = 0

C. Using while loop inside for loop is incorrect

D. coins.sort() sorts ascending, should sort descending

Solution

1. Step 1: Check sorting order for greedy coin change

   Greedy coin change requires coins sorted descending to pick largest first.

2. Step 2: Identify sorting mistake

   coins.sort() sorts ascending by default, so it should be coins.sort((a,b) => b - a).

3. Final Answer:

   coins.sort() sorts ascending, should sort descending -> Option D

4. Quick Check:

   Sort descending for greedy coin change [OK]

Hint: Sort coins descending for greedy coin change [OK]

Common Mistakes:

• Using default ascending sort
• Ignoring sorting affects greedy choice
• Assuming while loop is wrong here

5. You want to find the minimum number of jumps to reach the end of an array where each element represents max jump length at that position. Which approach is best and why?

const arr = [2,3,1,1,4];

hard

A. Greedy, because it chooses the farthest reachable index at each step

B. Recursion without memoization, to explore all paths

C. Dynamic Programming, to store minimum jumps for each index

D. Brute force, to try every possible jump

Solution

1. Step 1: Understand the problem nature

   Minimum jumps problem can be solved efficiently by greedy approach choosing the farthest reachable index.

2. Step 2: Compare approaches

   Recursion without memoization and brute force are inefficient; DP is possible but greedy is optimal and simpler here.

3. Final Answer:

   Greedy, because it chooses the farthest reachable index at each step -> Option A

4. Quick Check:

   Minimum jumps = Greedy approach [OK]

Hint: Pick farthest reachable index greedily for minimum jumps [OK]

Common Mistakes:

• Using recursion without memoization causing timeout
• Overcomplicating with DP when greedy suffices
• Trying brute force leading to inefficiency