Memoization to Optimize Recursion in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of recursion?

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does memoization improve recursive function performance?

By saving results of subproblems, memoization prevents the function from recalculating the same values multiple times, reducing time complexity from exponential to linear in many cases.

beginner

In TypeScript, what data structure is commonly used to implement memoization?

A JavaScript object or Map is commonly used to store computed results with input parameters as keys for quick lookup.

intermediate

Explain with a simple example how memoization works in a Fibonacci recursive function.

In a Fibonacci function, memoization stores the result of fib(n) after computing it once. When fib(n) is needed again, the stored value is returned immediately instead of recalculating fib(n-1) and fib(n-2).

intermediate

What is the difference between memoization and tabulation?

Memoization is a top-down approach that caches results during recursion, while tabulation is a bottom-up approach that builds a table iteratively without recursion.

What does memoization primarily help to reduce in recursive functions?

A Number of function parameters

B Repeated calculations of the same subproblems

C Memory usage by deleting variables

D Code length

Memoization stores results of subproblems to avoid recalculating them, reducing repeated work.

Which data structure is best suited for memoization in TypeScript?

A Map or Object

B Array

C Set

D String

Map or Object allows storing key-value pairs for quick lookup of computed results.

What is the time complexity improvement when using memoization on Fibonacci recursion?

A From O(n) to O(1)

B No improvement

C From O(2^n) to O(n)

D From O(n^2) to O(n^3)

Memoization reduces exponential time O(2^n) to linear time O(n) by caching results.

Memoization is an example of which programming technique?

A Greedy algorithm

B Brute force

C Divide and conquer

D Dynamic programming

Memoization is a dynamic programming technique that stores intermediate results.

Which of the following is NOT true about memoization?

A It always reduces space complexity

B It uses extra memory to store results

C It avoids repeated recursive calls

D It can be implemented using a cache

Memoization uses extra memory, so it does not reduce space complexity; it may increase it.

Describe how memoization optimizes a recursive Fibonacci function.

Think about how repeated calls to fib(n) are handled.

Explain the difference between memoization and tabulation in dynamic programming.

Consider the order of solving subproblems.