Amazon Interview Question Software Engineer in Tests




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.

Comments/criticisms welcome.

Thanks,
Rohith Menon.

- Rohith Menon on October 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- J.W. on March 12, 2009 | Flag
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.

- Gopal Krishna on December 16, 2008 | Flag Reply
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.

- Tao Su on October 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HINT: use a variant of SELECTION ALGORITHM

- Hint Hunter on October 28, 2008 | Flag Reply
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.

- Anonymous on October 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what do you mean by boundary elements.

- jianwei.sun on October 28, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on October 29, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on October 29, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Gud job man

- Aryan on October 29, 2008 | Flag Reply
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.

- Anonymous on October 29, 2008 | Flag Reply
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.


Please comment/rectify.

- YetAnotherCoder on November 06, 2008 | Flag Reply
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.

- KK on May 15, 2009 | Flag Reply
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.

- Anonymous on September 07, 2009 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More