DP vs Recursion vs Greedy Choosing the Right Tool in DSA Typescript - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Function

What is the output of the following TypeScript code that uses recursion to calculate Fibonacci numbers?

DSA Typescript

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(5));

A 3

B 8

C 13

D 5

💡 Hint

Trace the recursive calls for fib(5).

The recursive function fib calculates Fibonacci numbers where fib(0)=0 and fib(1)=1. For fib(5), the result is 5.

🧠 Conceptual

intermediate

Choosing Greedy vs Dynamic Programming

Which problem characteristic best indicates that a greedy algorithm is the right choice over dynamic programming?

A Optimal substructure without overlapping subproblems

B No optimal substructure

C Optimal substructure and overlapping subproblems

D Overlapping subproblems without optimal substructure

💡 Hint

Greedy algorithms work when local choices lead to global optimum.

Greedy algorithms work best when the problem has optimal substructure but does not require solving overlapping subproblems, unlike dynamic programming.

🔧 Debug

advanced

Why Does This Memoized Recursive Code Fail?

Consider this TypeScript code for memoized recursion to compute factorial. What error does it produce?

DSA Typescript

function factorial(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}
console.log(factorial(0));

A Returns 1

B Stack overflow error

C TypeError: Cannot read property of undefined

D Returns undefined

💡 Hint

Check base case for n=0.

The base case covers n <= 1, so factorial(0) returns 1 correctly without error.

❓ Predict Output

advanced

Output of Greedy Coin Change Algorithm

What is the output of this TypeScript code that uses a greedy approach to make change for 30 cents with coins [25, 10, 5, 1]?

DSA Typescript

function greedyChange(coins: number[], amount: number): number[] {
  const result: number[] = [];
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}
console.log(greedyChange([25, 10, 5, 1], 30));

A [5, 5, 5, 5, 5, 5]

B [25, 5]

C [25, 1, 1, 1, 1, 1]

D [10, 10, 10]

💡 Hint

Greedy picks largest coin first.

The greedy algorithm picks 25 first, then 5 to make 30 cents.

🧠 Conceptual

expert

When Is Dynamic Programming Necessary Over Greedy?

Which scenario best explains when dynamic programming is necessary instead of a greedy approach?

A When local optimal choices always lead to global optimum

B When the problem has optimal substructure but no overlapping subproblems

C When the problem has optimal substructure and overlapping subproblems requiring exploration of all subproblems

D When the problem has no optimal substructure

💡 Hint

Dynamic programming solves overlapping subproblems efficiently.

Dynamic programming is needed when the problem has both optimal substructure and overlapping subproblems, requiring careful reuse of solutions.