## Microsoft Interview Question

Country: India
Interview Type: Phone Interview

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

int func ( int a[], int m, int n )
{

int row;
i = m;
j = n;
while( i >= 0 && j >=0 )
{
if( a[i][j] )
{
j--;
row =i;
}
else
i--;
}
return(row);
}

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

``O(m+n)``

Comment hidden because of low score. Click to expand.
-2

It should be O(mn)

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

The idea here is to scan right until you reach a 1, then scan down until you reach a 0, then right until you reach a 1, continue this cycle and record when you reach a new 1. This will be your max row.

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

Could you clarify this? I didn't understand.

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

Sure, (Also I made a mistake- should be left and downward, not right and downward)

Let's say our matrix is the following:

00011111
00001111
00111111
01111111
00001111

We know that the max 1 row will be the one where we reach a 0 the latest from the left. Start from the top right. Scan left until we reach a 0. When we reach a zero, record the column we are on- if this column is lower than the max row column, then we set it as the max row. When we reach 0, go down the column until we reach a 1, when we get to this scan left again until we reach 0, doing the same process. When we are at the last row and at a 0, we are done.
First row, we scan left until we get to the x
000x1111
00001111
00111111
01111111
00001111

Scan down to the first 1 we get:

00011111
00001111
001x1111
01111111
00001111

Scan left again:

00011111
00001111
00x11111
01111111
00001111

Scan down until we reach a 1:

00011111
00001111
00111111
01x11111
00001111

Left to get to zero:

00011111
00001111
00111111
0x111111
00001111

Down to the last row:

00011111
00001111
00111111
01111111
0x001111

We have seen that the row that had the smallest column was the 2nd to last one, so this is our answer. Because at worse cast we step down from top right to bottom left, we find the answer in at most 2n operations

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

Finally some sane person who actually presents an algorithm instead of a truck load of cryptic code. Thank you!!

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

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

``````#include <stdio.h>

int findRowMaxOnes(int *arr, int m, int n)
{
int i = 0, j = n-1;
while(!((i == m) || (j < 0)))
{
if (*((arr+i*n)+j) == 1)
j--;

if (*((arr+i*n)+j) == 0)
i++;
}
return n-j-1;

}

int main()
{
int ans;
int arr[6][10] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1},
{0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,1,1,1,1,1,1,1,1},
};

ans = findRowMaxOnes((int *)arr, 6, 10);
printf("%d\n", ans);
}``````

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

``````public class MatrixWithMaxOnes
{
public int FindRowWithMaxOnes(int[][] matrix)
{
int maxRow = 0, index=0, prevIndex =0;
for(int i =0;i<matrix.Length;i++)
{
index = BinarySearch(matrix[i], 0, matrix[i].Length-1);

if (index <= prevIndex)
{
prevIndex = index;
index = 0;
maxRow = i;
}
}
return maxRow;
}

public int BinarySearch(int[] array, int start, int end)
{
if (start <= end)
{
int mid = (start + end) / 2;
if((mid ==0 || array[mid-1]<1) && array[mid]==1)
{
return mid;
}
else if (array[mid] < 1)
{
return BinarySearch(array, mid + 1, end);
}
else
{
return BinarySearch(array, start, mid - 1);
}
}
return -1;
}

}``````

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

Since each row starts with 0's and followed by 1's you need to scan the rows according to column - worst case if will be O(MN) runtime

``````public int findRow(int[][] arr) {
for (int col=arr[0].length; col++)
for(int row=0; row<arr.length; row++)
if(arr[row][col] == 1)
return row;

return -1;
}``````

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

``````def mostOnesRow(matrix)
mostOnesRow = 0
soonestOneCol = matrix[0].size

0.step(matrix.size - 1, 1) do |row|
0.step(matrix[row].size - 1, 1) do |col|
next if col > soonestOneCol
if matrix[row][col] == 1
soonestOneCol = col
mostOnesRow   = row
end
end
end
return mostOnesRow
end``````

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

typedef class CArray<int, int> CIntArray;

void GetRowWithMaxOnes(int** Array, int numRows, int numCols, CIntArray &myArray)
{
myArray.RemoveAll();
if (Array == NULL || *Array == NULL ||numRows < 1 || numCols < 1) return ;
bool foundOne = false;
for (int i = 0; i < numCols; i++)
{
for (int j = 0; j < numRows; j++)
{
if(Array[j][i] == 1)
{
foundOne = true;
}
}
if (foundOne) break;
}
}

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

I am returning an Array instead of int because there can be more than one row with the same (MAX) value of ones

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

binary search on the rows, at each iteration, if there are both 0 and 1 under the heads, sift the heads above 0, and move the rest of the heads to left. if there are only 0 under the heads, move the heads to the right, if there are only 1 under the heads, move the heads to the left. run time O(m lg^2 n)

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

#include <stdio.h>

int findRowMaxOnes(int *arr, int m, int n)
{
#if 0
int i,j;
for (i=0; i<m; i++)
{
for (j=0; j<n; j++)
//printf("%d ", *((arr+i*n)+j));
printf("\n");
}
return 0;
#endif

int i = 0, j = n-1;
while(!((i == m) || (j < 0)))
{
if (*((arr+i*n)+j) == 1)
j--;

if (*((arr+i*n)+j) == 0)
i++;
}
return n-j-1;

}

int main()
{
int ans;
int arr[6][10] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1},
{0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,1,1,1,1,1,1,1,1},
};

ans = findRowMaxOnes((int *)arr, 6, 10);
printf("%d\n", ans);
}

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

Complexity is O(n)

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

I think the complexity is O(n+m). Your solution is the most efficient.

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

public int findMaxRow(int[][] arr)
{
int max=0;
int rowWithMax=0;
for (int row=0; row < arr.length; row++)
{
int tempMax=0;
for(int col=0; col<arr[0].length; col++)
{
if(arr[row][col] == 1)
{
tempMax=tempMax+1;
}
}

if ( tempMax > max)
{
max=tempMax;
rowWithMax=row;
}

}
return rowWithMax;
}

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

public int findMaxRow(int[][] arr)
{
int max=0;
int rowWithMax=0;
for (int row=0; row < arr.length; row++)
{
int tempMax=0;
for(int col=0; col<arr[0].length; col++)
{
if(arr[row][col] == 1)
{
tempMax=tempMax+1;
}
}

if ( tempMax > max)
{
max=tempMax;
rowWithMax=row;
}

}
return rowWithMax;
}

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

Solutions can be done in

``O(n)``

or

``O(log(n))``

For first row we can use binary search to find the ending of 0 or starting of 1. for next row we can continue from the last row since we only need to find the lower (i.e. left side of the current index of 1.

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

By using binary search to get a row's first 1, Is it time complexity come to O(m+logn)

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

``````public class maxOnes {
public static int[][] inputArr = { { 0, 0, 0, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1, 1, 1, 1 } };

public static int maxRow=0;
public static void moveLeft(int row){
for (int i = 0; i < inputArr[0].length; i++) {
if(inputArr[row][i]==1){
maxRow=row;
moveDown(row,i);
break;
}
}
}

public static void moveDown(int row,int col){
for (int i = row+1; i < inputArr.length; i++) {
if(inputArr[i][col]==1){
maxRow=i;
moveRight(i, col);
break;
}
}
}

public static void moveRight(int row,int col){
for (int i = col; i >=0; i--) {
if(inputArr[row][i]==0){
moveDown(row, i+1);
break;
}
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
moveLeft(0);
System.out.println(maxRow);
}

}``````

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

``````public class maxOnes {
public static int[][] inputArr = { { 0, 0, 0, 1, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1, 1, 1, 1 } };

public static int maxRow=0;
public static void moveLeft(int row){
for (int i = 0; i < inputArr[0].length; i++) {
if(inputArr[row][i]==1){
maxRow=row;
moveDown(row,i);
break;
}
}
}

public static void moveDown(int row,int col){
for (int i = row+1; i < inputArr.length; i++) {
if(inputArr[i][col]==1){
maxRow=i;
moveRight(i, col);
break;
}
}
}

public static void moveRight(int row,int col){
for (int i = col; i >=0; i--) {
if(inputArr[row][i]==0){
moveDown(row, i+1);
break;
}
}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
moveLeft(0);
System.out.println(maxRow);
}

}``````

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

``````public class MatrixWithMaxOnes
{
public int FindRowWithMaxOnes(int[][] matrix)
{
int maxRow = 0, index=0, prevIndex =0;
for(int i =0;i<matrix.Length;i++)
{
index = BinarySearch(matrix[i], 0, matrix[i].Length-1);

if (index <= prevIndex)
{
prevIndex = index;
index = 0;
maxRow = i;
}
}
return maxRow;
}

public int BinarySearch(int[] array, int start, int end)
{
if (start <= end)
{
int mid = (start + end) / 2;
if((mid ==0 || array[mid-1]<1) && array[mid]==1)
{
return mid;
}
else if (array[mid] < 1)
{
return BinarySearch(array, mid + 1, end);
}
else
{
return BinarySearch(array, start, mid - 1);
}
}
return -1;
}

}``````

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

The max value which can be in any row is no. of columns, with this in mind we need to start column based search starting from left most column i.e., with column id 0, this search cannot be binary search or any other optimized as each row value is not incremental(or we don't know) whenever we find first 1 in our column based search we found our row, the value will be =
no. of columns - found_col_id or max_column_id - found_col_id + 1

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

public int MaxRow(int[][] m)
{
int row=0,col=0,oldMaxRow=0;
//Find first occurence of 1 in row=0;
while(row < m.Length)
{
if(m[row][col]==1)
{
col--; break;
}
else
col++;
}
//try to move down till you hit 0, then move left in the same row;
// repeate till the last row.
while(col<m[0].Length && row < m.Length)
{
//if you hit 1 in down then update column
if(m[row][col]==1)
{
oldMaxRow=row;
while(col>=0){ if( m[row][col]==1) col--; else break; }
}
//else move down further to search 1
else row++;
}

return row;

}

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

public int MaxRow(int[][] m)
{
int row=0,col=0,oldMaxRow=0;
//Find first occurence of 1 in row=0;
while(row < m.Length)
{
if(m[row][col]==1)
{
col--; break;
}
else
col++;
}
//try to move down till you hit 0, then move left in the same row;
// repeate till the last row.
while(col<m[0].Length && row < m.Length)
{
//if you hit 1 in down then update column
if(m[row][col]==1)
{
oldMaxRow=row;
while(col>=0){ if( m[row][col]==1) col--; else break; }
}
//else move down further to search 1
else row++;
}

return row;

}

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

``````public int MaxRow(int[][] m)
{
int row=0,col=0,oldMaxRow=0;
//Find first occurence of 1 in row=0;
while(row < m.Length)
{
if(m[row][col]==1)
{
col--; break;
}
else
col++;
}
//try to move down till you hit 0, then move left in the same row;
// repeate till the last row.
while(col<m[0].Length && row < m.Length)
{
//if you hit 1 in down then update column
if(m[row][col]==1)
{
oldMaxRow=row;
while(col>=0){ if( m[row][col]==1) col--; else break; }
}
//else move down further to search 1
else row++;
}

return row;``````

}

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

``````private static int FindLargestRow(int[,] array, int n)
{
var largestRow = -1;
var maxNonZeroCells = 0;

for (int i = 0; i < n; i++)
{
for (int j = n - 1 - maxNonZeroCells; j >= 0; j--)
{
if (array[i, j] == 1)
{
var nonZeroCells = n - j;
if (nonZeroCells > maxNonZeroCells)
{
maxNonZeroCells = nonZeroCells;
largestRow = i;
}
}
else
break;
}
}
return largestRow;
}``````

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

``````A <- Input Matrix
start with A[1] and figure out the first 1 lets the index was j
for k = 2 to n
if A[k][j] equals 1 then
while(j > 0 and A[k][j] == 1)
j = j -1;
j = j +1
output n-j as max size, one can save k as well to tell which row``````

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

``````public class bSearch {

public static void main(String[] args){
int[][] matrix = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1},
{0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,1,1,1,1,1,1,1,1},
};
System.out.println(maxOnes(matrix));

}

private static int maxOnes(int[][] matrix){
int m = matrix.length;
int n = matrix[0].length;
int l = 0; int r = n;
for(int i = 0; i < m; i++){
if(matrix[i][r -1] == 1) {
r = bSearch(matrix[i], l, r -1);
}
}
return n - r;
}

private static int bSearch(int[] nums, int l, int r){
int x = r;
while(l <= r){
int mid = l + ((r-l) >>1);
if(nums[mid] == 1){
x = mid;
r = mid -1;
} else l = mid + 1;
}
return x;
}
}``````

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

``````private static int RowWithMaxOne(int[,] input)
{
int maxRow = input.GetLength(0);
int maxCol = input.GetLength(1);
int row = 0;
int col = maxCol - 1;
int result = 0;
while (row < maxRow && col >= 0)
{
if (input[row, col] == 1)
{
col--;
result = row;
}
else
row++;
}
return result;
}``````

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.