← All Problems

9. Minimum Edits to Repair a Malformed Tool Call

General Hard Anthropic-Style Coding Rounds
Grounding: General pattern common across ML-research-lab technical interviews, not tied to one specific reported example. Edit distance (Levenshtein) is a widely cited classic dynamic-programming category across general software engineering interview prep sources; no source in this batch's research names a specific reported instance of this exact question at Anthropic.

Problem

A model occasionally emits a tool name that's close to, but not exactly, one the runtime recognizes — a typo, a missing character, a transposed pair.

Rather than reject the call outright, the runtime wants to find how many single-character edits (insertions, deletions, substitutions) it would take to turn the emitted tool name into a known valid one, so it can offer the closest match instead of failing the call.

Source: src/9_min_edits_repair_tool_call.py

def min_edit_distance(source: str, target: str) -> int:
    ...

Examples:
>>> min_edit_distance("serch_web", "search_web")
1

>>> min_edit_distance("kitten", "sitting")
3

Step-by-Step Approach

  1. Recognize this as classic Levenshtein edit distance between two strings.
  2. Build a DP table dp[i][j] = edit distance between source[:i] and target[:j], sized (n+1) x (m+1).
  3. Initialize the base cases: dp[i][0] = i (delete all of source[:i]) and dp[0][j] = j (insert all of target[:j]).
  4. Fill the table row by row: if source[i-1] == target[j-1], no edit is needed at this position, so dp[i][j] = dp[i-1][j-1]; otherwise take 1 plus the minimum of the delete/insert/substitute neighbors (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
  5. Return dp[n][m], the distance between the full source and full target strings.

The key insight is that every edit operation corresponds to a specific move through the table (delete = move down, insert = move right, substitute = move diagonally), so the three-way min at each cell is really just asking "which single edit gets me here cheapest."

Reference solution

def min_edit_distance(source: str, target: str) -> int:
    n, m = len(source), len(target)
    # dp[i][j] = edit distance between source[:i] and target[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i  # delete all of source[:i]
    for j in range(m + 1):
        dp[0][j] = j  # insert all of target[:j]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if source[i - 1] == target[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # chars match, no edit needed
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete source[i-1]
                    dp[i][j - 1],      # insert target[j-1]
                    dp[i - 1][j - 1],  # substitute source[i-1] -> target[j-1]
                )
    return dp[n][m]

Key Functions & Tricks

  • dp[i][0] = i / dp[0][j] = j — base cases: transforming to/from an empty string costs exactly the string's length
  • dp[i][j] = dp[i-1][j-1] — matching characters carry the diagonal cost forward with no penalty
  • 1 + min(delete, insert, substitute) — the three-way recurrence covering every possible single edit at this position
  • (n+1) x (m+1) table — sized to include the empty-prefix base cases at row/column 0

How to Recognize This Pattern

The signal is "minimum number of insert/delete/substitute operations to turn one sequence into another" — distinct from LCS (which only allows deletions from both sides, no substitution) and from longest-common-substring (which requires contiguity). The 2D DP table with the three-way min recurrence is the standard, always-correct approach. Common variations assign different costs to insert/delete/substitute instead of uniform cost 1, restrict the allowed operations (e.g. no substitution, only insert/delete — which reduces to an LCS-based formula), or ask only for the DP table's final value without reconstructing the actual edit sequence. A common pitfall is off-by-one errors in the base-case initialization (dp[i][0] and dp[0][j]), which silently corrupts every value that depends on them since the recurrence builds outward from those edges.

← Previous Next →