Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
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.
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)
if (N%2 != 0){
return Matrix[N/2][N/2];
} else {
return (Matrix[N/2][N-1] + Matrix[N/2+1][0])/2;
}
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!
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
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
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
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
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.
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.
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 .
Hi Gaurav, thts true. Median depends only on secondary diagonal values.
Other elements doesnt affect it.
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.
{{
{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;
}
}}}
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
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 ?
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 .. :)
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).
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)
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.
Is it not a merge sort, where we are given N sorted arrays and need to find the median of N arrays compbined?
- P November 06, 2011Just 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