Amazon Interview Question
Software Engineer / Developerssort the smaller array. now binary search for each element of larger array in the smaller array. complexity=O(mlgm+nlgm). mlgm to sort and nlgm to check if each element of larger array exists in smaller array . doing other way round leads to complexity of O((m+n)lgn). so first way is better.
2nlogn + 2n-1
- Anonymous July 21, 2011