## Problem Implement a line-level diff tool similar to Unix `diff`. Given two lists of strings (lines of text), compute the minimal edit script (insertions and deletions) to transform one into the other. Output in unified diff format. ```python def compute_diff( original: list[str], modified: list[str] ) -> list[str]: # unified diff lines pass ``` ## Example ``` original = ["foo", "bar", "baz"] modified = ["foo", "qux", "baz"] compute_diff(original, modified) # Output: # @@ -1,3 +1,3 @@ # foo # -bar # +qux # baz ``` ## Follow-ups 1. What algorithm computes the minimum edit distance efficiently? What is its time and space complexity? 2. How does the Myers diff algorithm improve on naive LCS-based approaches? 3. How would you extend this to word-level or character-level diffs within changed lines? 4. How do you handle files with thousands of lines efficiently — can you avoid an O(n^2) DP table?

InterviewDB Question

String Diff: Compute and Display Line-Level Diffs Between Two Text Files

phone

Question Details

Problem Implement a line-level diff tool similar to Unix diff. Given two lists of strings (lines of text), compute the minimal edit script (insertions and deletions) to transform one into the other. Output in unified diff format. Example Follow-ups What algorithm computes the minimum edit distance efficiently? What is its time and space complexity? How does the Myers diff algorithm improve on naive LCS-based approaches? How would you extend this to word-level or character-level diffs within chan…

Full Details

🔒

Unlock all Jane Street questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a jane street interview during the phone round.

It covers the following topics: Strings, Dynamic Programming, Phone, Coding, Onsite .

Topics

Strings Dynamic Programming Phone Coding Onsite

String Diff: Compute and Display Line-Level Diffs Between Two Text Files

Question Details

Full Details

About This Question

Topics

More Jane Street Interview Questions