Microsoft Interview Question for Software Engineer in Tests

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 8 vote

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={{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 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.

int min = a;
int minOfRows[rows];
for(i = 0;i < rows;i++)
minOfRows[i] = 0;
minOfRows = 1;
for(i = 1;i < k;i++){
min = INT_MAX;
for(j = 0;j < rows; j++){
if(minOfRows[j] < cols){
if(a[j][minOfRows[j]] < min){
min = a[j][minOfRows[j]];
r = j;
}
}
}
minOfRows[r]++;
}

Comment hidden because of low score. Click to expand.
0

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} , Set B = { Neighbours of a, i.e a , a } ;

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'

Comment hidden because of low score. Click to expand.
0

how to do this arrays if three arrays are given?

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

find min at 0,0 then adjust the matrix by moving all the row elements or columns then repeat the same for k times.

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

void getkthMin(int kth)
{
int a = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};

// The smallest item is located at a
// 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;
}
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];
}
}

Comment hidden because of low score. Click to expand.
0

Will this work for a(mXn) matrices since it seems by your pointer initialization, that it is assumed only for 3X4 matrices!

Comment hidden because of low score. Click to expand.
0

Anon you are right. This problem is more difficult than what I thought. I will post another solution for it which will print the matrix in order.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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++
}

Comment hidden because of low score. Click to expand.
0

This will not work for following matrix:-
int [][] a =
1, 2, 3, 4
5, 7, 9, 10
6, 15, 20, 22

Find 3rd minimum i.e. 3 here..

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

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 = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}, {11,16,21,23}};
bool visitedNode = {false};

std::cout<<a<<"(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;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

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

Something similar to 25 horses . Minimum number of steps to find to 3

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

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 = {{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;
}

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

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;
}

Comment hidden because of low score. Click to expand.
0

Corrected :Complexity is O((m + n)*k)

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

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);
}

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

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;
if k==m*n return ary[m][n];
if k<(m*n)/2 {
//create a minHeap H
//push triplet (ary,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

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

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

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=INT_MAX){  //the matrix is empty
return false;
}
min=matrix;
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;
}
}

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

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!

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

In your case, if K is median, then the run time will be O(m*(m*n/2))

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

public static int findSmallest(int arr[][], int k) {
int row = 0;
int column = 0;
int m = arr.length;
int n = arr.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];

}

Comment hidden because of low score. Click to expand.
0

For this input
int a = {{2,5,8,10}, {4,7,9,12}, {6,15,20,22}};

This will give the wrong result for k=3.

Comment hidden because of low score. Click to expand.
0

check out my solution above..It works.

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.

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.