Why Dynamic Programming and When Recursion Alone Fails in DSA Typescript - Test Your Knowledge

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 to handle base cases.

The Fibonacci sequence is calculated by adding the two previous numbers. So we use the '+' operator.

2fill in blank

medium

Complete the code to add memoization to the recursive Fibonacci function.

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

Not using memo array to store results.

Using wrong operator instead of addition.

Memoization stores results to avoid repeated calculations. The addition operator '+' combines the two previous Fibonacci numbers.

3fill in blank

hard

Fix the error in the recursive factorial function to correctly calculate factorial.

DSA Typescript

function factorial(n: number): number {
  if (n === 0) return 1;
  return n [1] factorial(n - 1);
}

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

A+

B-

C/

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of multiplication.

Missing base case for n=0.

Factorial is the product of all positive integers up to n, so we multiply n by factorial(n-1).

4fill in blank

hard

Fill both blanks to create a dynamic programming solution for Fibonacci using bottom-up approach.

DSA Typescript

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

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

A<=

B<

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= in loop condition causing extra iteration.

Using subtraction instead of addition for dp calculation.

The loop runs while i is less than or equal to n, and each dp[i] is the sum of the two previous dp values.

5fill in blank

hard

Fill all three blanks to implement memoized recursion for the coin change problem.

DSA Typescript

function coinChange(coins: number[], amount: number, memo: Map<number, number> = new Map()): number {
  if (amount === 0) return 0;
  if (amount < 0) return -1;
  if (memo.has(amount)) return memo.get(amount) as number;
  let minCoins = Infinity;
  for (const coin of coins) {
    const res = coinChange(coins, amount [1] coin, memo);
    if (res >= 0 && res [2] minCoins) {
      minCoins = res [3] 1;
    }
  }
  memo.set(amount, minCoins === Infinity ? -1 : minCoins);
  return memo.get(amount) as number;
}

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 for amount update.

Using > instead of < for comparison.

Forgetting to add 1 when updating minCoins.

We subtract the coin value from amount, check if result is less than minCoins, and update minCoins by adding 1 to res.