Memoization in JavaScript — Hot topic for Interview

Wikipedia definition of Memoization is

In computing, memoization or memoization is an optimisation technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

In simple words, rather executing a code snippet repeatedly to perform a particular task, we can save the results of previous computation and use it later to avoid unnecessary computation.

Let’s start with a simple example, let’s create a function named add that adds number 10 to parameter that is passed as an argument.

const addTen = function(num){
return num + 10;
}
console.log(addTen(20)) //Output of this would be 30

Say you call the same function with same argument for 3 times, like snippet below.

const addTen = function(num){
return num + 10;
}

Observe the pattern here, every-time, same argument is being passed and same process is carried out inside the addTen function, in this scenario computing the same code again and again is of no use. Rather, we can save the result of the computation and if the parameter that is passed is already known to the snippet then rather freshly computing saved result can be returned as shown below.

let cache = {};
const addTen = function(num){
if(num in cache){
console.log("Inside Memoization block")
return cache[num]
}else{
console.log("Inside Regular execution block")
cache[num] = num + 10;
return cache[num]
}
}
console.log(addTen(20))
console.log(addTen(20))

Output of above snippet would be

Inside Regular execution block
30
Inside Memoization block
30

As you might have guessed, first time the addition has happened and further on memoization block is executed. This saves complex computation by saving the results. In interview if the question asked like what is memoization explain with a snippet ? Then write the above code, it is simple and easy to explain, you can even spice it with closures and inner functions if your aware of the concept.

Some interviews will be tricky they would ask quite complicated question, like below.

  1. Can you write memoization function for calculating Fibonacci series ?
  2. Can you write memoization function for finding Factorial of a number?

Let’s answer the questions below,

Finding Fibonacci of a number using memoization

For those of you who don’t know what is Fibonacci series, It is a series of numbers where a number is the addition of the last two numbers, starting with 0, and 1. Ex of sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Fibonacci of 2 is = 1 + 1 = 2 // fibonacci(1) + fibonacci(0)

First let’s see the usual recursive approach to calculate the Fibonacci series.

function fibonacci(num) { 
if (num <= 1) return 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}

The code looks very simple in above approach, we recursively iterate the function until the base case, I,E till value is 0 or 1. Problem with plain recursion is, same values are calculated repeatedly which will increase the computations that will happen inside the function. Rather computing the value every-time we can use the memoization function, as shown below

function fibonacci(num, cache) {
cache = cache || {};

In this line

if (cache[num]) return cache[num];

We are checking if the fibonacci of a value is already calculated, if it is already calculated we will not be re-calculating it, rather we just use that value. This would improve the time complexity of algorithm from 0(2^n) in previous approach to 0(2N) in this approach.

I will leave the approach to find Factorial of number using Memoization to readers. Happy coding !!

Related articles by same author

  1. Prototype and Protypal Inheritance in JavaScript
  2. How everything is Object in JavaScript ?
  3. Event Bubbling and Trickling/Capturing in JavaScript — Common interview question

Read more here.

React Native developer with JavaScript fan. Overall 5 years of Software Experience. Coffee lover, likes travelling and writing.