Microsoft Interview Question
Software Engineer / DevelopersUse 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.
1. Set all 1's to 2's in the matrix
2.
for(i: 0 to n-1)
{
for(j: 0 to m-1)
{
if(A[i][j] == 2)
{
//change all 0's of that row and column to 1
}}}
3. Change 2's back to 1.
Time complexity = O((n*m)*(n+m))
Space complexity = O(1)
This is not O(nm) as you yourself noted. And what is the point of changing everything to 2? LOL.
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
if (a[i][j]==1){
//mark its corresponding row and colunm to -1
for (int k = 0; k<m; k++)
if (a[i][k]==0) //only covert 0 to -1, leave 1 no change :-)
a[i][k] = -1;
for (int k = 0; k<n; k++)
if (a[k][j]==0)
a[k][j]= -1;
}
}
}
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
if (a[i][j]==-1){
//revert it to 1
a[i][j]=1;
}
}
}
So basically using matrix itself as storage, just traverse it twice. I think I can find a better solution - thinking...
OK, use two stack to trace the row and column number that has all 0 in it.
int t = 0;
stack <int> r;
stack <int> c;
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
if (a[i][j]==1){
//make false if this row has 1
t = 1;
}
}
//check if this row has all 0
if (t==0){
//keep this row;
r.push(i);
}else{
//do not keep, reset t
t = 0;
}
}
for (int i = 0;i<m;i++){
for (int j = 0;j<n;j++){
if (a[j][i]==1){
//make false if this column has 1
t = 1;
}
}
//check if this column has all 0
if (t==0){
//keep this column;
c.push(i);
}else{
//do not keep, reset t
t = 0;
}
}
//use some extra storage
int rs = r.size();
int cs = c.size();
int* rr = new int [rs];
int* cc = new int [cs];
for (int i = rs-1; i>=0;i--){
rr[i]=r.top();
r.pop();
}
for (int i = cs-1; i>=0;i--){
cc[i]=c.top();
c.pop();
}
//set all elements to 1
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
a[i][j]=1;
}
}
// and change only intersections of these rows and columns with all 0
for (int i = 0;i<rs;i++){
for (int j = 0;j<cs;j++){
a[rr[i]][cc[j]]=0;
}
}
I will try to explain as good as I can. Imagine we have flags for specfying the directions Up Down Left Right. For example if a matrix element has UP flag set it means you need to set the flag for the cell up above to UP if it is not 1 during traverse. 3 traverses are needed.
First Traverse from top left corner to bottom right corner. If you encounter a 1 you just check the cell to right if it is 0 set it to RIGHT. Check the cell below if it is zero set the cell to DOWN. If you encounter a cell with value RIGHT set the cell to the right to RIGHT if it is zero. If you encounter a cell with value DOWN set the cell below to DOWN if it is zero.
Once finished also traverse from bottom right corner to top left corner using similar logic this time using LEFT and UP.
Once both traverses are finished convert all non zero values to 1.
O(n*m*3) 3 coming from 3 traverses.
call the myChange method with : myChange(a, flag);
here flag is used to keep the reference for the first column, whether or not to set the elements of the first column as one.
the idea here is that, i am storing the information for setting the 1's in ith row in the element a[i][0] and for jth column in a[0][j]. But as we are short of one element as the a[0][0] will need to store the information for first row and column as well.
#define N 3 //Row
#define M 4 //Column
void setRow(int a[N][M], int irow)
{
if( a[irow][0] < 2)
{
a[irow][0] += 2;
}
}
void setCol(int a[N][M], int jcol, int &flag)
{
if( jcol!=0 && a[0][jcol] < 2)
{
a[0][jcol] += 2;
}else if( flag == 0)
{
flag = 2;
}
}
void myChange( int a[N][M], int &flag)
{
for( int i=0; i<N; i++){
for( int j=0; j<M; j++){
if( a[i][j]==1)
{ setRow(a,i);
setCol(a,j, flag);
}
}
}
for( int i=N-1; i>=0; i--){
for( int j=M-1; j>0; j--){
if( a[i][0]>1 || a[0][j]>1)
a[i][j]=1;
}
if( flag)
a[i][0] = 1;
}
}
tell me if you find any flaws.
thanks
I don't know if this is cheating, but:
input = [
0b1001,
0b0010,
0b0000,]
col_mask = 0
for r in range(len(input)):
col_mask |= input[r]
if input[r] != 0:
input[r] = 0b1111
else:
input[r] = col_mask
for r in range(len(input)):
print bin(input[r])
Should actually be:
for input in [[
0b0000,
0b1001,
0b0010,],
[
0b1010,
0b0100,
0b0000,]]:
col_mask = 0
for r in range(len(input)):
col_mask |= input[r]
for r in range(len(input)):
if input[r] != 0:
input[r] = 0b1111
else:
input[r] = col_mask
for r in range(len(input)):
print bin(input[r])
print
<pre lang="" line="1" title="CodeMonkey95939" class="run-this">public class Matrix {
public static void flood(boolean[][] matrix) {
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col]) {
matrix[0][col] = true;
matrix[row][0] = true;
}
}
}
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
matrix[row][col] = matrix[0][col] || matrix[row][0];
}
}
}
public static void printMatrix(boolean[][] matrix) {
for (int row = 0; row < matrix.length; row++) {
for (int column = 0; column < matrix[0].length; column++) {
System.out.print(matrix[row][column] ? "1 " : "0 ");
}
System.out.println();
}
}
public static void main(String[] argc) {
boolean[][] matrix = new boolean[40][50];
// populate random booleans
Random random = new Random();
for (int i = 0; i < 40; i++) {
for (int j = 0; j < 50; j++) {
matrix[i][j] = false;
}
}
for (int i = 0; i < 5; i++) {
matrix[Math.abs(random.nextInt()) % 40][Math.abs(random.nextInt()) % 50] = true;
}
printMatrix(matrix);
flood(matrix);
printMatrix(matrix);
}
}
</pre><pre title="CodeMonkey95939" input="yes">
</pre>
Wait, no, I think this ends up setting everything to 1... you need to use an intermediate variable as suggested above...
mat = [[1, 0, 0, 1],
[0, 0, 1, 0],
[0, 0, 0, 0]]
def print_mat():
for row in mat:
print row
print
print_mat()
# Set first row and col to 2.
for r in range(len(mat)):
for c in range(len(mat[0])):
if mat[r][c]:
mat[0][c] = 2
mat[r][0] = 2
print_mat()
# Set r, c to 1 if need to change.
for r in range(0, len(mat)):
for c in range(0, len(mat[0])):
if (mat[0][c] == 2 or mat[r][0] == 2) and mat[r][c] != 2:
mat[r][c] = 1
print_mat()
# Change 2s back to 1
for r in range(0, len(mat)):
if mat[r][0] == 2:
mat[r][0] = 1
for c in range(0, len(mat[0])):
if mat[0][c] == 2:
mat[0][c] = 1
print_mat()
Step1
Sum up the last column and store in one variable t1
Sum up the last row and store in one variable t2
Sum up the columns (except the last) and store in the last row
Sum up the rows (except the last) and store in the last column
Step2
If t1 is positive change all the values in last column to 1
If t2 is positive change all the values in last row to 1
Loop over the last row cells (except the last) and if the value is positive change all the values in respective column to 1
Loop over the last column cells (except the last) and if the value is positive change all the values in respective row to 1
1 0 0 1
0 0 1 0
0 0 0 0
After step 1
t1=1, t2=0
1 0 0 2
0 0 1 1
1 0 1 0
After step 2
1 1 1 1
1 1 1 1
1 0 1 1
Array is scanned only 2 times and only 2 variables extra
Therefore complexities are as required
Let's start over:
1, find one cell C is 1; if there is none, all cells are 0.
2, use the same row and column cells of the found 1 as storage, sum up corresponding rows and columns.
3, identify the 0s in the cross of C, and get the cells should be marks as 0s.
int C_r = -1, C_c = -1;
// find the first cell with 1
for (int i = 0;i<n;i++){
for (int j = 0;j<m;j++){
if (a[i][j]==1){
//make false if this row has 1
C_r = i;
C_c = j;
break;
}
}
//check if it was found
if ((C_r != -1) && (C_c !=-1))
break;
}
if ((C_r == -1) && (C_c ==-1)){
cout<<"All cell are 0s"<<endl;
return 0;
}
//now C_r and C_c has value;
int sum=0;
for (int i = 0;i<m;i++){
if(i!=C_c){
for (int j = 0;j<n;j++)
sum+=a[j][i];
//store it in the cross of C
a[C_r][i]=sum;
//reset sum
sum = 0;
}
}
sum=0;
for (int i = 0;i<n;i++){
if(i!=C_r){
for (int j = 0;j<m;j++)
sum+=a[i][j];
//store it in the cross of C
a[i][C_r]=sum;
//reset sum
sum = 0;
}
}
//check if a element in row C_r a[C_r][j] is 1, then change all a[i][j] to 1
for (int i = 0;i<m;i++){
if(i!=C_c){
if (a[C_r][i]==1)
for (int j =0;j<n;j++)
if(j!=C_r)
a[j][i]=1;
}
}
for (int i = 0;i<n;i++){
if(i!=C_r){
if (a[i][C_c]==1)
for (int j =0;j<m;j++)
if(j!=C_c)
a[i][j]=1;
}
}
//then mark C_r row and C_c column to 1
for (int i = 0;i<n;i++)
a[i][C_c]=1;
for (int i = 0;i<m;i++)
a[C_r][i]=1;
Here is my solution:
#include <iostream>
#include <queue>
using namespace std;
int main()
{
const int row = 3;
const int col = 4;
int a[row][col] = { 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0};
queue <bool> s;
// Now print the array
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cout << a[i][j];
cout << " ";
}
cout << endl;
}
cout << endl;
// For each row
for (int i = 0; i < row; i++)
{
bool isPresent = false;
// If there is one in the column, enqueue true, else false
for (int j = 0; j < col; j++)
{
if (a[i][j] == 1 )
{
isPresent = true;
break;
}
}
s.push(isPresent);
}
// For each column
for (int j = 0; j < col; j++)
{
bool isPresent = false;
// If there is one in the row, enqueue true else false
for (int i = 0; i < row; i++)
{
if (a[i][j] == 1 )
{
isPresent = true;
break;
}
}
s.push(isPresent);
}
// Now get the front from the queue; if the element is true, set the entire column
for (int i = 0; i < row; i++)
{
if(s.front() == true)
{
for (int j = 0; j < col; j++)
{
a[i][j] = 1;
}
}
s.pop();
}
// Do the same with columns
for (int j = 0; j < col; j++)
{
if(s.front() == true)
{
for (int i = 0; i < row; i++)
{
a[i][j] = 1;
}
}
s.pop();
}
// Now print the array
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
cout << a[i][j];
cout << " ";
}
cout << endl;
}
cout << endl;
return 0;
}
traverse the whole matrix once. if a[i][j]==1 then a[0][j]=a[i][0]=3 -- O(n*m)
traverse first row if a[0][j]==3(j=1 for 1st iteration)
for(i=0 to n-1) a[i][j]=1 -- O(n*m)
traverse first column if a[i][0]==0(i=1 for 1st iteration) for(j=0to m-1) a[i][j]=1 -- O(n*m)
if(a[0][0]=3) make 1st row and column 1 -- O(n*m)
so total time complexity - O(n*m)
no extra space
correct me if i am wrong
Here's a very simple solution and i think this is what the first two post by Annonymous refer to. Below is the pseudo code:
for(i=0;i<row_count;i++)
for(j=0;j<column_count;j++)
{
if (a[i][j] == 1)
{
a[i][0] = 1;
a[0][j] = 1;
}
}
for(i=1;i<row_count;i++)
for(j=1;j<column_count;j++)
{
if (a[0][j] == 1 || a[i][0] == 1)
{
a[i][j] = 1;
}
]
if (a[0][0] == 1)
{
for (i=0;i<row_count;i++)
{
a[i][0] = 1;
}
for (i=0;i<column_count;i++)
{
a[0][i] = 1;
}
}
thus O(mn) time complex and no extra space requied
Small bug at a[0][0]?
Some a[0][i] and a[j][0] = 1 (i, j !=0) will change a[0][0] to 1.
I guess that is why O(1) space is needed.
package MyPackage;
public class Test {
public static void main(String[] args) {
int a[][] = {{1,0,0,0},
{0,1,0,0},
{1,0,0,1},
{1,0,1,0},
};
for(int i=0;i<a.length;i++)
for(int j=0;j<a[i].length;j++)
{
if(a[i][j]==1)
{
for(int l=0;l<a.length;l++)
{
if(a[l][j]==0)
a[l][j]=-1;
}
for(int k=0;k<a[i].length;k++)
{
if(a[i][k]==0)
a[i][k]=-1;
}
}
}
for(int i=0;i<a.length;i++)
{
for(int j=0;j<a[i].length;j++)
{
if(a[i][j]==-1)
a[i][j]=1;
System.out.print(a[i][j]);
}
System.out.println();
}
}
}
1. First making all the 0s as -1 for the row where the value is 1
2. while printing negate the -1 and print the matrix.
boolean mark = false;
//row wise marking from left to right
for(int i = 0; i < a.length; i++)
{
for(int j = 0; j < a[0].length; j++)
{
if(a[i][j] == 1)
mark = true;
else if(mark)
a[i][j] = 2;
}
mark = false;
}
mark = false;
//row wise marking from right to left
for(int i = a.length-1; i >= 0; i--)
{
for(int j = a[0].length -1; j >= 0; j--)
{
if(a[i][j] == 1)
mark = true;
else if(mark)
a[i][j] = 2;
}
mark = false;
}
//column
mark = false;
//column wise marking from left to right
for(int j = 0; j < a[0].length; j++)
{
for(int i = 0; i < a.length; i++)
{
if(a[i][j] == 1)
mark = true;
else if(mark)
a[i][j] = 2;
}
mark = false;
}
mark = false;
//column wise marking from right to left
for(int j = a[0].length -1; j >= 0; j--)
{
for(int i = a.length-1; i >= 0; i--)
{
if(a[i][j] == 1)
mark = true;
else if(mark)
a[i][j] = 2;
}
mark = false;
}
for(int i = 0;i < a.length; i++)
for(int j = 0;j < a[0].length; j++)
if(a[i][j] == 2)
a[i][j] = 1;
//C# using BitArray
static void Main()
{
Console.Write("n: ");
int n = int.Parse(Console.ReadLine());
Console.Write("m: ");
int m = int.Parse(Console.ReadLine());
BitArray[] matrix = new BitArray[n];
for (int i = 0; i < n; i++) //construct the matrix
matrix[i] = new BitArray(m);
Console.WriteLine("Input your matrix elements");
FillMatrix(matrix, n, m); //this method get the data into the matrix
int register = 0; //register the indices of the rows that contain 1s
int rowIndex;
for (int j = 0; j < m; j++)
{
rowIndex = -1;
for (int i = 0; i < n; i++)
{
if (matrix[i][j] == true)
{
rowIndex = i;
register |= ((int)0x1)<<rowIndex;
}
}
if (rowIndex != -1)
{
for (int i = 0; i < n; i++)
matrix[i][j] = true;
}
}
rowIndex = 0;
while (register != 0)
{
if ((register & 0x1) != 0)
{
matrix[rowIndex].Xor(matrix[rowIndex]);
matrix[rowIndex].Not();
}
rowIndex++;
register >>= 1;
}
Dispaly(matrix, n, m); //dispaly the output
}
public class Matrix {
private void print(int[][] matrix) {
int d = matrix.length;
for (int i = 0; i < d; ++i) {
for (int j = 0; j < matrix[i].length; ++j) {
System.out.print(matrix[i][j]);
System.out.print(' ');
}
System.out.println();
}
}
public void processMatrix(int[][] matrix, int si, int sj) {
for (int i = si; i < matrix.length; ++i) {
for (int j = sj; j < matrix[i].length; ++j) {
if (matrix[i][j] == 1) {
if (j + 1 < matrix[0].length) {
processMatrix(matrix, i, j + 1);
} else {
processMatrix(matrix, i + 1, 0);
}
for (int r = 0; r < matrix.length; ++r) {
matrix[r][j] = 1;
}
for (int c = 0; c < matrix[i].length; ++c) {
matrix[i][c] = 1;
}
return;
}
}
}
}
public static void main(String[] args) {
int[][] m = { { 1, 0, 0, 1 }, { 0, 0, 1, 0 }, { 0, 0, 0, 0 } };
Matrix instance = new Matrix();
instance.print(m);
instance.processMatrix(m, 0, 0);
System.out.println("after");
instance.print(m);
}
}
My solution : tracking 1s in integer vars (in bit presentation)
public static void MatrixChanges (int[,] A)
{
int vertical = 0;
int horizontal = 0;
int n = A.GetLength (0);
int m = A.GetLength (1);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (A [i, j] == 1)
{
vertical |= (1 << i);
horizontal |= (1 << j);
}
for (int i = 0; i < n ; i++)
for (int j = 0; j < m; j++)
A[i,j] = ((((vertical >> i) & 1) == 1) || (((horizontal >> j) & 1) == 1))? 1 : 0;
}
below uses the same idea as ctci solution
public class RowCol {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] a= new int[][]{{1, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 1, 1, 1}};
for (int j = 0; j < a.length; j++) {
System.out.println("");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i][j]);
}
}
System.out.println("");
System.out.println("");
System.out.println("");
RowCol rowCol = new RowCol();
rowCol.check(a);
for (int j = 0; j < a.length; j++) {
System.out.println("");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i][j]);
}
}
}
int[][] findZeros(int[][] matrix) {
for (int i = 0; i < matrix.length; i++)
for (int j = 0; j < matrix.length; j++)
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
return matrix;
}
int[][] check(int[][] matrix) {
matrix = findZeros(matrix);
for (int j = 0; j < matrix.length; j++) {
if (matrix[0][j] == 0)
matrix = nullifyColumn(j, matrix);
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0)
matrix = nullifyRow(i, matrix);
}
return matrix;
}
int[][] nullifyColumn(int j, int[][] matrix) {
if (matrix[0][j] == 0) {
for (int i = 0; i < matrix.length; i++)
matrix[i][j] = 0;
}
return matrix;
}
int[][] nullifyRow(int i, int[][] matrix) {
if (matrix[i][0] == 0) {
for (int j = 0; j < matrix.length; j++)
matrix[i][j] = 0;
}
return matrix;
}
}
What do you guys think about this..
int row, col;
for all rows r
for all columns c
if M[r][c] is 1 do
row << r; //bit wise
col << c;
for all rows r
for all columns c
if (row ^ r) > 0 || (col ^ c) > 0
M[r][c] = 1
Here we are using two variables irrespective so O(1)
And we are parsing the matrix twice so O(m*n)
what do you guys think?
Bad solution. You are in effect _trying_ to use O(m+n) memory, aren't you?
But in reality the program will just fail miserably because of the limited int size, giving you wrong results.
I am using two integers so it is definitely not O(m+n).
About the limit you are right, but any way you have to scan the matrix using for loop right with an index, like (for i=0; i<n;i++) so if i is integer here then my two variables row, col will be integers or they will be long. No?
No.
You n will have log n bits, while you require row and col to have n and m bits.
Yes?
<pre lang="" line="1" title="CodeMonkey79445" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey79445" input="yes">
</pre>
- Anonymous September 01, 2011