Compute a Diff Between Two File Versions

Updated · By

A minimal diff keeps as many lines as possible, and the kept lines are a longest common subsequence of both files. Fill a table where lcs[i][j] is the LCS of the suffixes at line i and line j, then walk from the top: keep equal lines, otherwise delete or insert toward the larger value. O(n × m) time and space.

hardPattern: 2-D dynamic programmingFrom Devana's GitHub question set

Problem

A code review tool shows what changed between two versions of a file, line by line. The diff should be minimal, with as few deleted and inserted lines as possible, and readable.

Write diff(old, new), where both are lists of lines. Return a list of operations, each {"op": "keep" | "delete" | "insert", "line": str}, that turns old into new when applied in order.

def diff(old: list[str], new: list[str]) -> list[dict]:

This is one of Devana's own questions, written in the style of GitHub's interviews. It is not a question leaked from GitHub, and Devana is not affiliated with GitHub.

Constraints

  • The number of deletes plus inserts must be the minimum possible.
  • Lines are compared exactly, whitespace included.
  • When several minimal diffs exist, keep matching lines as early as possible, and at each change list deletions before insertions.
  • Files have up to a few thousand lines in this version; the follow-ups cover very large files.

Examples

Example 1

Input:  old = ["a", "b", "c", "d"], new = ["a", "c", "d"]
Output: keep a, delete b, keep c, keep d

Removing one line is the smallest possible change.

Example 2

Input:  old = ["a", "b"], new = ["b", "a"]
Output: delete a, keep b, insert a

Only one line can be kept, so the swap costs one delete and one insert. A diff that kept nothing would cost four operations.

Hints

Open one at a time, and try the problem again after each.

Hint 1

If you keep k lines, how many deletes and inserts do you need? Which k do you want?

Hint 2

The kept lines, in order, form a subsequence of both files. You want the longest one.

Hint 3

Define lcs[i][j] for the suffixes old[i:] and new[j:]. What is it when old[i] == new[j]? When they differ?

Hint 4

Fill the table from the bottom-right corner, then walk it from the top-left so the operations come out in order.

Approach: from brute force to optimal

Brute force: try every subsequence

Enumerate subsequences of the old file, longest first, and test whether each appears in order in the new one. Exponential.

Complexity: O(2^n × m)

A longest common subsequence table

Keeping k lines costs (n - k) deletes and (m - k) inserts, so a minimal diff is one that keeps a longest common subsequence. The recurrence: lcs[i][j] = lcs[i+1][j+1] + 1 when the lines match, otherwise max(lcs[i+1][j], lcs[i][j+1]).

Walking from (0, 0): keep on a match; otherwise move toward the larger neighbor, deleting from the old file when that is at least as good as inserting from the new one.

Complexity: O(n × m) time and space

What real diff tools add

Myers' algorithm finds a minimal diff in O((n + m) × D) time for D differences, which is fast when files are similar, as they usually are. Tools also strip the common prefix and suffix before diffing, and Git offers the patience and histogram algorithms, which match lines that appear once in each file first, for more readable output.

How to say it in the interview

Make the reduction explicit: "a minimal diff is everything outside a longest common subsequence." Then give the recurrence, the table and the walk. Raise the O(n × m) memory problem yourself and say how real tools avoid it; that is where the follow-ups go.

Solution

Python

def diff(old, new):
    n, m = len(old), len(new)
    # lcs[i][j]: longest common subsequence of old[i:] and new[j:].
    lcs = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if old[i] == new[j]:
                lcs[i][j] = lcs[i + 1][j + 1] + 1
            else:
                lcs[i][j] = max(lcs[i + 1][j], lcs[i][j + 1])

    ops, i, j = [], 0, 0
    while i < n or j < m:
        if i < n and j < m and old[i] == new[j]:
            ops.append({"op": "keep", "line": old[i]})
            i, j = i + 1, j + 1
        elif j == m or (i < n and lcs[i + 1][j] >= lcs[i][j + 1]):
            ops.append({"op": "delete", "line": old[i]})   # deletions first on a tie
            i += 1
        else:
            ops.append({"op": "insert", "line": new[j]})
            j += 1
    return ops

JavaScript

function diff(oldLines, newLines) {
  const n = oldLines.length;
  const m = newLines.length;
  // lcs[i][j]: longest common subsequence of oldLines[i:] and newLines[j:].
  const lcs = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = m - 1; j >= 0; j--) {
      lcs[i][j] = oldLines[i] === newLines[j]
        ? lcs[i + 1][j + 1] + 1
        : Math.max(lcs[i + 1][j], lcs[i][j + 1]);
    }
  }

  const ops = [];
  let i = 0, j = 0;
  while (i < n || j < m) {
    if (i < n && j < m && oldLines[i] === newLines[j]) {
      ops.push({ op: "keep", line: oldLines[i] });
      i++;
      j++;
    } else if (j === m || (i < n && lcs[i + 1][j] >= lcs[i][j + 1])) {
      ops.push({ op: "delete", line: oldLines[i] }); // deletions first on a tie
      i++;
    } else {
      ops.push({ op: "insert", line: newLines[j] });
      j++;
    }
  }
  return ops;
}

Both versions are tested against the same cases, including every example on this page.

  • Keeping a matching pair is always safe: when old[i] == new[j], some longest common subsequence uses that pair.
  • The table has (n + 1) × (m + 1) cells, so two 10,000-line files need 100 million of them. That is the cost the follow-ups ask about.
  • >= in the walk is the tie-break that lists deletions before insertions.

Follow-up questions

What is the complexity of the standard algorithm, and where does it hurt?

O(n × m) time and memory, and memory runs out first. Hirschberg's algorithm computes the same alignment in linear space by divide and conquer, and Myers' algorithm is fast when the files are similar.

Why is the minimal diff sometimes the least readable one?

Minimal counts lines, not meaning. Lines such as a closing brace or a blank line match all over a file, so a minimal diff can stitch a change together from unrelated braces. Matching lines that are unique in both files first, as patience diff does, follows the code's structure.

How would you detect a moved block rather than a delete plus an add?

After diffing, hash each deleted block and each inserted block. A deleted block whose hash matches an inserted one is a move, and can be shown as one, with fuzzy matching if it was edited during the move.

How do you handle a generated file with one enormous line?

A line diff sees one changed line. Fall back to a word or character diff within it, with a size cap, or show the file as changed without a diff.

Common mistakes

  • Comparing line by line at the same position, which marks every line after an insertion as changed.
  • Defining the table on prefixes and then walking it from the start. Prefix tables are walked from the end, with the output reversed; suffix tables, as here, are walked from the start.
  • Allocating the full table for very large files.
  • Treating minimal as the only goal and ignoring readability.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview