Hi Vijay, I realized that this is a version of the classic problem known as "element uniqueness" (this problem is about finding the duplicate elements in an unsorted array - we could consider the two arrays as one large concatenated array)
There seems to be a proof that the lower bound for the "element uniqueness" problem is o(n lg n) http://compgeom.cs.uiuc.edu/~jeffe/pubs/extlower.html So I guess there is no possible o(n) solution as of now. [i.e until someone finds a better one :)]
