Microsoft Interview Question Software Engineer in Tests
public List<int> SortData(List<List<int>> matrix)
{
List<int> v = new List<int>();
int count = 0;
List<int> ps = new List<int>();
for (int i = 0; i < matrix.Count; i++)
{
ps.Add(0);
count += matrix[i].Count;
}
while (count-- > 0)
{
int min = int.MaxValue;
int index = 0;
for (int y = 0; y < matrix.Count; y++)
{
if (ps[y] < matrix[y].Count && matrix[y][ps[y]] < min)
{
index = y;
min = matrix[y][ps[y]];
}
}
ps[index]++;
v.Add(min);
}
return v;
}
1, 4, 8,
5, 6, 9,
8, 10, 11,
9, 10, 12,
rows = 4
count of numbers = 12
output = 1 4 5 6 8 8 9 9 10 10 11 12
@First Anonymous
Your approach seems fine but you need to add a proper explanation for the same. Also I feel we can have some simple and short answer as your approach seems way too big/complex.
Anyone out there with some smart answer?
For Lickie,
Actually this is just a normal counting sort. Suppose the range is from n1 to n2, then we have an counting array c[] with size n1 - n2 + 1 and initialize with 0s. then scan matrix from a[0][0] to a [m-1][n-1]. if a[i][j] = x1, then a[x1 + n1] ++. When we finish, we have c[] with frequency of all numbers in the matrix. Then scan c[], for each c[i] = k, print i k times. We than get the sorted array.
For matrix scanning, we have time complexity O(mn).
For counting array scanning, we have time complexity O(i - j + 1). since i-j+1 <= mn, O(mn) + O(i - j + 1) = O(mn).
Hope now is clear.
I also agree that there might be other better solution since this method dose not make use of the property of row and column have been sorted. However the time complexity can not be better than O(mn) since we have to scan each matrix element. it may get better space complexity though.
1. Count sorting with cost of space which is determined the MIN and MAX value of the matrix(2 corners). It's a quicker but non-stable algorithm. With Cost: O(M*N + (MAX-MIN));
2. Standard Merge sorting treats matrix as M array of sorted arrays. Cost: O(M^2*N)
3. Merge sorting with min heap treats matrix as M array of sorted arrays, but use min heap structure to sort the right most elements of each arrays. Cost: O(M*N*lgM)
Both 2 and 3 are stable algorithms. Obviously, 3 the favorite one. (down side is code complexity )
Counting sort is stable. Radix sort uses counting sort as a subroutine because of its stability.
How about the following approach?
The problem here is not really sort the elements in the matrix,but just print them in sorted fashion.
Print the smallest element a(1,1)(we assume 1..m,1..n as indexes),and insert a(1,2) and a(2,1),along with the indexes into a min_heap.
while( min_heap is not empty){
next_element_to_print = deleteMin(min_heap);
print(next_element_to_print);
min_heap.insert(Right(next_element_to_print));
min_heap.insert(Bottom(next_element_to_print));
}
// Right() and Bottom() functions return the right and bottom neighbors of the
// current element
The above matrix may not be a min heap. so Min Heap has to be built first. so the complexity would be M*Nlog(M*N).....
You do not build the complete min heap out of the matrix in one go here. You incrementally build it and also carry out the deleteMin operation hand in hand as the algorithm proceeds.
We don't have to actually sort the complete matrix.So why at all go for Merge sort.Also I'm talking about using a min heap as an auxillary data structure.There is no heap-SORT involved here.
Hi,
Plz chk if I am correct in this approach. Since all the rows and columns are sorted (let it be ascending order), it means for any element e(i,j) is the smallest in the sub-matrix A'[i-n, j-m].
if this property is used, the sorted matrix can be produced as e(1,1), min_sort{e(2,1), e(1,2)}, min_sort{e(3,1), e(2,2), e(1,3)}, ... min_sort{e(i,1), e(i+1,2)..e(1,i)}
This approach utilises the sort order of the matrix while reducing the time complexity to 2*(k^2) * log(k) where k = (m+n)/2
In my view, most of above solutions miss the basic point and so the basic method.
There's no need to boter with minHeap and such jazz.
Have 2 pointers. Walk first pointer on row i and second on row i+1. compare each column/number and print the smaller followed by larger. Advance a pointer only if its contents were printed.
What did I miss if anything?
In my view, most of above solutions miss the basic point and so the basic method.
There's no need to boter with minHeap and such jazz.
Have 2 pointers. Walk first pointer on row i and second on row i+1. compare each column/number and print the smaller followed by larger. Advance a pointer only if its contents were printed.
What did I miss if anything?
What is the significance of 'row & column sorted' here ? I understand that a 'row sorted' n*m matrix can be considered as N arrays of sorted data each of M length.
And with that said, min heap would make sense. As we would simply maintain a heap of the n-elements one from each stream & then keep popping and adding element from the stream from which the element was just popped.
However if the data is also column as well as row sorted, then all the data in the matrix apparently would be sorted anyways ? Is this thought right ?
Also on other lines, had the matrix data being random without any 'sorted' constraints
then, merge sort would make sense. In each iteration, keep merging rows one each time. That would take O(nm*log(nm)) in worst case but not in place.
Please advise
This is an extract min from a young tablaeu. Ref: http://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
Why can't we traverse diagonally and apply merge on the column and row, instead of different rows ? This is a O(mn) solution
Assume that the entire matrix is a min heap
Have a function ExtractMin() that returns the minimum elsment in O(m+n)
Using the function the above problem can be solved in O(mn*(m+n))
ExtractMin()
{
remove the element a[0[0] and replace it by infinity;
MinHeapify(A,0,0);
}
MinHeapify(A,i,j)
{
i_index=i;
j_index=j;
min = a[i][j];
if( i+1 < m && j < m && a[i+1][j] < min )
{
i_index = i+1;
j_index=j;
}
if(i < m && j+1 < m && a[i][j+1] < min )
{
i_index = i;
j_index=j+1;
}
if(i_index == i && j_inddex == j)
return;
else
swap(a[i][j],a[i_index][j_index])
MinHeapify(A,i_index,j_index);
}
Some errors corrected
- Anonymous August 25, 2009Assume that the entire matrix is a min heap
Have a function ExtractMin() that returns the minimum element in O(m+n)
Using the function the above problem can be solved in O(mn*(m+n))
ExtractMin()
{
remove the element a[0[0] and replace it by infinity;
reduce the number of elements by one;
MinHeapify(A,0,0);
}
MinHeapify(A,i,j)
{
i_index=i;
j_index=j;
min = a[i][j];
if( i+1 < m && j < m && a[i+1][j] < min )
{
i_index = i+1;
j_index=j;
min = a[i+1][j];
}
if(i < m && j+1 < m && a[i][j+1] < min )
{
i_index = i;
j_index=j+1;
}
if(i_index == i && j_inddex == j)
return;
else
swap(a[i][j],a[i_index][j_index])
MinHeapify(A,i_index,j_index);
}