Amazon Interview Question
Software Engineer in Testssorry dude - all sols seem to be wrong. My sol is below:
Given array A of n integers (or reals), find below
median = n/2;
m = select median.
a = select element n/2-k;
b = select element n/2+k;
m, a & b can be done in O(n) time using Selection algo given in Cormen book.
Now, define the array B of 2k integers (exclude the median in array B), such that all values in B are in range [a,b].
Then, do
for(int i = 0; i < 2 * k; i++)
B[i] = B[i] - m;
Now, find c = the kth smallest absolute value in array B (using a version of selection sort that considers absolute value of negative number while doing comparison).
Then, scan array B and find all numbers whose absolute value <= c and put that in array C.
for (i = 0; i < k; i++)
C[i] += m;
output array C as result.
Find the two boundary elements (a and b) with SELECTION algorithm. Then scan the array again to find elements e satisfying a<= e <=b.
This is linear time.
Finding just the two boundary elements doesn't work when n is odd and k is even or n is even and k is odd. This is because you have to decide which boundy element doesn't belong in the group. one of the boundy elements will be father away from the median than the other. So to decide this you also need to use the selection algorithm to find the median itself. If n is even it depends on how you define median you may need to select 2 elements instead of just the median.
what is mean of "closest to the median of S", the cloest means the distance or the value?
assume the closest means distance. First get median value m in O(n) time by using select algorithm (we may need a copy of S). Then, search the position p of m in S (since all elements are distinct). The cloest number is from p-k/2 to p+k/2.
Given : unsorted Array [1...n]
m= n/2 if n even , n/2 +1 if n odd .
a= m-k/2 if m even , m - k/2 if m odd
b= m+ k/2 if m even , m + k/2 + 1 if m odd
Variation in Quick Sort, We will pick two pivot element.
Then,We will partition the array till we get desired a and b
After partition there would be three unsorted subarray.
Depending on the indices of pivot elements, perform a recursive call.
Scenarios
1. pA and pB are outside the desired boundary.
Call.. Array[pA+1..pB-1] m-=pA+1,
2. pA & pB are inside the desired boundary
Call.. Array[low..pA-1] with k= pA-a,
Array[pA..high] with k= b-pA
append the result with Array[pA..pB]
3. pA is inside, pB outside
Call.. Array [low...pB-1]
4. pA is outside, pB inside
Call.. Array [pA+1...high] m-=pA+1
5. pA =a & pB=b , return Array[pA..pB]
In step 2 , We can use Find nth Smallest/Largest program as well.
Please comment/rectify.
median = n/2;
- Rohith Menon October 29, 2008m = quick_select median.
a = quick_select element n/2-k;
b = quick_select element n/2+k;
Now do quick_select element k from a to b. During this step partition the elements between a to b not based on the number, but based on the distance from median.
Eg:-
select a random number r from the array between a and b.
find the distance d1 = abs(r-m);
now partition the array based on whether d = (arr[i]-m) < d1 or >= d1 , i from position of a to position of b.
Using this partition, you can quick_select the kth closest element from the median.
Total time_complexity :-
O(n). (4 quick selects)
refer http://en.wikipedia.org/wiki/Selection_algorithm for quick select algorithm.
Comments/criticisms welcome.
Thanks,
Rohith Menon.