The Longest Common Subsequence, SVN and media files
by Abhijeet Kashnia
Here's a sample question from one of my friend's phone interview with a major technical online giant ( if you browse the internet, then you've heard their name)
You've got a fairly big audio file (why audio?), and somebody takes a copy of that file, and makes a small change in that file. (I guess you can always open a media file with a text editor.) So, how do you detect exactly what changes were made between the original and the new modified copy of that file?
One year later as I started using subversion(SVN), the repository for our source code, I saw a feature called diff, which can let you compare the checked-in version of your source with your working copy.
Wondering how SVN did this, I came across the Longest common subsequence algorithm.
A standard dynamic programming approach is used to implement this algorithm, which also has applications in genetics.