title: How to find differences between 2 almost-identical files very fast?
body: <p>If you have two mainly identical files with 1000s of records, how will you write code to find differences between them. Assume that unix/linux commands are not allowed to be used. </p>
  
  <p>My idea: </p>
  
  <p>Because most of entries are the same, we can sort the entries of the two files, then compare each entry one by one, e.g. entry i in file1 compare to entry i in file2. It is O(n lg n), n is size of file.</p>
  
  <p>Are there O(n) solution ? </p>