Bloomberg LP Interview Question
Financial Software Developersfor each element of an array A, perform a binary search for that element on the other array B. this takes O(lg n) for each element of A, so it takes a total of n*O(lg n) time
If one array is size n, and the other m, then we can do it in either O(n log m) or O(m log n), depending on which array you choose to do the binary search in.
if m is much larger than n, then O(n log m) would be preferable, So you pick the array with lesser elements and go through each of that and do a binary search on the larger array.
The arrays are not sorted as given. So you need to consider in the nlogn and mlogm sorting cost first.
If the arrays are sorted, then an aligned sweep of both arrays will suffice. Complexity is O(n+m).
You are right. I forgot to add the sorting cost.
It is O( (n+m) log n) or O ( (n+m) log m) depending on the array you choose to sort.
So it seems like sorting the smaller array is better.
And, if both arrays are sorted...
Using a aligned sweep O(n+m) need not be better. Doing a binary search on the larger array might be better, depending on n and m.
Ok...this probably is a dumb question...but what does an "aligned sweep" mean here? :-S
By aligned sweep I meant the following:
You have index a into array A and index b into array B.
(Assume A and B are sorted ascending starting with least at 0).
Initially a = b = 0.
Now you compare A[a] with B[b]
if both are equal, add A[a] (or B[b]) to list of common elements and increment a and increment b.
if A[a] < B[b] increment a.
if A[a] > B[b] increment b.
This is what I meant by "aligned sweep"...
Suppose size of smaller array is n and size of larger array is m.
If we sort the smaller array first(nlogn) and then (Binary)search for each element in the larger array(Ologn) one by one(Total m elements) in this sorted array then it can be achieved in nlogn+mlogn=m+n(logn)
But what happens if each array have some duplicate elements itself contained inside it????Can someone suggest further or any other good logic???
For finding the intersection of the two arrays we will need the concept of hashing and at first, we will insert the array elements of the largest array and then, we will check the elements which are present in the hashset if yes then, they are the array elements which are common to both the arrays.
U can use merge sort... makes sense? and identify the duplicates while merging.... so total time will be O(nlogn)
Use hashing.
- amit April 07, 2009