Memoization Top Down DP in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

const memo: Record<number, number> = [1];

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

A{}

B[]

Cnull

Dnew Map()

Attempts:

3 left

💡 Hint

Common Mistakes

Using an array [] instead of an object for memo.

Setting memo to null causes errors when accessing keys.

We use an empty object {} to store computed results by keys (numbers).

2fill in blank

medium

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

DSA Typescript

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

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

Aundefined

Bmemo

Cn

Dresult

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if 'memo' in memo is incorrect.

Checking for 'result' or 'undefined' keys is wrong.

We check if the key n exists in memo to reuse the stored result.

3fill in blank

hard

Fix the error in the recursive call to compute Fibonacci with memoization.

DSA Typescript

const fib = (n: number): number => {
  if (n <= 1) return n;
  if (n in memo) return memo[n];
  memo[n] = fib([1]) + fib(n - 2);
  return memo[n];
};

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

An - 1

Bn + 1

Cn - 3

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n - 3 skips necessary Fibonacci steps.

The Fibonacci sequence sums fib(n-1) and fib(n-2).

4fill in blank

hard

Fill both blanks to complete the memoized factorial function.

DSA Typescript

const factorial = (n: number): number => {
  if (n <= 1) return 1;
  if ([1] in memo) return memo[n];
  memo[n] = n * factorial([2]);
  return memo[n];
};

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

An

Bn - 1

Cmemo

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'memo' instead of 'n' in memo.

Calling factorial(1) always instead of factorial(n-1).

Check if n is in memo, then recursively call factorial(n-1).

5fill in blank

hard

Fill all three blanks to create a memoized function that computes the nth Tribonacci number.

DSA Typescript

const tribMemo: Record<number, number> = {};
const tribonacci = (n: number): number => {
  if (n <= 1) return n;
  if (n === 2) return 1;
  if ([1] in tribMemo) return tribMemo[n];
  tribMemo[n] = tribonacci([2]) + tribonacci(n - 2) + tribonacci([3]);
  return tribMemo[n];
};

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

An

Bn - 1

Cn - 3

Dn - 4

Attempts:

3 left

💡 Hint

Common Mistakes

Using n-4 instead of n-3 breaks the sequence.

Checking for wrong keys in tribMemo.

Check if n is in tribMemo, then sum tribonacci(n-1), tribonacci(n-2), and tribonacci(n-3).