Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
3
of 3 vote

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();
		}
	}

- Anonymous September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

given a matrix of 0's and 1's means it is probably a bitmap, and inorder to set a value of '2' you would need it to be integers. Since the question doesn't mention the matrix is a bitmap you solution is fine but for a bitmap this is not a valid solution

- archioliis October 08, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use 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.

- Anonymous August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use first row and first column itself, instead of trying to find an all zero column/row. Just remember whether to set those to all 1 or not.

- Anonymous August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- R August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not O(nm) as you yourself noted. And what is the point of changing everything to 2? LOL.

- Anonymous August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok, as you have written, maybe you need it.

- Anonymous August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i cud do it by traversing the matrix 4 times..2 times columnwise and 2 times row wirse

is there some betr approach?

- coder August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
            }
        }

}

- xbai@smu.edu August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So basically using matrix itself as storage, just traverse it twice. I think I can find a better solution - thinking...

- xbai@smu.edu August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;            
        }
    }

- xbai@smu.edu August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem clearly states space is O(1).

- Rayden August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't understand how the code presented by @xbai is O(n*m). i think it is O(n*m)*(n+m).Consider if each of the cell of the matrix is 1 then for each cell your code traverse that whole row and whole column.

If i misunderstood some thing then please correct me.

- Abdul Samad April 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Rayden August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not symmetric in dimiension.

- xbai@smu.edu September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Aditya August 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(n*m(n+m)) not O(n*m)

- Rayden August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am traversing each element in first nested for loop and then again traversing each element whether to set it or not ..
I think it is O(2*n*m) could you please elaborate on how you arrived at the O(n*m(n+m)) Conclusion

- Aditya August 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The 1s and 0s make me think of binary trickery...

- Jesse September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- Jesse September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Jesse September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

<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>

- Anonymous September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the best answer so far.

- Jesse September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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()

- Jesse September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, it won't set everything to 1... as it does the flood in two iterations.

- Anonymous September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Naveen September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- xbai@smu.edu September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So two extra integers this time.

- xbai@smu.edu September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Victor September 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Store complexity should be O(1)

- Anonymous September 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I mean space complexity should be O(1)

- Anonymous September 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- baghel September 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

edit: traverse first column if a[i][0]==3(i=1 for 1st iteration)

- baghel September 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 6 vote

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

- Anonymous September 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the best solution........no bug I found

- abhrajuit September 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will fail for input:
0 0 0 1
0 0 1 0
0 0 0 0

- brown_geek September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Abaghel exactly what i posted...although after you :-)

- The Artist September 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- DNS September 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

do a 2 pass approach:
1. First pass, set row[i] and col[j]=1 if a[i][j]=1
2. Second pass, set a[i][j]=1 if either row[i] or col[j] is 1

- hs September 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- brown_geek September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess question must have enforced the condition 2D array as binary matrix

MM()
	for each i from 0 to n-1
		for each j from 0 to m-1
			if(a[i][j])
				a[0][j] = 1
				a[i][0] = 1
	for each i from n-1 to 0
		for each j from m-1 to 0
			if(!a[i][j] && (a[i][0]  || a[0][j]))
				a[i][j] = 1

- Prateek Caire September 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//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

           
                
            
        }

- Ayad September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
	}
}

- smffap March 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Konstantin February 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

}

- megha January 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

- Anonymous September 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No.

You n will have log n bits, while you require row and col to have n and m bits.

Yes?

- Anonymous September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh yeah..you r right..

- Anonymous September 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

<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>

- abhrajuit September 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ignore the upper program pls...

- abhrajuit September 04, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More