Amazon Interview Question for Software Engineer in Tests

• 2

Comment hidden because of low score. Click to expand.
1
of 0 vote

median = n/2;
m = 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.

Thanks,
Rohith Menon.

Comment hidden because of low score. Click to expand.
0

The question is asking the K numbers , NOT "the kth closest element from the median".

Comment hidden because of low score. Click to expand.
1
of 0 vote

sorry 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Does this problem have an O(n) solution? The best way I can think of is a variant of "finding the k-th smallest (or median) of an array" which is a variant of quick sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

HINT: use a variant of SELECTION ALGORITHM

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

what do you mean by boundary elements.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Good thought. But these are just trivial things, right?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Gud job man

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use median of medians algorithm to get the number closest to the median. Divide the array to blocks of 5,compute median for each block (constant number of comparisions) and insert them to a list. Repeat the procedure on the list.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@KK:
it seems you forget to read the Question properly, to remind you "it says find the k closest numbers to the median" and not just find the closest number to the median.
The algo you mentioned is just the one used for finding median of medians.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.