Overlapping Subproblems and Optimal Substructure in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the nth Fibonacci number using 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.

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2). So the correct operator is '+'.

2fill in blank

medium

Complete the code to store computed Fibonacci values in a memo object to avoid repeated calculations.

DSA Typescript

function fibMemo(n: number, memo: {[key: number]: number} = {}): number {
  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

Using wrong operator in memoized calculation.

Not returning memo[n] after storing.

Memoization stores results of fib(n-1) + fib(n-2) to avoid repeated work. So '+' is correct.

3fill in blank

hard

Fix the error in the code to correctly check if a memoized value exists for n.

DSA Typescript

function fibMemoFix(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[[1]]) return memo[n];
  memo[n] = fibMemoFix(n - 1, memo) + fibMemoFix(n - 2, memo);
  return memo[n];
}

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

An

Bn - 1

C0

Dundefined

Attempts:

3 left

💡 Hint

Common Mistakes

Checking memo[n-1] instead of memo[n].

Checking memo[0] or memo[undefined].

The memo object keys are indexed by n, so the check must be memo[n].

4fill in blank

hard

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

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, leaving dp[n] uninitialized.

Using '-' instead of '+' in dp calculation.

The loop must run from i=2 to i <= n to compute dp[n]. Here, '<=' is correct. The Fibonacci sum uses '+'.

5fill in blank

hard

Fill all three blanks to create a function that uses memoization and demonstrates optimal substructure.

DSA Typescript

function fibOptimal(n: number, memo: {[key: number]: number} = {}): number {
  if (n <= 1) return n;
  if (memo[[1]]) return memo[n];
  memo[n] = fibOptimal(n [2] 1, memo) [3] fibOptimal(n - 2, memo);
  return memo[n];
}

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

An

B-

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Checking wrong memo key.

Using wrong operator in recursive calls.

Check memo[n] to reuse results. The recursive calls use n - 1 and n - 2, summed with '+'.