After filling an LCS table for two deployment config files, how do you walk it back to emit the diff?
answer
- the numbers already record every choice
- start at the bottom-right corner
- equal lines step diagonally
- up versus left is removed versus added
- the output arrives backwards
basics
~20 sStart at the bottom-right cell and walk to the origin. Equal lines mean a diagonal step and an unchanged line; otherwise move toward the larger neighbour — up emits a removal, left an addition. The walk is O(m+n) and its output arrives reversed.
solid answer
~50 sThe filled table already encodes every choice, so no extra back-pointer array is needed. Set `i = m`, `j = n` and loop while both are positive: if the two current lines are equal, that line is context — step diagonally and emit it unchanged; otherwise compare `dp[i-1][j]` against `dp[i][j-1]` and move toward the larger, emitting a removal when you go up and an addition when you go left. When one index hits zero, drain the other: everything left in the first file is removed, everything left in the second is added. Each step decrements `i` or `j` or both, so the walk is `O(m+n)` over the already-computed table. Two things surprise people: the lines come out in reverse and must be flipped before printing, and a tie between the two neighbours means several equally optimal diffs exist — the tie-break is what makes one tool's output look different from another's on the same files.
code
pseudocode · 12 linesi = m; j = n
while i > 0 and j > 0:
if A[i-1] == B[j-1]:
emit(" ", A[i-1]); i = i - 1; j = j - 1 # unchanged
else if dp[i-1][j] >= dp[i][j-1]:
emit("- ", A[i-1]); i = i - 1 # removed
else:
emit("+ ", B[j-1]); j = j - 1 # added
while i > 0: emit("- ", A[i-1]); i = i - 1
while j > 0: emit("+ ", B[j-1]); j = j - 1
...
reverse the emitted lines before printinggo deeper
Know that the last cell holds only a number and that the actual matched lines come from walking backwards. Be able to state the three moves — diagonal, up, left — and what each one means for the output.
Trace the walk out loud on a small pair of files, including the two drain loops and the reversal at the end. Explain why the stored values are enough and no back-pointer array is needed.
Show you have shipped this: name the orientation so removals and additions cannot be swapped, handle the drains, and explain that ties produce several equally minimal diffs, which is why readability heuristics sit on top of the alignment.
Own the decision of what a unit of comparison is — lines, fingerprinted lines, or semantic blocks — and how much post-processing readability is worth, since minimal and useful are not the same output and reviewers only ever see the second.
## The value is not the deliverable A diff tool does not want the number 47. It wants the actual list: these lines are unchanged, this block was removed from the old config, this block was added in the new one. The table gives you the number in its last cell; the *alignment* is recovered by walking backwards through the cells that produced it. ## Why the values alone suffice A common instinct is to store a parent pointer in every cell during the fill. You do not need one. Standing in cell `(i,j)` you can recompute which move was taken by looking at the same information the fill loop looked at: - If the two current lines are equal, the fill took the diagonal and added one. That line is part of the common subsequence — in diff terms, a context line present in both files. - If they are not equal, the fill took the larger of the up and left neighbours. Move toward whichever is larger. Dropping the pointer array halves the memory the reconstruction needs and removes a whole class of bugs where pointers and values disagree. ## Reading the moves as diff operations Orient the table so the old file indexes rows and the new file indexes columns. Then: | Move from (i,j) | Diff line | |---|---| | diagonal to `(i-1, j-1)` | unchanged line, present in both | | up to `(i-1, j)` | line `A[i-1]` removed from the old file | | left to `(i, j-1)` | line `B[j-1]` added in the new file | Getting this mapping backwards produces a diff that is internally consistent and completely wrong — additions labelled as removals — and it will pass a length-based test, so name the orientation explicitly when you describe your walk. ## The two boundary cases The loop must handle running off an edge. When `i` reaches 0 there is nothing left in the old file, so every remaining line of the new file is an addition; when `j` reaches 0, every remaining line of the old file is a removal. Forgetting the two drain loops silently truncates the diff at exactly the point where one file has a block appended at the front — a very common shape for config files that gain a new header. ## The output is reversed The walk starts at the end of both files and works toward the start, so lines are produced in reverse order. Either collect and reverse at the end, or push onto a stack-like buffer and drain it. Printing as you go is a classic bug that looks fine on a symmetric test input and scrambles on a real one. ## Ties, and why two tools disagree When `dp[i-1][j] == dp[i][j-1]`, both moves lead to an optimal alignment of the same length; they simply group the changes differently. The subsequence is *a* longest one, not *the* longest one. This is why two diffs of the same pair of files can both be minimal and yet look different — one shows a removed block followed by an added block, the other interleaves them. Production diff tools spend real effort on this: after finding a minimal alignment they apply heuristics that slide changes to more human-readable boundaries, preferring to break at blank lines or at lines with less indentation, so a changed block in a nested configuration section is reported against the section header rather than against a stray closing brace. The alignment is the algorithm; the readability is a post-pass. ## Cost The fill is `O(m*n)` time. The walk itself is `O(m+n)`, since each step decreases `i`, `j`, or both, and it does no arithmetic beyond a comparison per step. Note that for a line-oriented diff, `m` and `n` are line counts, not character counts, and lines are usually compared by a precomputed fixed-size fingerprint so that each cell's comparison is constant time rather than proportional to line length. ## What a good answer sounds like "Start bottom-right. Equal lines: diagonal, emit as context. Otherwise move toward the larger of up and left — up is a removal from the old file, left is an addition in the new. Drain whichever index is left when the other hits zero. Reverse the output. It's `O(m+n)` over the table I already have, and ties mean several equally minimal diffs exist, which is why tools add readability heuristics on top."
- Do you need a separate back-pointer table during the fill?No. Standing in a cell you can recompute the move: equal lines mean the diagonal was taken, otherwise the fill took the larger of the up and left neighbours, and you move that way. A pointer array doubles the memory and adds a way for pointers and values to disagree. Its only real advantage is when comparing two lines is itself expensive.
- Two tools produce different but equally short diffs of the same files. How?Ties. When the up and left neighbours hold the same value, both moves lead to an alignment of the same optimal length; they only group the removals and additions differently. The tie-break is a free choice, and real tools go further, sliding change blocks to more readable boundaries after the minimal alignment is found.
- What is the running time of the reconstruction itself?O(m+n). Every iteration decrements i, j, or both, so the walk visits at most m+n cells regardless of how large the table is, and does one comparison per step. The quadratic cost lives entirely in the fill; reconstruction is cheap once the table exists.
The filled table is a hillside of costs already surveyed; reconstruction is walking downhill from the far corner, reading the signposts you already planted rather than surveying again.
saying these in an interview costs you the question
- Insists a parent-pointer array is required to reconstruct
- Claims reconstruction costs another O(m*n) pass
- Prints lines as they are emitted, without reversing
- Forgets the drain loops when one index reaches zero
- Assumes the longest common subsequence is unique