|
Input is a matrix of size n x m of 0s and 1s......
Microsoft Interview Questions and Answers
(Continued from previous question...)
40. Input is a matrix of size n x m of 0s and 1s......
Question:
Input is a matrix of size n x m of 0s and 1s.
eg:
1 0 0 1
0 0 1 0
0 0 0 0
If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1
Solution should be with Time complexity = O(n*m) and O(1) extra space
maybe an answer1:
public static void change(int[][] matrix){
//change by row
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(matrix[i][j] == 1){ //if one element is 1 mark all 0's on same row
for(int k = 0; k < matrix[i].length; k++){
if(matrix[i][k] == 0)
matrix[i][k] = 2;
}
break;
}
}
}
//change by column
for(int i = 0; i < matrix[0].length; i++){
for(int j = 0; j < matrix.length; j++){
if(matrix[j][i] == 1){ //if one element is 1 mark all 0's on same column
for(int k = 0; k < matrix.length; k++){
if(matrix[k][i] == 0)
matrix[k][i] = 2;
}
break;
}
}
}
//make all 2's 1
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(matrix[i][j] == 2){
matrix[i][j] = 1;
}
}
}
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[i].length; j++){
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
maybe an answer2:
se the matrix itself for book-keeping.
First try to find a column with all zeroes. If there are none, then all locations
needs to be filled with 1.
Now walk the rows, if a row needs to be set to 1, only set the corresponding entry in the column found above.
Similarly find an all zeroes row, and use that to book-keep the columns which need to be set to 1.
At the end make two passes, setting the rows and the columns using the information in the special column and row.
(Continued on next question...)
Other Interview Questions
| 