Memoization to Optimize Recursion in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the memo object for caching results.

DSA Typescript

const memo: [1] = {};

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

ASet<number>

BArray<number>

CRecord<number, number>

DMap<number, number>

Attempts:

3 left

💡 Hint

Common Mistakes

Using Array instead of an object for memoization.

Using Set which only stores unique values without keys.

We use a Record with number keys and number values to store computed results for each input number.

2fill in blank

medium

Complete the code to check if the result for n is already cached in memo.

DSA Typescript

if ([1] in memo) return memo[n];

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

Acache

Bmemo

Cresult

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if 'memo' is in memo (wrong variable).

Using 'result' or 'cache' which are not defined here.

We check if the input number n is a key in the memo object to reuse the cached result.

3fill in blank

hard

Fix the error in storing the computed Fibonacci value in memo.

DSA Typescript

memo[n] = [1] + [2];

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

Afib(n - 1)

Bfib(n - 2)

Cmemo[n - 1]

Dmemo[n - 2]

Attempts:

3 left

💡 Hint

Common Mistakes

Calling fib recursively again instead of using memoized values.

Mixing up memo keys or using wrong indices.

We store the sum of previously computed Fibonacci values from memo to avoid repeated recursion.

4fill in blank

hard

Fill both blanks to complete the memoized Fibonacci function.

DSA Typescript

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

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

Ain

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' or '*' instead of '+' for Fibonacci addition.

Using wrong operator for checking memo keys.

We check if n is in memo and then add the results of fib(n-1) and fib(n-2) to store in memo.

5fill in blank

hard

Fill all three blanks to create a memoized factorial function.

DSA Typescript

const factorialMemo: Record<number, number> = {};
function factorial(n: number): number {
  if (n <= 1) return 1;
  if (n [1] factorialMemo) return factorialMemo[n];
  factorialMemo[n] = n [2] factorial(n [3] 1);
  return factorialMemo[n];
}

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

Ain

B*

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '*' for multiplication.

Using '+' instead of '-' to decrement n.

Not checking cache correctly.

We check if n is in factorialMemo, then multiply n by factorial(n-1) and store the result.