A strong answer
Treat each file as a sequence of lines. The lines that stay the same form a common subsequence, and the smallest diff keeps as many lines as possible: it is a longest common subsequence of the two line sequences. Every line not in the LCS is shown as deleted (from the old file) or inserted (into the new one). Equivalently, diff computes a shortest edit script of insertions and deletions.
The textbook method fills a table where dp[i][j] is the LCS of the first i lines of one file and the first j of the other: on equal lines, take the diagonal plus one; otherwise, the larger of the cell above and the cell to the left. Walking back from the bottom-right cell recovers which lines matched, and the rest are the edits. That costs O(m × n) time and space, too much for large files.
Real tools are smarter. Git's default, Myers' algorithm, searches for the shortest edit script by increasing number of edits D, in O((m + n) × D) time, which is fast when the files are similar, the common case. Its linear-space version finds the middle of the optimal edit path and recurses on both halves, the same idea as Hirschberg's algorithm, so memory stays O(m + n). Tools also hash lines first so comparisons are cheap, and trim common prefixes and suffixes. Alternatives such as patience diff and histogram diff anchor on lines that occur only once, which tends to produce diffs that are easier for humans to read than ones that match blank lines or braces.
What the interviewer is listening for
- The reduction from diff to LCS or shortest edit script.
- The table, its cost, and how reconstruction produces the edits.
- At least one technique real tools use to scale.
Common mistakes
- Comparing files character by character by default.
- Forgetting that the table alone gives the size of the diff, not the diff.
- Assuming the O(m × n) table is what Git runs.