Adobe Amazon Interview Question
Country: India
ACRush dude
First thing ... we need to find row with max no of 1's not 0.
Second thing....It is not of O(n). The worst case will be O(n2).
@volvo if we have to find max 1's we can start with top left and move forward to next column in a row if we are getting 1's else if it's a 0 we move down in next row same column.
Since in worst case we traverse n + n = 2n cells of the matrix hence complexity is O(2n) => O(n)
ACRush, with the revisions in his latest comment, is correct. It is O(n).
I seem to vaguely recall seeing ACRush on the Google Code Jam scoreboard, if memory serves me right :)
Not exactly 2nd best coder... Tourist would come before him and if the problem is way too tough....Then Lyrically is the best amongst all of them...!!!
Jesus Christ, that was an awesome algorithm! Of course it finds out the row with maximum number of zeroes, but you get the idea, for maximum number of one's, you just have to start from top-left and go rightwards. Vintage ACRush!
lets say we have a matrix of size (rows * columns)
scan towards the left on the first row from top right till you hit the last 1.
move downwards on that column till you hit another row with 1
repeat the same
// add checks to validate rows and columns > 0
c=columns
r=0
bestr = 0
// start from top right
while (r < rows && c > 0) {
if (a[r][c-1] == 0) r++ else { c--; bestr=r}
}
ya. I agree. During interview we settled on this as the best approach worst case is 0(m+n)
In your question you have said all rows are sorted.
But I think in this solution you are assuming all rows and columns are sorted.
ok i may be understanding the solution in a different way. But the question has ONLY rows sorted(ie, values in rows are sorted).
Ex matrix (4 rows, 3 colmuns):
011 <= 1st row sorted so 1s are at end
001 <= 2nd row sorted
000 <= 3rd row, all 0s
011 <=4th row with 1s at end
O(m+n) is not possible with the question that you have stated here.
we need to look into each row, we can apply binary search on column of that row so total time complexity is O(mLogn)
Questions states that each row is sorted in descending order, so the matrix above should have been this instead:
10000
11000
11100
00000
11111
Having said that, we are asked to find the maximum number of 1s (unless the question was asking for 0s originally). So once we find the last 1 in the first row and start moving downwards, if we encounter another 1 again, why would you want to move left again? Shouldn't you move right instead?
O(log n) time. Start from the middle column (n/2) and check if any row has 1's. If yes, store the column value and proceed in columns with (n/2) to (n) and check only for rows which had 1's previously.
Modified Binary Search is perfect solution for this problem.
Ravenclaw don't go from column to column. In next loop also check for ((n/2)+n)/2 column.
Ravenclaw dont you think it is O(nlog n) rather than O(log n) coz for iterating all the rows in a column 'n' iterations would be needed?
this is O(nlgn) as in worst case consider matrix is full of 1's an no 0.Then for each iteration you check all rows ie n for 1's, as total no of iterations is lg n time complexity amounts to nlgn
At max 2n operation.
#include <stdio.h>
#define SIZE 6
int matrix[SIZE][SIZE] = {
{1,1,1,1,0,0},
{0,0,0,0,0,0},
{1,0,0,0,0,0},
{1,1,1,0,0,0},
{1,1,1,0,0,0},
{1,1,0,0,0,0}
};
int main () {
int i=0, j=0;
while ( i < SIZE ) {
if ( j == SIZE )
break ;
while ( j < SIZE ) {
if ( matrix[i][j] == 1 ) {
j ++ ;
}
else break ;
}
i ++ ;
}
printf ( "\n%d", j ) ;
return 0;
}
Let's say n/2 coloumn has all 1 , OR even if some of those has 1 in it then ?
ok i am figuring out something here but not clear.
Please elaborate, with the help of interviewer I could find out a solution with 0(m+n), but i think anything with binary search would still be better.
Binary search is the right way, matrix is not sorted row wise as you can check the question
011
111
000
sorted column wise --->
but not row wise
|
|
v
so we need to count no of 1's in first row using binary search and keep track of row number and 1's count, then move to the next row and perform the same, at the end you will have 1's count for all the rows, print all the rows which has max 1's which should be closer or equal to n (column length)
Mat[n][n]
int row = 0;
int i;
for (i = n- 1; (i >= 0) && (!Mat[0][i]); --i);
int column = i;
if (i == n - 1)
return row;
int tryingColumn = i + 1;
for (j = 1; j < n; ++j)
{
if (Mat[j][tryingColumn])
{
++tryingColumn;
while (tryingColumn < n)
{
if (Mat[j][tryingColumn])
++tryingColumn;
}
row = j;
if (tryingColumn == n)
return row;
}
}
return row;
Mat[n][n]
int row = 0;
int i;
for (i = n- 1; (i >= 0) && (!Mat[0][i]); --i);
int column = i;
if (i == n - 1)
return row;
int tryingColumn = i + 1;
for (j = 1; j < n; ++j)
{
if (Mat[j][tryingColumn])
{
++tryingColumn;
while (tryingColumn < n)
{
if (Mat[j][tryingColumn])
++tryingColumn;
}
row = j;
if (tryingColumn == n)
return row;
}
}
return row;
Can be done in logn..Keep binary searching on each row till you are encountering one..Remove those rows which got zero..Last row left is the solution..
nice questio though taking the help of binary search it will still be O(nlogn) worst case
1. using binary search find the 1(index i) which has 0 at index i + 1. Once you got that move to 2. next row and check if newRow(index) == 0 then move to next row // this has less 1st than earlier row
3. else apply binarySearch on newRow from index to nth index as shown in step 1 // this has more or equal 1s than earlier row
eventually you will find the row which has max number of 1s
Though worst case it will be O(NlogN)
worst case is
row1 has one 1
row2 has two 1
row3 has three 1.
eventually it will go to complexity o(n logn)
//O(n) time, O(1) space solution. Just move right (while we have 1s) and down. Keep a track of longest row
public int getLongestRowIdx(int[][] m) {
int longestRowIdx = 0;
int longestClmnIdx = 0;
int i = 0;
int j = 0;
for (int i = 0; i < m.length; i++) {
while (j < m[0].length && m[i][j] == 1)
j++;
if (j - 1 > longestClmnIdx) {
longestRowIdx = i;
longestClmnIdx = j - 1;
}
}
return longestRowIdx;
}
int FindMaxRow(int a[][],n)
{
int j = n-1;
int i = 0;
int Max = i;
while( i<n && j<n)
{
if(a[0][j] != 0)
{
j--;
}
else
{
i++;
j++;
}
if(i>0)
{
if(a[i][j] != 1)
{
i++;
}
else
{
Max = i;
j++;
}
}
}
Return Max;
}
Very simple.
Just search the first column.If any row has one in it then it would be the biggest as the whole matrix is sorted as mentioned.
public class MatrixMax {
public static void main(String[] args) {
int mat[][]=new int[5][5];
mat[0][0]=0;
mat[0][1]=1;
mat[0][2]=1;
mat[0][3]=1;
mat[0][4]=1;
mat[1][0]=0;
mat[1][1]=0;
mat[1][2]=1;
mat[1][3]=1;
mat[1][4]=1;
mat[2][0]=0;
mat[2][1]=0;
mat[2][2]=0;
mat[2][3]=1;
mat[2][4]=1;
mat[3][0]=1;
mat[3][1]=1;
mat[3][2]=1;
mat[3][3]=1;
mat[3][4]=1;
mat[4][0]=0;
mat[4][1]=0;
mat[4][2]=0;
mat[4][3]=1;
mat[4][4]=1;
//this is for worst case scenario.. all are zero
/*for(int i=0;i<mat.length;i++){
for(int j=0;j<mat[i].length;j++){
mat[i][j]=0;
}
}*/
int st=0;
int end=mat[0].length;
int j=0;
int bestr = 0;
int count=0;
j=(st+end)/2;
System.out.println("here "+j);
while(j>=0 && j<mat[0].length){
boolean flag=false;
System.out.println("Value of j "+j);
for(int i=0;i<mat.length;i++){
count++;
if(mat[i][j]==1){
end=j;
bestr=i;
flag=true;
break;
}
}
if(!flag){
st=j;
}
if(j==0 || j==mat[0].length-1)
break;
j=(st+end)/2;
}
System.out.println("Best r "+bestr);
System.out.println("Count "+count);
}
}
This code is based on binary search...
Even in worst case scenario count=15. (5*5 matrix)
using binary search for N rows, for example, search starts with N/2 position for each row. The search terminates for the row if current position at this row is 0. For the remaining rows, the search repeat until there is only one row left. Worst case O(NlgN)
It can be done in O(n) time.
- ACRush August 13, 2012Start from top right element check if its 0 or 1, if its 0 move to j-1 element in that row and store the index of row in a variable,if its 1 move to next row by incrementing i but keeping j same. do the same step here as well.
At the end the variable will consist of row with max 0's.