Memoization | Skilled.dev
Learn

Memoization

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

DO SOME CALCULATION COUNTER? create a count and log it for different nth fibs and then show count with memoized https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/learn/lecture/12409068#overview

GO UP TO FIB(7) AND REMOVE THOSE BOXES TO FIT MORE CALLS?

Memoization (or caching) is an optimization that stores the result from a function call or expensive calculation so that it isn't performed more than once. Like most of our optimizations, we take on more space to lower our time complexity.

Not only do we see memoization, but it is a very common technique used in production to keep our applications running fast.

  • The frontend uses to UI state to prevent it from needing to re-render
  • The backend store expensive calculations in memory
  • We store expensive or frequent database queries in a cache like Redis to make the data immediately accessible

In interviews, we most often refer to memoization when storing the result of recusrive calls. For example, if we recursively compute a Fibonacci number, it requires O(2n) time complexity (ignoring constants).

const fib = (n) => {
  if (n === 0 || n === 1) {
    return 1;
  }

  return fib(n - 1) + fib(n - 2);
}

Let's take a look at what is actually happening if we call fib(5). I've highlighted function calls with the same arguments in similar colors.

Not only do we call the same function many times, but it also triggers additional recursive calls. If we instead store the result of a function call, we can just use the memoized value that was previously calculated instead going deeper into the recursive tree.

We don't have to worry about fib(0) and fib(1) repeats because those are our base cases.

For this problem, we use a hashtable where the key is the result for calcuting a Fibonacci number which corresponds to the argument to the function.

{
  0: 1, // fib(0)
  1: 1, // fib(1)
  2: 2, // fib(2)
  3: 3, // fib(3)
  4: 5, // fib(4)
  5: 8, // fib(5)
  // ... and so on for all the fibonacci numbers
}

Translating this to code, we get the following:

const memo = {};

const fib = (n) => {
  if (n === 0 || n === 1) {
    return 1;
  }

  // If we have the value in our hash table,
  // return it instead of continuing with the recursive case
  if (memo[n]) {
    return memo[n];
  }

  const nthFib = fib(n - 1) + fib(n - 2);

  memo[n] = nthFib;

  return nthFib;
}

Now let's view our tree of recursive calls again. I'll gray out the function calls that no longer run or are base cases. I've highlighted the border in yellow for the function calls that utilize a memoized value.

By using memoization, we improve our runtime from O(2n) to O(n)

Prev
Subproblems and Overlapping Subproblems
Next
Bottom-Up vs Top-Down

Table of Contents