Recursion and Memoization Interview Patterns: LCS, Edit Distance, Word Break

By /

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:

  1. Overlapping subproblems: the same subproblem is computed multiple times in a naive recursion
  2. 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) total

Word 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) states

Edit 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 word2

Decode 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_cache in 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

  • Uber Interview Guide
  • Snap Interview Guide
  • Atlassian Interview Guide
  • LinkedIn Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • Asked at: Coinbase Interview Guide

    Scroll to Top