Memoization Interview Pattern: When to Use It and 5 Problems to Practice (2026)

When interviewers ask you to solve a combinatorial or dynamic‑programming problem, they often expect you to recognize that a naïve recursion will recompute the same state many times. Memoization is the technique of caching those results the first time you see a state and reusing them on later calls. In plain words, think of it as "remember‑the‑answer" for each distinct sub‑problem.

Why memoization works: overlapping subproblems

A problem has overlapping subproblems when the recursive tree contains the same input more than once. Classic examples are Fibonacci numbers or grid‑path counting. If each subproblem is solved independently, the total work grows exponentially. By storing the answer the first time you compute it, subsequent visits become O(1) look‑ups, turning exponential time into polynomial.

Signals that a problem wants memoization

If you see any of these, pause and ask yourself: Can I define a state that uniquely captures the subproblem? If yes, memoization is a good candidate.

A worked example: "Climbing Stairs"

Problem: You can take 1 or 2 steps at a time. How many distinct ways are there to reach the top of an n‑step staircase?

A direct recursive solution:

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

For n = 30 this makes more than a million calls. The overlapping subproblems are the same climb(k) for many k. Memoizing eliminates the duplication.

from functools import lru_cache

@lru_cache(maxsize=None)
def climb(n):
    if n <= 1:
        return 1
    return climb(n-1) + climb(n-2)

Now each climb(k) runs once, giving O(n) time and O(n) space (the cache). You could also use an explicit dict:

memo = {}

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

Both versions are interview‑ready; the decorator is shorter, but a dict shows the underlying idea more explicitly.

Complexity analysis

• Time: O(number of distinct states). For the stair problem, there are n+1 states, so O(n).
• Space: O(number of states) for the cache plus recursion depth. In Python, the recursion depth is limited, so you may need to convert to an iterative DP if n can be large.
• Trade‑offs: Memoization can use a lot of memory when the state space is large (e.g., DP on two dimensions with many possible values). In those cases, bottom‑up DP with rolling arrays may be preferable.

Common pitfalls

1. Mutable arguments – Dictionaries or lists as keys are unhashable, causing TypeError with @lru_cache. Use a tuple or convert the mutable structure to an immutable representation.
2. Missing base cases – Forgetting a base case can lead to infinite recursion or wrong answers.
3. Cache bloat – Storing every state when only a subset is needed wastes memory. You can limit maxsize or prune rarely‑used states.
4. Incorrect state definition – If your state does not capture all needed information (e.g., forgetting a "previous character" in a string DP), the cache will return wrong results.
5. Recursion depth limits – Python's default recursion limit (~1000) can be hit for large inputs. Switch to an explicit stack or bottom‑up DP when needed.

Five practice problems

Below are five problems that naturally lead to memoization. They are described in your own words; you should write the recursive relation yourself before adding a cache.

1. Unique Paths in a Grid

Prompt: Given an m × n grid, you start at the top‑left corner and can only move down or right. How many ways can you reach the bottom‑right corner? Hint: Define paths(i, j) as the number of ways to reach cell (i, j). The relation is paths(i, j) = paths(i‑1, j) + paths(i, j‑1).

2. Word Break

Prompt: Given a string s and a dictionary wordDict, determine if s can be segmented into a space‑separated sequence of one or more dictionary words. Hint: Let can_break(i) be true if the suffix starting at index i can be segmented. Then can_break(i) = any(can_break(j) for j>i if s[i:j] in wordDict).

3. Palindrome Partitioning Minimum Cuts

Prompt: Return the fewest cuts needed to partition a string into palindromic substrings. Hint: Use min_cuts(i) for the suffix starting at i. For each j ≥ i where s[i:j] is a palindrome, min_cuts(i) = min(min_cuts(j+1) + 1).

4. Edit Distance (Levenshtein)

Prompt: Compute the minimum number of insert, delete, or replace operations to convert word a into word b. Hint: Define dist(i, j) as the edit distance between the suffixes a[i:] and b[j:]. The recurrence checks the three edit operations.

5. Count of Binary Trees with Given Height

Prompt: How many distinct binary trees with n nodes have height exactly h? Hint: Let count(n, h) be the answer. For each possible left‑subtree size k, combine count(k, h‑1) and count(n‑1‑k, h‑1). Use memoization to avoid recomputing the same (n, h) pair.

Each of these problems exhibits overlapping subproblems; a naïve recursion will explode, while memoization brings the runtime down to polynomial.

How to practice this

1. Write the recursive formula first – before you add any cache, ensure the recurrence is correct and covers all base cases.
2. Add a cache manually – implement a dictionary version, then replace it with @lru_cache to see the syntax difference.
3. Run a timer – compare the naïve recursion against the memoized version on inputs near the constraint limits. Notice the speedup and memory usage; this will help you talk about complexity confidently.

---

If you want to rehearse your explanation aloud, Call Assistant can listen to you and give instant feedback, keeping the conversation on point while you ground your story in real experiences from your resume.