Recursion and Memoization Interview Patterns
Memoization transforms exponential recursive solutions into polynomial ones by caching subproblem results. In Python, @lru_cache makes memoization trivial. This guide covers the patterns for recognizing when memoization applies and the most important problems.
When Memoization Applies
Memoization works when a problem has:
- Overlapping subproblems: the same subproblem is computed multiple times in a naive recursion
- Optimal substructure: the optimal solution to a problem can be constructed from optimal solutions to subproblems
Signs you should memoize: the recursive tree has exponential branching (2^n calls) but only polynomial distinct states (n^2 distinct (i, j) pairs).
Python Memoization with lru_cache
from functools import lru_cache
@lru_cache(maxsize=None) # unlimited cache
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# Without cache: O(2^n) calls. With cache: O(n) unique calls.For problems with mutable arguments (lists, dicts), convert to tuples before passing to cached functions.
Coin Change (LeetCode 322)
def coin_change(coins, amount):
@lru_cache(maxsize=None)
def dp(remaining):
if remaining < 0: return float('inf')
if remaining == 0: return 0
return 1 + min(dp(remaining - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
# State: remaining amount (0 to amount)
# Transitions: try each coin denomination
# Time: O(amount * len(coins)), Space: O(amount)Longest Common Subsequence (LeetCode 1143)
def lcs(s1, s2):
@lru_cache(maxsize=None)
def dp(i, j):
if i == len(s1) or j == len(s2): return 0
if s1[i] == s2[j]:
return 1 + dp(i+1, j+1)
return max(dp(i+1, j), dp(i, j+1))
return dp(0, 0)
# State: (i, j) = position in s1 and s2
# O(m*n) states, O(1) per state = O(m*n) totalWord Break (LeetCode 139)
def word_break(s, wordDict):
words = set(wordDict)
@lru_cache(maxsize=None)
def dp(start):
if start == len(s): return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in words and dp(end):
return True
return False
return dp(0)
# State: start index (0 to n)
# Try all prefixes from start — O(n^2) states * O(n) string check = O(n^3)Regular Expression Matching (LeetCode 10)
def is_match(s, p):
@lru_cache(maxsize=None)
def dp(i, j):
if j == len(p): return i == len(s)
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
if j + 1 < len(p) and p[j+1] == '*':
# either skip "x*" entirely, or use it (if first char matches)
return dp(i, j+2) or (first_match and dp(i+1, j))
return first_match and dp(i+1, j+1)
return dp(0, 0)
# State: (i, j) = position in s and p
# O(m*n) statesEdit Distance (LeetCode 72)
def min_distance(word1, word2):
@lru_cache(maxsize=None)
def dp(i, j):
if i == 0: return j # insert all remaining chars of word2
if j == 0: return i # delete all remaining chars of word1
if word1[i-1] == word2[j-1]:
return dp(i-1, j-1) # no operation needed
return 1 + min(
dp(i-1, j), # delete from word1
dp(i, j-1), # insert into word1
dp(i-1, j-1) # replace
)
return dp(len(word1), len(word2))
# Classic interview problem: Levenshtein distance
# State: (i, j) = first i chars of word1, first j chars of word2Decode Ways (LeetCode 91)
def num_decodings(s):
@lru_cache(maxsize=None)
def dp(i):
if i == len(s): return 1 # decoded successfully
if s[i] == '0': return 0 # leading zero — invalid
result = dp(i + 1) # single digit
if i + 1 < len(s) and int(s[i:i+2]) <= 26:
result += dp(i + 2) # two digits
return result
return dp(0)Memoization vs. Bottom-Up DP
| Aspect | Memoization (top-down) | Bottom-up DP |
|---|---|---|
| Order | Automatic (lazy) | Manual (must figure out) |
| Only needed states | Yes (sparse problems) | No (fills all states) |
| Stack overflow risk | Yes (deep recursion) | No |
| Space optimization | Hard (cache stores all) | Easy (rolling array) |
| Interview speed | Faster to write | Requires careful indexing |
Interview Tips
- Use
@lru_cachein Python — it is production-grade and acceptable in interviews - Always state the number of distinct states and time per state to derive total complexity
- For 2D memoization (LCS, edit distance, regex matching), the state is (i, j) — a 2D table
- Convert mutable parameters to tuples for lru_cache:
dp(tuple(coins), amount) - When interviewers ask “can you do it bottom-up?” — convert by filling the dp array in reverse order of the recursion
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the difference between memoization and tabulation in dynamic programming?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Memoization (top-down): implement the recursive solution naturally, add caching (lru_cache or a dict) to avoid recomputing subproblems. The recursion naturally computes only the needed subproblems. Easy to write, risk of stack overflow for deep recursion. Tabulation (bottom-up): fill a DP table iteratively from smallest subproblems to largest. No recursion overhead, easy to optimize space with rolling arrays, but you must manually determine the correct fill order. When to use each: use memoization for irregular recursion trees (word break, regular expression matching) where many subproblems may not be needed. Use tabulation when you need space optimization (coin change with O(amount) space instead of O(amount * coins)), or when recursion depth exceeds Python's default limit (~1000 levels). In interviews, memoization with @lru_cache is faster to write and equally valid.” }
},
{
“@type”: “Question”,
“name”: “How do you approach edit distance (Levenshtein) in a coding interview?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Edit distance is the minimum number of insertions, deletions, or replacements to convert word1 to word2. State: dp(i, j) = min edits to convert word1[:i] to word2[:j]. Base cases: dp(i, 0) = i (delete all of word1), dp(0, j) = j (insert all of word2). Transitions: if word1[i-1] == word2[j-1], no edit needed: dp(i,j) = dp(i-1, j-1). Otherwise, take the minimum of: dp(i-1, j) + 1 (delete from word1), dp(i, j-1) + 1 (insert into word1), dp(i-1, j-1) + 1 (replace). Time O(m*n), space O(m*n) or O(min(m,n)) with rolling array. Variants: if you only allow insertions and deletions (no replacements), edit distance = m + n – 2 * LCS(word1, word2). Mention this connection to LCS – it impresses interviewers.” }
},
{
“@type”: “Question”,
“name”: “How do you solve Word Break with memoization and what is the time complexity?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Word Break: given string s and dictionary of words, can s be segmented into dictionary words? Top-down: dp(start) = can s[start:] be segmented? Base case: dp(len(s)) = True (empty remainder). For each start, try all ends from start+1 to len(s)+1: if s[start:end] is in the word set AND dp(end) is True, then dp(start) = True. Memoize dp with @lru_cache. Time: O(n^2) states (n start positions) * O(n) per state (trying n split points, each requiring O(n) string slice check) = O(n^3). With a Trie instead of string slicing: O(n^2). State space: O(n) unique start positions. This is a good example where memoization outperforms backtracking: without memoization, the naive backtracking re-explores the same suffix many times.” }
}
]
}