Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Can you walk me through your logic for this below matrix?
1 2 8 14
3 6 15 17
5 9 18 20
7 11 19 21
I'm assuming that the median for even number of elements (say, m) is either A[m/2] or A[m/2+1].
- 1st iteration:
1 2 8 14 ----> 2,8
3 6 15 17 ------> 6,15
5 9 18 20 -------> 9,18
7 11 19 21 -------> 11,19
The median of the 2-D array must lie between [2,19]. Eliminate all elements lesser than 2 and greater than 19 (which is 1, 20, 21) in this case.
Repeat again finding median for the rows again.
You will end up with '9' as the median.
for this [1 2 3 5 6 7 8 {9 11} 14 15 17 18 19 20 21]
median is (9+11)/2 = 10
so the answer u r getting '9' as median is wrong it seems.
for this [1 2 3 5 6 7 8 {9 11} 14 15 17 18 19 20 21]
median is (9+11)/2 = 10
so the answer u r getting '9' as median is wrong it seems.
I mentioned before that I'm assuming that for 4 elements, the median can be either the 2nd or 3rd element and not taking the avg of both.
The above technique can be tweaked to return the average at the end. In that case, you will get 10.
The best case if O(nlogn). However, if you take the numbers of the array and sort them, the ave case complexity would be O(nlogn). Once it is sorted, it is easy to find the median. Then why one should go for all the hassle proposed here?
This question seems weird. The solution is pretty straight forward if this is the complete information about the question. Are you sure this is exactly what is asked?
This is complete question... For below array can you explain the logic how you find the median element if this is so easy?
1 3 4 8 9
2 5 18 45 50
6 7 22 25 55
Yes the example given above is incorrect, the example can be given as:
1 3 4 8 9
2 5 18 25 50
6 7 22 45 55
take the middle element, here 18, all element before that in the left and above will be smaller than 18, and all element on the right, and bottom will be larger than 18. Thus we need to find median of the remaining elements i.e. {6, 7}, 18, {8, 9}, We can sort these sorted array sub arrays to get median. This will work if we have odd number of row and columns, in case of even rows and/or columns, we shall have modify logic a little, but idea will remain same. The complexity of this approach will be log(max(row, col)), where matrix is of dimension row X column.
@abhishekatuw: Now consider this sample,
1 2 8 14
3 6 15 17
5 9 18 20
7 11 19 21
Here we need to sort {5,7,11},{6,15,9,18},{8,14,17} right??? here complexity of the algorithm is not coming O(max(row,col))... If i am right, is there better solution? else let me know what wrong thing i have done?
Was the question asked for the position at Hyderabad. or Redmond.. and was it for MSIT or IDC?
The median of the diagnoal will be the median of the whole array.
Because if we read the matrix in diagnoal form from top left (smallest element in matrix) to bottom right (largest element in matrix) we will get a sorted list of the entire matrix.
Do you mean to say that if we have a NxN matrix, we need to consider only sqrt(2)*N diagonal elements for finding the OVERALL median?
Didn't understand the logic of reading the matrix through diagonal. Can you please elaborate?
There is another post for same question, however even their I think they could not reach to a concrete solution. Tried to put the link, but careercup is not allowing.
@abhishekatuw :
jus post question id part of the link :-
like this for this thread
question?id=12305698
The following program works for all kind of matrices. The logic that I followed is forming pairs. Consider the example discussed below.
1 2 8 14
3 6 15 17
5 9 18 20
7 11 19 21
For this matrix, the pairs are formed like(1, 21), (2, 20), (3, 19).... and so on. The first pair represents the least and the largest number, then second one represents the next least and the next largest and so on...
If the row*column is even, then the last pair formed by the above procedure will contain median. Both the number can act as median here.
If the row*col is odd, then the last pair formed will contain same number. Hence that will be the median.
#include<stdio.h>
void main()
{
int mat[10][10];
int r, c, row, col, min, max, mn, mx, count = 0, r1, r2, m;
printf("\nEnter the numbe of rows and columns\n");
scanf("%d %d", &row, &col);
printf("\nEnter the elements row-wise\n");
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
scanf("%d", &mat[r][c]);
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
if(c == (col-1))
printf("%d\n", mat[r][c]);
else
printf("%d ", mat[r][c]);
min = mat[0][0];
max = mat[row - 1][col - 1];
mn = min;
mx = max;
r1 = ((row*col)/2 - 1); //-----For even (row*col)----//
r2 = ((row*col)-1)/2; //-----(For odd row*col)----//
//-----------------If row*col are even------------------//
if((row*col)%2 == 0)
{
for(count = 0; count < r1; count ++)
{
mx = max;
mn = min;
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
if(mat[r][c] > min && mat[r][c] < mx)
{
mx = mat[r][c];
}
mn = mx;
m = mx;
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
if(mat[r][c] > mn && mat[r][c] < max)
{
mn = mat[r][c];
}
min = m;
max = mn;
printf(" {%d %d } ", min, max); //------ To show pairs-----//
}
printf("\nMedian is %d\n", min);
}
//-----------------If row*col are odd------------------//
else
{
for(count = 0; count < r2; count++)
{
mx = max;
mn = min;
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
if(mat[r][c] > min && mat[r][c] < mx)
{
mx = mat[r][c];
}
mn = mx;
m = mx;
for(r = 0; r < row; r++)
for(c = 0; c < col; c++)
if(mat[r][c] > mn && mat[r][c] < max)
{
mn = mat[r][c];
}
min = m;
max = mn;
printf(" {%d %d} ", min, max);
}
printf("Median is %d", min);
}
}
1 2 8
3 6 15
5 9 18
now total elements are N.
now imagine given 2D matrix in for of 3 different 1D array (column wise(moving top to bottom ))
we know that median will be at position N/2;
so considering 1D array ( i.e coulmn wise ) we want to do merge 3 one dimensional array
when count reaches N/2 ....that element is the median.
I give up on understanding the "median of the rows" approach. So instead I am solving it the straightforward way, which is to keep a minimum heap. Each time I pop out the minimum element, I will try to add the element to the right and to the bottom (unless they have been added already) to the heap. Will keep doing this until I popped enough elements (depending on whether total elements is odd or even).
The Element class is omitted for brevity. It basically just contains 3 fields: (1) value (2) row (3) col
static double median(int[][] matrix) {
int numRows = matrix.length;
int numCols = matrix[0].length;
boolean added[][] = new boolean[numRows][numCols];
int n = numRows * numCols;
PriorityQueue<Element> heap = new PriorityQueue<Element>();
heap.add(new Element(matrix[0][0], 0, 0));
Element e = null;
for(int i=(n-1)/2; i>=0; i--) {
e = heap.poll();
if(i == 0)
break;
int row = e.row;
int col = e.col;
if(row != numRows-1 && !added[row+1][col]) {
heap.add(new Element(matrix[row+1][col], row+1, col));
added[row+1][col] = true;
}
if(col != numCols-1 && !added[row][col+1]) {
heap.add(new Element(matrix[row][col+1], row, col+1));
added[row][col+1] = true;
}
}
if(n%2 == 1)
return e.value;
else return (e.value + heap.poll().value)/2.0;
}
struct item{
int val, x, y;
item(int val_, int x_, int y_) : val = val_, x = x_, y = y_ {};
};
int getMedian(const vector< vector<int> >& a)
{
int m = a.size(), n = a[0].size();
int k = (m+n)/2;
priority_queue< item > pq;
vector< vector<bool> > visit(m, vector<bool>(n, 0));
pq.push( item(a[m-1][n-1], m-1, n-1) );
visit[m-1][n-1] = 1;
while (--k) {
item i = pq.top(); pq.pop();
int x = i.x, y = i.y, val = i.val;
if (x-1 >=0 && !visit[x-1][y] ) { visit[x-1][y] = 1; pq.push( item(a[x-1][y], x-1, y) ); }
if (y-1 >=0 && !visit[x][y-1] ) { visit[x][y-1] = 1; pq.push( item(a[x][y-1], x, y-1) ); }
}
if ( (m+n)&1 ) return pq.top().val;
else return (pq.top().val + val)/2.0;
}
1.Find medians of either each row or column.
2. Then find median of all medians...
If i am wrong ... please let me know it..
For below array
1 3 4 8 9 ---- median is 4
2 5 18 45 50 ---- median is 18
6 7 22 25 55 ---- median is 22
As per your logic median is median of medians 18 (4 18 22)
Actually it is 8
if you put these element in a single dimension array and sort it you will get 1 2 3 4 5 6 7 8 9 18 22 25 45 50 55.
medain will avg of two middle elements which will not be 18.
i think we can use divide and conqueuer.
Let me knw if i m wrong..
plzzzzzzzz comment.
@naga4042: This is 3X5 matrix, so there are total 15 elements, so 8th element is the median... if there are even number of elements ex. 4X4 matrix then median will be average of 8th and 9th element. can you code how you use divide and conquer logic here?
- This is similar to finding the median of 2 sorted arrays. Can extend the same divide and conquer technique here.
- Bugaboo January 02, 2012- Find the median of all rows (Say m1,m2,m3 for 3X5 matrix)
- The overall median should lie b/w Min(m1,m2,m3) and Max(m1,m2,m3)
- Eliminate all elements from each row which does not lie in the above range
- Repeat above steps once again until the input becomes small enough to sort and pick the median (since sorting smaller set of elements like 4 elements take constant time)
Worst case time complexity will be O(n^3) [for a square matrix]
Best case time complexity will be O(nlog n) [Input size always divides by half]