Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Lol .. no there cant be a row with all 0's and column with all 1's in same matrix.. avoid jumping into coding..
Can you please provide a solution for those of us who don't know "the celebrity problem"? Thank you so much!
Time Complexity : O( M * N )
Step 1 ) Store sum of each row and each column.
Mark all row/columns with sum 0 or 1 as ZERO or ONE.
If sum is 1, store what index had element 1.
Step 2 ) Iterate through all rows marked ZERO/ONE.
a) If a row is ZERO and a column marked ZERO/ONE exists, Bingo! we have our pair.
b ) If a row is ONE then check if the column corresponding to stored index is marked ZERO/ONE. If yes, we have our pair
keep repeating this process upto last row. if no success, no such row/column exists.
Cool, you were thinking just like I was :)
But you made several mistakes.
Columns need to be checked for sum of (n-1) and n.
Also, taking sums is a waste of a sweep down the rows/columns. It requires multiple sweeps if the sums are (n-1) for a column or 1 for a row.
And the last process is explained inefficiently. See my solution below.
Posting solution on behalf of Abhishek.
Here the idea is to traverse from the bottom to top.
1) consider a[i][j], check if i'th row is zero and j'th column is 1. if yes, return true. Note that we have started from a[n][n];
2) else if a[i][j] ==0
move one column left and check (1).
if a[i][j]==1
move one row up and check(1)..
In this code isrow checks if all the row element are 0's except a[i][j] and iscolumn checks if all the column elements are 1's except a[i][j].
isbooleanmatrix(A,i,j,n)
{
if(i==0 && j ==0)
{
if(isrow && iscoulumn)
return true;
else
{
printf("Not Present");
return;
}
}
else
{
if(isrow && iscoulumn)
return true;
else
{
if(A[i][j] == 0 && j)
isbooleanmatrix(A,i,j-1,n);
else
isbooleanmatrix(A,i-1,j,n);
if(i)
isbooleanmatrix(A,i-1,j,n);
else
isbooleanmatrix(A,i,j-1,n);
}
}
}
Please explain your idea first (or just your idea).
You have to touch every element of the array, O(n^2), so this gives us a lot of room to work with.
Say you have two integer arrays (zero initialized) of size n:
R[i] -> for information on each rows i
C[i] -> for information on each column i
As you are scanning row i from left to right, if you encounter a '1' somewhere but do not encounter it after that point, mark the position in R[i]. If you did not encounter any 1's mark this somehow (e.g., R[i] = -1). If any other case leave R[i] as it is (i.e., 0).
Do the same thing with each column ( mark position of the only 0 you saw in a column in C[i], or if you did not see any 0's, set C[i]=-1).
Now do your check:
If any element of R is > 0, say R[t], then if t's column was all 1's we have a match ... thus check of C[R[t]] = -1. We have a match if so.
If any element of C is > 0, say C[t], then if t's row was all 0's we have a match.. thus check R[C[t]] = -1. We will have a match.
Note, these check only takes O(n) time.
Going through each column and row only takes O(n^2) time.
Thus total O(n^2).
If interviewer expects somtehing that is n^2 without the O , then he/she is a loser.
Everything here is about 2n^2 + O(n). So why bother coming up with fancy/trickery? A systematic solution gives the best case time.
def magic_row_col_exists(matrix):
row_size = len(matrix)
col_size = len(matrix[0])
# dict to track which row/col is invalid
invalid_rows = {}
invalid_cols = {}
num_zeroes_in_row = [0] * row_size
num_ones_in_col = [0] * col_size
# iterate all elements in the matrix
for i in xrange(0, row_size):
# if either all rows are invalid or all cols are invalid, return False
if len(invalid_cols) == col_size or len(invalid_rows) == row_size:
return False
for j in xrange(0, col_size):
if matrix[i][j] == 0:
num_zeroes_in_row[i] += 1
else:
num_ones_in_col[j] +=1
# mark if this row is invalid
if j > 1 and num_zeroes_in_row[i] < j:
invalid_rows[i] = True
# mark if this col is invalid
if i > 1 and num_ones_in_col[j] < i:
invalid_cols[j] = True
if len(invalid_rows) == row_size or len(invalid_cols) == col_size:
return False
else:
# valid row indices are those which are not in invalid_rows
valid_row_indices = [ i for i in xrange(0, row_size) if i not in invalid_rows.keys():
for i in valid_row_indices:
if num_zeroes_in_row[i] == row_size:
# if a row containing all zeroes, as long as there is a col that is valid, return True
if len(invalid_cols) < col_size:
return True
else:
# if a row contains all zeroes, except 1
for j in xrange(0, col_size):
# look all the values in the column containing 1, they all must contain 1's
# if so, return True
if matrix[i][j] == 1 and num_ones_in_col[j] == col_size:
return True
return False
If you go through two consecutive rows , you will either find a 1 or not. Which is what we have to do here right ?
I mean the matrix will be say :
0 0 0 0
0 0 0 1
0 0 0 1
0 0 0 1
or say
0 1 0
0 1 0
0 1 0
In either case if we check two consecutive rows, then we have our result right?
it's not enough to check just 2 consecutive rows.
in the following example, only row 4 and column 3 match the problem's requirements, but there is no way to "guess" that we need to look up row 4. we need to check all rows
0 0 1 1 0
0 1 1 0 0
1 1 1 0 0
0 0 1 0 0
0 0 1 0 1
int row, col;
printf("Enter row number: ");
scanf_s("%d", &row);
printf("\nEnter column number: ");
scanf_s("%d", &col);
if(row > n || col > n)
{
printf("\nIncorrect row/col value!");
}
else
{
int flag = 0;
for(int i = 0; i<n; i++)
{
if(matrix[row-1][i] != 0 && i!=col-1)
{
flag = 1;
break;
}
if(matrix[i][col-1]!=1 && i!=row-1)
{
flag=1;
break;
}
}
if(flag == 0)
{
printf("Row and Column values are correct!!!!!");
}
else
{
printf("Row and Column values are not correct---");
}
}
1. Traverse the given matrix from top left to bottom right.
2. Keep track of the row. If row has all zeros and only one ambigous elemtent.
Save AMBIGUOUS_ROW[i] = Column Index of ambiguous elem. i is the row index we are conidering.
3. If row is all zeros. Mark AMBIGUOUS_ROW[i] as -2.
If not mark AMBIGUOUS_ROW[i] = -1 to indicate invalid row.
4. Perform the same with all columns marking row indices of all ambiguous elements. However check for 1s now. These are two seperate loops outside each other complexity is still O(n).
// We now have both AMBIGOUS_ROW[] and AMBIGOUS_COL[]
5. Traverse AMBIGUOUS_ROW from 0 to N-1. Each element with index 'i' in this array represents the ith row.
6. If AMBIGOUS_ROW[i] == -1 ignore. // Invalid row
7. If AMBIGOUS_ROW[i] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_COL // All 0 row
8. If AMBIGOUS_ROW[i] == Something else, 5 for example, then see AMBIGOUS_COL[i]. If its -2, we have a match, otherwise we dont.
9. Now repeat for cols.
10. Traverse AMBIGUOUS_COL from 0 to N-1. Each element with index 'j' in this array represents the jth column.
11. If AMBIGOUS_COL[j] == -1 ignore.
12. If AMBIGOUS_COL[j] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_ROW
13. If AMBIGOUS_COL[j] == Something else, 10 for example, then see AMBIGOUS_ROW[j]. If its -2, we have a match, otherwise we dont.
1. Traverse the given matrix from top left to bottom right.
2. Keep track of the row. If row has all zeros and only one ambiguous element.
Save AMBIGUOUS_ROW[i] = Column Index of ambiguous elem. i is the row index we are considering.
3. If row is all zeros. Mark AMBIGUOUS_ROW[i] as -2.
If not mark AMBIGUOUS_ROW[i] = -1 to indicate invalid row.
4. Perform the same with all columns marking row indices of all ambiguous elements. However check for 1s now. These are two separate loops outside each other complexity is still O(n).
// We now have both AMBIGOUS_ROW[] and AMBIGOUS_COL[]
5. Traverse AMBIGUOUS_ROW from 0 to N-1. Each element with index 'i' in this array represents the ith row.
6. If AMBIGOUS_ROW[i] == -1 ignore. // Invalid row
7. If AMBIGOUS_ROW[i] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_COL // All 0 row
8. If AMBIGOUS_ROW[i] == Something else, 5 for example, then see AMBIGOUS_COL[5]. If its -2, we have a match, otherwise we dont.
9. Now repeat for cols.
10. Traverse AMBIGUOUS_COL from 0 to N-1. Each element with index 'j' in this array represents the jth column.
11. If AMBIGOUS_COL[j] == -1 ignore.
12. If AMBIGOUS_COL[j] == -2 ignore // All potential matches will be caught while traversing AMBIGUOUS_ROW
13. If AMBIGOUS_COL[j] == Something else, 10 for example, then see AMBIGOUS_ROW[10]. If its -2, we have a match, otherwise we dont.
In step 2 : "Keep track of the row. If row has all zeros and only one ambiguous element.... : this takes O(n ^ 2) "
Please correct me if I am wrong. Maybe I misunderstood step 1.
Traverse the matrix diagonally.
1) traverse each diagonal element.
2) while traversing, check if a[i-1][j]==0 && a[i][j-1]==1;
3) if (2) satisfies then i and j could be the row and column we are looking for. Traverse the entire column up and down and check if all are ones, then traverse the entire row left and right and check if all are zeros.
4) If still we don't get the row and column , traverse diagonally till the end repeating (2) and (3)
There are n*n elements, so you can't possible have a O(n) solution, but O(n*n).
- Miguel Oliveira September 11, 2013