Microsoft Interview Question
Software Engineer in TestsCountry: India
Interview Type: In-Person
Okay..here is another one..in O(k.x) time and O(k+x) space.
where x = k in worst case, but in average case , x will be of order O(1).
The idea is to traverse the matrix in such a way that we encounter kth element directly.
a.) Maintain two sets Set A and Set B.
Initially, set A = { NULL }, Set B = {NULL}
Set A == elements which we have seen till now.
Set B == neighbours of the elements of Set A,in sorted order using insertion sort.
b.) Set A = {a[0][0]} , Set B = { Neighbours of a[0][0], i.e a[0][1] , a[1][0] } ;
c.) if sizeof(set A) == k ), return kth element from Set A.
d.) else move minimum(Set B) to set A .
e.) Insert neighbours ( neighbours(a[x][y]) = {a[x][y+1] ,a[x+1][y],a[x-1][y],a[x][y-1]) of minimum(Set B) to Set B[use insertion sort]. As Set B will be of small size, you can assume that insertion sort will be fast and will do the ordering in O(1) time.
In the above example:
Set A Set B
{NULL } {NULL}
{2} {4,5}
{2,4} {5,6,7}
{2,4,5} {6,7,8}
{2,4,5,6} {7,8,15}
{2,4,5,6,7} {8,15}
Here...k == 5 , so stop and return 5th element of Set A i.e, '7'
void getkthMin(int kth)
{
int a[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};
// The smallest item is located at a[0][0]
// For given a a[x][y], the succeding item will be in one of the following numbers:
// a[x-1][y+1] if (a[x-1][y+1] < a[x][y]) then increase the column until a bigger number is reached.
// a[x][y+1]
// a[x+1][y]
// a[x+1][y-1] if (a[x+1][y-1] < a[x][y]) then increase the row until a bigger number is reached.
if (kth == 1)
{
std::cout<<"The "<<kth<<"th smallest number is "<<a[0][0];
}
else
{
int counter = 1;
int x = 0;
int y = 0;
while (counter < kth)
{
int a1 = INT_MAX;
int a2 = INT_MAX;
int a3 = INT_MAX;
int a4 = INT_MAX;
int x1 = x;
int y1 = y;
int x2 = x;
int y2 = y;
int x3 = x;
int y3 = y;
int x4 = x;
int y4 = y;
if (x - 1 >= 0)
{
while (a[x1-1][y1+1] < a[x][y])
{
y1++;
}
x1 = x1 - 1;
y1 = y1 + 1;
a1 = a[x1][y1];
}
if (y2 + 1 < 4)
{
y2 = y2+1;
a2 = a[x2][y2];
}
if (x3 + 1 < 3)
{
x3 = x3 + 1;
a3 = a[x3][y3];
}
if (y - 1 >= 0)
{
while (a[x4+1][y4-1] < a[x][y])
{
x4++;
}
x4 = x4 + 1;
y4 = y4 - 1;
a4 = a[x4][y4];
}
if (a1 < a2 && a1 < a3 && a1 < a4)
{
// a1 is the succeding item
x = x1;
y = y1;
}
else if (a2 < a1 && a2 < a3 && a2 < a4)
{
x = x2;
y = y2;
}
else if (a3 < a1 && a3 < a2 && a3 < a4)
{
x = x3;
y = y3;
}
else
{
x = x4;
y = y4;
}
std::cout<<"The "<<counter + 1<<"th smallest item is "<<a[x][y]<<std::endl;
counter++;
}
std::cout<<"The "<<kth<<"th smallest item is "<<a[x][y];
}
}
Will this work for a(mXn) matrices since it seems by your pointer initialization, that it is assumed only for 3X4 matrices!
r1=0;c1=0;r2=0,c2=1;
int element;
while(ctr<k)
{
if(a[r1][c1]<a[r2][c2]){element =a[r1][c1]; r1++; }
else {element =a[r2][c2];r2++;}
if(r1==arr.length){r1=0;c1=c2+1;}
if(r2==arr.length){r2=0;c2=c1+1;}
ctr++
}
This method will print the matrix in order and it's easy to modify so it can print the nth element
struct Point
{
Point(int row = 0, int column = 0):
x(row),
y(column)
{}
int x;
int y;
};
void printInOrder(void)
{
int a[4][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}, {11,16,21,23}};
bool visitedNode[4][4] = {false};
std::cout<<a[0][0]<<"(0,0) ";;
typedef std::list<Point> BoundaryList;
BoundaryList boundaryList;
int minX = 0;
int minY = 0;
Point aPoint(minX,minY);
visitedNode[minX][minY] = true;
boundaryList.push_back(aPoint);
while (minX < 4 && minY < 4)
{
int succeedingNum = INT_MAX;
BoundaryList::iterator it = boundaryList.begin();
while (!boundaryList.empty() && it != boundaryList.end())
{
aPoint = *it;
// The left and down side items have been visited already so this is
// not the bondary point anymore. Remove it from the list
//
if ((aPoint.x == 4 || visitedNode[aPoint.x + 1][aPoint.y] == true) &&
(aPoint.y == 4 || visitedNode[aPoint.x][aPoint.y + 1] == true))
{
it = boundaryList.erase(it);
}
else
{
int x = aPoint.x;
int y = aPoint.y;
// For each bonuary point, check the left and down side item and the smallest
// one will be the succeeding item
//
if (x + 1 < 4 && visitedNode[x+1][y] != true && a[x+1][y] < succeedingNum)
{
succeedingNum = a[x+1][y];
minX = x+1;
minY = y;
}
if (y + 1 < 4 && visitedNode[x][y+1] != true && a[x][y+1] < succeedingNum)
{
succeedingNum = a[x][y+1];
minX = x;
minY = y+1;
}
it++;
}
}
Point boundaryPoint(minX, minY);
visitedNode[minX][minY] = true;
std::cout<<succeedingNum<<"("<<minX<<","<<minY<<") ";
boundaryList.push_back(boundaryPoint);
if (minX == 3 && minY == 3)
{
break;
}
}
}
The following sorts the matrix. To find 'kth' element, the add a check to stop the while loop at ctr==k.
private static int[] sortMatrix(int a[][],int rows,int cols){
int elem[]=new int[rows*cols];
int r1=0,c1=0,r2=0,c2=1,count=0;
while(c1<cols && c2<cols){
if(a[r1][c1]<a[r2][c2]){
elem[count]=a[r1][c1];
r1++;
}
else{
elem[count]=a[r2][c2];
r2++;
}
if(r1==rows){
r1=0;
c1=c2+1;
}
if(r2==rows){
r2=0;
c2=c1+1;
}
count++;
}
elem[count]=a[rows-1][cols-1];
return elem;
}
First I sort the matrix merging each row. Then element at (k-1) of the sorted array is the answer. For this solution, it is enough that the matrix is sorted row wised. Or I couldn't make the use of column and row sorted matrix :(
void mergeSortedArray(int *a1, int *a2, int &sizeR)
{
int size1 = sizeR;
int size2 = 4;
sizeR = size1 + size2;
int arrayR[sizeR];
int index1 = 0;
int index2 = 0;
int indexR = 0;
while ((index1 < size1) && (index2 < size2))
{
if (a1[index1] < a2[index2])
{
arrayR[indexR] = a1[index1];
index1++;
}
else
{
arrayR[indexR] = a2[index2];
index2++;
}
indexR++;
}
for (int i=index1; i<size1; i++)
{
arrayR[indexR] = a1[i];
indexR++;
}
for (int i=index2; i<size2; i++)
{
arrayR[indexR] = a2[i];
indexR++;
}
for (int i=0; i<sizeR; i++)
{
a1[i] = arrayR[i];
std::cout << "element in arraymerged " << arrayR[i] << std::endl;
}
}
void findKthSmallestInColumnRowSortedMatrix(int k)
{
int array[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};
int numberofRows = 3;
int numberofColumns = 4;
int sizeResult = numberofColumns * numberofRows;
int arrayResult[sizeResult];
int indexResult = 0;
for (int i=0; i<numberofRows; i++)
{
mergeSortedArray(arrayResult, array[i], indexResult);
}
std::cout << k << " smallest element is " << arrayResult[k - 1] << std::endl;
}
This is called Young's Tableau.
Perform k remove from this and maintain the state of Tableau. Remember to use INFINITY as a large number for elements which are no longer valid.
Complexity O( max(M,N)+K)
int RemoveMin(PYNGTBL tbl, int x, int y)
{
if( Empty(tbl, x, y))
return INF;
int min = tbl->a[x][y];
if(Min(tbl,x,y+1) > Min(tbl, x+1, y))
{
tbl->a[x][y]= RemoveMin(tbl,x+1, y);
}
else
{
tbl->a[x][y]= RemoveMin(tbl,x, y+1);
}
return min;
}
public void find(int nth) {
if (nth >= M * N) {
return;
}
int[] rows = new int[M];
for (int i = 0; i < M; i++) {
rows[i] = 0;
}
int ptr = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nth; i++) {
min = Integer.MAX_VALUE;
int r = 0;
for (int k = 0; k <= ptr; k++) {
if (matrix[k][rows[k]] < min) {
min = matrix[k][rows[k]];
r =k;
}
}
if(rows[r] == 0){
ptr++;
if(ptr == M){
ptr--;
}
}
rows[r]++;
}
System.out.println(min);
}
A O(K log K) algorithm
Logic: after ary[p][q], the next smallest element is either ary[p+1][q] or ary[p][q+1]
If K==1 return ary[0][0];
if k==m*n return ary[m][n];
if k<(m*n)/2 {
//create a minHeap H
//push triplet (ary[0][0],0,0) into minHeap
for (int i=0; i<k; i++) {
//extract root of heap, say (val, p, q)
min=val
//push ary[p+1][q], and ary[p][q+1]
//pop the top element
}
else {
//do the same as if block, except you start from bottom and use maxHeap and execute it m*n-k times
}
return min
Using a Tableau algorithm doesn't need a min-heap data structure.
The code is as follows:
int getKthMin(int matrix[][],int m,int n,int k){
int min;
for(int i=0;i<k;i++){
extractMin(matrix[][],m, n,min);
}
return min;
}
bool extractMin(int &matrix[][],int m,int n,int& min){
if(matrix[0][0]=INT_MAX){ //the matrix is empty
return false;
}
min=matrix[0][0];
int i=0,j=0,ii,jj;
while(true){
if(i+1<m){
if( j+1<n ){
if(matrix[i+1][j]<matrix[i][j+1]){
ii=i+1;
jj=j;
}else{
ii=i;
j=j+1
}
}else{
ii=i+1;
jj=j;
}
}else{
if(1+j<n){
ii=i;
jj=j+1;
} else{
return true;
}
}
int temp=matrix[ii][jj];
matrix[ii][jj]=matrix[i][j];
matrix[i][i]=temp;
i=ii;
j=jj;
}
}
Can we do better with this way?
public int findKth (int[][] mat, int m, int n, int k) {
if (k > m*n)
return -1; // Just an error code
int[] count = new int[m];
int total = 0;
// when there are still elements in the matrix
while (true) {
int min = Integer.MAX_VALUE;
int idx;
// Find the min one
for (int i = 0; i < m; i++) {
if (count[i] < n) {
if (mat[i][count[i]] < min) {
min = mat[i][count[i]];
idx = i;
}
}
}
total++;
count[idx]++;
if (total == k) {
return min;
}
}
}
In this way, the running time should be O(k*m), and we should always choose min(m, n) to use here. If I am wrong, please correct me. Thanks!
I don't have a solution for this question.
However, there is an algorithm to find Kth elements in an array, which runs O(N)
public static int findSmallest(int arr[][], int k) {
int row = 0;
int column = 0;
int m = arr.length;
int n = arr[0].length;
//k is out of range
if(k > m * n)
return -1;
//k is the max element
if(k == m * n)
return arr[m - 1][n -1];
if(k <= m)
column = 0;
else
column = k / m;
row = ((k - (column * m)) - 1);
return arr[row][column];
}
For this input
int a[3][4] = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};
This will give the wrong result for k=3.
your code will return 6, correct answer should be 5.
I hope this will be helpful. It has time complexity O(k.num_rows) and space complexity O(num_cols)
Basically I find the minimum element k times. And for finding minimum element we just need to check the first (unscanned) element of each row. And then increment it accordingly.
min stores the minimum element.
minOfRows[i] stores the index (i.e column) of row i which is the first unscanned or rather minimum element of that row.
For eg: a[3][4]={{2,5,6,10},{4,8,9,12},{7,15,20,22}};
minOfRows = 0 for all rows.
For 1st iteration:
min = 2 (1st element of the matrix is minimum and last element (bottom right) is the maximum)
minOfRows[0] is incremented by 1;
For 2nd iteration:
We check minimum from among minOfRows[j] column element for each row j. and update min and minOfRows accordingly.
- artemis October 27, 2012