Memoization Interview Questions & Tips

By Githire B. Wahome | Last updated: July 13, 2023

What Is Memoization?

Memoization is a programming technique used to speed up the execution time of a function by caching its results. Oftentimes, the term is confused with ‘memorization’. Conceptually, they allude to the same idea, except that memoization entails caching the results of a function while memorization entails committing data of any type to memory. That said, it is fair to think of memoization as a type of memorization.

When a function is called with a set of parameters, the result is stored in a cache with the input parameters being keys to the result values. The next time the function is called with the same parameters, instead of recomputing the result, it is retrieved from the cache. This can result in significant performance gains, especially for functions that are called repeatedly with the same inputs.

Companies That Ask Memoization Questions

Google

Meta

Netflix

When to Use Memoization in Interviews

If dynamic programming is the Yin, Memoization is the Yang. These two go hand in hand. Dynamic programming problems are characterized by the existence of optimal substructure and overlapping subproblems.

1. Optimal Substructure: Dynamic programming problems have optimal substructure, which means that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.
2. Overlapping Subproblems: Dynamic programming problems also have overlapping subproblems, which means that the same subproblems are often solved multiple times.

Any time a problem satisfies the above criteria, it becomes a candidate for memoization. We will center around the good old Fibonacci problem in this article to demonstrate this.

Fibonacci Problem

The Fibonacci problem is a mathematical sequence where each number is the sum of the two preceding ones, starting from 0 and 1. The sequence goes as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on.

Below is a short script showing how we can compute any Fibonacci number recursively.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Common Mistakes in Interviews Featuring Memoization

Failure to Identify Sub-problems

Memoization works best when the function being memoized has repeated calls with the same input values. However, problems that involve random or non-deterministic computations may not be good candidates for memoization.

Failing to Flesh Out the Naive Solution

Understanding how the naive solution would work is key to drawing the call tree.

Improper Key Selection

The memo is usually an object like a hash table. When selecting the keys, a simple heuristic is to select all the NON-STATIC parameters of the function call.

memo = {0:0, 1:1}

def fibonacci(n):
    if n not in memo:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

Unnecessary Memoization

Depending on the problem, a memoized value may only need to be accessed once or a few times.

Failure to Make State Updates

This step involves defining and manipulating the return values of recursive calls.

fib(n) = fib(n-2) + fib(n-1) # State transition for top-down approach
first, second = second, first + second # State transition for bottom up approach

What to Say in Interviews to Show Mastery Over Memoization

Clearly Identifying the Optimal Substructure and Overlapping Subproblem

In an interview, make sure you talk about how the problem exhibits these two properties.

Justifying the “Key” Selection to Your Memo

When selecting this key, your primary goal is to ensure it remains unique for each function call.

Clearly Defining the Carried-Over State During State Transition

Take a few seconds to talk about what you are computing and how it will carry on as input to the next set of operations.

Discussing Trade-Offs Between Top-Down and Bottom-Up Solutions

One of the key trade-offs to be mindful of is just how much you actually need to memoize.

Following a Step-By-Step Framework When Finding the Solution

Frameworks such as FAST have been proposed to help capture the general steps followed when solving dynamic programming problems.

Common Memoization Interview Questions

Medium

Employee Hierarchy
Given an array of employee IDs including who they report to, write a function to calculate the score for a given employee.

Hard

Longest Increasing Path in a Matrix
Given an m x n integers matrix, return the length of the longest increasing path in the matrix. You may only move up, down, left, or right.

Adjacent Topics to Memoization

• Dynamic Programming
• Hash Tables
• Recursion

About the Author

Githire B. Wahome
Githire (Brian) Wahome is a backend and machine learning engineer with almost a decade of experience across startups and large technology companies. He’s worked at Meta, Microsoft, and Qualtrics.