Microsoft Interview Question
Country: India
Interview Type: Phone Interview
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.
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
Finally some sane person who actually presents an algorithm instead of a truck load of cryptic code. Thank you!!
#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);
}
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;
}
}
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;
}
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;
myArray.Add(j+1);
}
}
if (foundOne) break;
}
}
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)
#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);
}
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;
}
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;
}
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.
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);
}
}
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);
}
}
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;
}
}
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
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;
}
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;
}
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;
}
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;
}
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;
}
}
int func ( int a[], int m, int n )
- ravi February 12, 2015{
int row;
i = m;
j = n;
while( i >= 0 && j >=0 )
{
if( a[i][j] )
{
j--;
row =i;
}
else
i--;
}
return(row);
}