Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Is it not a merge sort, where we are given N sorted arrays and need to find the median of N arrays compbined?
Just run the merge sort algo, keeping a variable count, where count at any point gives the no of elements in the merged array.
PN: We are not storing the merged array, just keeping a count. Hence no extra space.
Stop when count = N^2 / 2. Return this value.
(only for odd numbers .. for even numbers, take both values n^2 / 2 and N^2 / 2 +1)

O(N^2 / 2) in constant space

- P November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I also think so, but we should also be able to use the property that the arrays are also sorted vertically(column wise).. so maybe merge sort time complexity could be reduced.

- Gaurav November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good point.
Lets see how can we use that.
First time, we know the first elements is A[0][0].

Then we need to companre A[0][1] and rest N-1 elements N-1 cols (A[1][0] ... A[N][0]) .. We just need to compare A[0][1] with A[0+1][0] (since in A[1][0] ... A[N][0], A[1][0] is the smallest) ..

The idea is, we just need to compare the values that have different column number, .. which should be done in constant time (since you can always find the smallest among N values in O(N)) ..

Will try to come up with pseudo code ..

Complexity (for original algo, which I guess I got wrong): M = N^2

O(M*N)

- P November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if (N%2 != 0){
  return Matrix[N/2][N/2];
} else {
  return (Matrix[N/2][N-1] + Matrix[N/2+1][0])/2;
}

- Anonymous November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what are you smoking... did you even try this ?

- Anonymous November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this solution is correct if the matrices are sorted..median in case of odd # of elements in a sequence is pos = floor(n/2)..which in case of matrix will be matrix[pos][pos] or..center of diagonal..

and if N^2 is even..then it'd be (Matrix[N/2][N-1] + Matrix[N/2+1][0])/2.. You can try..

This will work..in case of repetitions in matrix too!

- Jer November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I dont think the solution is correct
consider the matrix
1 5 9 12
6 12 16 18
7 16 17 20
8 18 20 25

answer should be 16
but with this approach it is 17

- getjar.com/todotasklist my android app November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic:
- Matrix of nxn numbers will have n^2 (say: nsq) numbers in sorted list.
If nsq is odd, median is a number at index nsq / 2 in the sorted list
If nsq is even, median is a a mean of numbers at indexes nsq / 2 and (nsq + 1) /2
- The trick is obtaining a sorted list out of this matrix. Strictly, speaking we
really don't need sorted list, but we need to traverse the matrix in sorted order.
- For i = 0 to n, Compare [i, i + 1 -> n-1] with [i + 1 -> n-1, i] and traverse
- Keep counting the number of sorted numbers passed by
- When sorted number counter reaches median index(es), take a value and note. In case of odd list, we just need to take one value. In case of even list, we need to take two values, and get mean of the two
- We can quit traversal once we find the values at median indexes

Here is the working code: h t t p://codepad.org/FEvad3aP (Remove spaces in http word of URL, CareerCup does not allow URLs in answers)

The complexity is: linear O(m) where 'm' is the element count (in case of a matrix of size nxn, m = n^2). The algorithm traverses at most m/2 elements and also does at most m/2 comparisons.

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can find the median in o(n^2) for a totally unsorted matrix using linear median finding algorithm. So what you have regardless of whether it works is not and improvement

- Anonymous November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can find the median in o(n^2) for a totally unsorted matrix using linear median finding algorithm. So what you have regardless of whether it works is not and improvement

- Anonymous November 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you misunderstood. Mine is also linear algorithm and pretty simple. n^2 itself is the number of elements here. In those algorithms you mentioned, O(n) is the time where 'n' is element count. In case of matrix of size nxn, the element count is 'n^2'. I hope that makes it clear.

Thanks,
Laxmi

- Laxmi Narsimha Rao Oruganti November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi laxmi,

I tried your solution for
1 5 7
2 6 8
4 11 15 ... i got 7 as the median whereas it should be 6 and even the traversal to have a sorted sequence is not correct.

- Gaurav November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey Gaurav,

Yes, you are right and code breaks for your input :(. I don't see any easy fix either :(.

Thanks again,
Laxmi

- olnrao November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This has to be O(n). If you have sorted rows and columns, you take any element as the centroid, you can show that the all elements in the second quadrant are smaller than the centroids value and all elements in the fourth quadrant are bigger than the centroids value. No such guarantee can be given for the elements in the first and third quadrants.

From this I believe that it is possible to show that the median of the matrix is same as the median of the secondary diagonal.

- Mohan November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Mohan,

That would mean for any matrix which has the same elements on the secondary diagonal has a same median ? Which can't be true just based on those few elements .

- Gaurav November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Gaurav, thts true. Median depends only on secondary diagonal values.
Other elements doesnt affect it.

- Anonymous November 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi Gaurav!

The question refers to matrices with whose rows and columns are in sorted order. The case you are referring is very easy to prove.

Let us say all the elements in the secondary diagonal are equal to x. Start with the top row and last column. Since, all the elements in the top row are sorted, let us say in increasing order, all the elements in the top row are less than or equal to x. Similarly all the elements in the last column are more than or equal to x. The median for this row and column put together is thus x.

Now, strip of the matrix with the top row and last column, and continue the same process. For every step, you strip the top row and last column till all the rows and columns are removed from the matrix. You can observe that median stays same.

- Anonymous November 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1  2  3  4 
5  6  7  8
9  10 11 12
13 14 15 16

Clearly for this case the median = (8 + 9)/2 doesn't lie on the secondary diagonal, so medians of matrix = median of scndry diagonal is completely wrong.

- ishantagarwal1986 November 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

See as simple as this:
divide the matrix equally in 4
if (n/2, n/2) index is lesser than n^2/2 , we know that the median would lie in the upper left corner.
Else we find the index i from the next 3 sub-matrices. Now i should be equal to n^2/2 - (n/2, n/2).

- Niki November 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can we view the matrix as n arrays that each contain n elements. then we can use n pointers to point to each row, and do merge sort to get the median

- Anonymous November 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
{if (N%2 != 0){
return Matrix[N/2][N/2];
} else {
return (Matrix[N/2][N/2+1] + Matrix[N/2+1][N/2])/2;
}
}}}

- aziz November 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are assuming the input to be:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Consider:

1 4 5
3 6 7
4 8 9

- P November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right. Thanks. so I think we can assume the median lies some where in the diagonal eg 4,6,5 in your example, since all numbers upper left of this diagonal is lower and lower right is bigger , if we sort the diagonal, we can find the median ?

- aziz November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, so now we know the N nos among which the median lies. But these N nos are not sorted.
We need to find N/2th (or N/2th and N/2 + 1 th) elment among these N nos.
If we apply order of statistics algo, we can find it in O(N).

Or we can choose to sort and get it in O(NlogN) which is much better than O(N^2) (N^2 is the total no of elements).

Good one .. :)

- P November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats true. Its lies on diagnal ( not principal diagonal). We can do in O(n).
Start from (0, 0). Compare (1,0) with (0,1). Goto the bigger value. From there, do similar comparison until u reach some diagonal element. For ex, if u r at (i,j), do comparison of (i+1,j) and (i, j+1).

- Anonymous November 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will be great ff somebody could provide pseudo code for this.

- Anonymous November 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will be great if somebody could provide pseudo code for this.

- Anonymous November 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i found it while searching, it finds in
nlogn time
kth smallest element in sorted matrix
selection_find(M, i0,j0, i2,j2, K):
# Find K-th smallest number between M(i0,j0) and M(i2,j2)
# assumption: M(i0,j0)<M(i2,j2)
N := number of values between M(i0,j0) and M(i2,j2)
# assumption: k<N
Pick at random i1,j1 so that M(i0,j0)<M(i1,j1)<M(i2,j2)
L := number of values between M(i0,j0) and M(i1,j1)
if L==K:
The answer is M(i1,j1)
if L<K:
The answer is selection_find(M, i1,j1, i2,j2, K-L)
if L>K:
The answer is selection_find(M, i0,j0, i1,j1, K)

median_find(M):
The answer is selection_find(M, 1,1, n,n, n²/2)

- master fuji November 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

OK master fuji, this looks interesting. Sadly, you don't give any supporting arguments to why this would be O(n log n) or how the algorithm actually works! For example how do you count the number of values between M(i0,j0) and M(i1,j1)? If you just go through the entire matrix, you counted n^2 elements! So, just in the 1st step, you are already over your O(n log n) time!

The trick to this problem is exactly this -- you split the matrix somewhere in the middle and you can easily eliminate about 1/2 of the elements in the fisrt step (the median has to be somewhere in the top right quadrant or bottom left quadrant). But the next step is not at all obvious.

- czpete425 November 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Youngify approach(Call Youngify N^2/2 times)

- Shwetank November 08, 2011 | Flag Reply


Add a Comment
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.

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