Microsoft Interview Question for Software Engineers


Country: United States




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

With space complexity of O(1), it got a little trickier.

I can think of 2 approaches:
1. Use a Point Class for matrix, with int oldvalue and int newvalue as variables. Initially both values will be the same. We only retrieve and set newvalue, that way we can check for zero in the oldvalue.

2. If we are not allowed to have point class then we would have to set zeros as we go along.

While we are traversing the matrix, for each point first CheckIfPrevRowsAreZero()
i.e check if a[0][j]..a[i-1][j] are zeros, if they are then set a[i][j] to zero. Once we are done with that check and if prev. rows are not zero then check if value of a[i][j] is zero, if it is set all the values in that row to zero and skip the row and go to the next one right away then repeat.
Running time is not that great. Its O(n^3)

- justaguy September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If we have O(1) space, I only came up with the solution using 2 passes (can it be improved ?)

the basic idea is: we need to choose some "junk" row and column to save the locations
of 0s in them. These junk row/col can be any that will be zeroed out anyway. Then in the 2nd pass, we just go over the whole matrix once again and zero out elements based on 0 pattern in our "junk" row/col:

#define NROWS 5
#define NCOLS 5

int A[NROWS][NCOLS] = {
    {1,1,1,0,1},
    {1,1,0,1,1},
    {1,1,1,1,1},
    {1,0,1,0,1},
    {1,1,1,1,1}};
    
void print_matrix() {
    printf("A = \n");
    for(int i = 0; i < NROWS; i++) {
        for(int j = 0; j < NCOLS; j++){
            printf("%d ", A[i][j]);
        }
        printf("\n");
    }
    printf("\n\n");
}
    
void compute() {
    // these row/col will be used to keep track of zeros in the matrix
    int junk_row = -1,
        junk_col = -1;
    
    for(int i = 0; i < NROWS; i++) {
        for(int j = 0; j < NCOLS; j++) {
            if(A[i][j] == 0) {
                // choose our junk row/col if they are not set yet
                if(junk_row == -1) {
                    junk_row = i;
                    junk_col = j;
                }
                // set markers where we need to zero out
                A[junk_row][j] = 0;
                A[i][junk_col] = 0;
            }
        }
    }

    if(junk_row != -1) {
        for(int i = 0; i < NROWS; i++) {
            for(int j = 0; j < NCOLS; j++) {
                // do not zero-out junk column/row !!
                if(j == junk_col || i == junk_row)
                    continue;
                A[i][j] &= (A[junk_row][j] & A[i][junk_col]);
            }
        }    
        // zero-out junk column/row
        for(int i = 0; i < NROWS; i++) 
            A[i][junk_col] = 0;
        for(int j = 0; j < NCOLS; j++) 
            A[junk_row][j] = 0;
    }
}


int main() {
    print_matrix();
    compute();
    print_matrix();
    return 1;
}

- pavel.em October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cant we use recursion,,i can do it by recursion

- Bridge September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

elaborate?

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

Can't use recursion as that's O(n) stack space and our space constraints are in-place or O(1).

- unordered_map October 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in two passes and O(1) space.

- Noobie September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We could use the weighted quick-union with path compression to accomplish this task.

- riaz.2012 September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you give some more information on your approach?

are you suggesting to use disjoint set...will it not be O(n) space?

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

can you give some more information on your approach
are you suggesting to use disjoint set? will it not be O(n) space?

- codealtecdown September 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't we make an array of pointers for the first element in each row that we need to 0 out and another array of pointers for each column and then use the pointers to 0 out the needed rows and columns

- twhite October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Couldn't we make an array of pointers for the first element in each row that we need to 0 out and another array of pointers for each column and then use the pointers to 0 out the needed rows and columns

- twhite October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The trick here is how to remember which cells had zeros in the original matrix vs which cells were set by the function/method as
we traverse along the metrix row by row.
We would violate the space O(1) constraint if we use a new data structure for this purpose.
So solution for this is a combination of the following actions
1. Replace zeros in cells not traversed yet with -1 when we set row or column to zero.
2. When we encounter a -1 later as we traverse, we will check whether the row or column was set to zero previously to confirm whether the -1 was a zero we memorized or whether it is a -1 in the originzl matrix.
3. Use the first row to keep track whether a column was set to zero or not.
4. Since we use the first row to keep track zero columns, we first check whether the first row has any zeros to begin with
5. after processing and setting all rows, set the first row to zero if there were any zeros at the begining

pseudocode
1. traverse first row
2. if there is a zero in a column
3. set firstRowHasZero = true
4. set non zero values in column to zero and zero values to -1
5. traverse each remaining row
6. set rowAlreadyReset = false
7. if a zero is in a column
8 or if (-1 is in a column and firstrow[column] has zero) //the column was set to zero and the current cell has a original zero
9 or if (-1 is in a column and rowAlreadyReset) //the row was set to zero and the current cell has a original zero
10. set rowAlreadyReset = true
11. set non zero values in column to zero and non visited zero values to -1
12. set non zero values in row to zero and non visited zero values to -1
13. if firstRowHasZero
14. set first row to zero

C# implementation

public int[,] ProcessMatrix(int[,] matrix)
{
    const int firstRow = 0; //used for code readability
    const int firstColumn = 0; //used for code readability

    int lookupValue = 0; //Value to find
    int altLookupValue = -1; //Value used to memorize original zeros not parsed yet

    int row = firstRow;
    int column;

    int rowCount = matrix.GetLength(0);
    int columnCount = matrix.GetLength(1);

    bool rowAlreadyReset = false; //used to avoid repeated rewrite of zero
    bool firstRowHasZero = false;

    if (rowCount > 0)
    {
        //Check whether first row has zero and also set columns to zero if zero encountered
        for (column = firstColumn; column < columnCount; column++)
        {
            if (matrix[row, column] == lookupValue) //original zero encountered
            {
                firstRowHasZero = true;
                //Set down cells to 0 if non zero and -1 if zero
                AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);
            }
        }
        //Process second row onwards
        for (row++; row < rowCount; row++)
        {
            rowAlreadyReset = false;
            for (column = firstColumn; column < columnCount; column++)
            {
                //check whether the column was previously identified to have zero
                bool columnAlreadyReset = (matrix[firstRow, column] == lookupValue);

                //Is the cell an Original Zero
                if (((matrix[row, column] == lookupValue) //found a 0
                        && (!(rowAlreadyReset //this zero is not due to a row reset
                                || columnAlreadyReset) //or column reset
                        )
                    )
                    || ((matrix[row, column] == altLookupValue) //found a -1
                        && (columnAlreadyReset //is this -1 due to a column reset 
                            ||(rowAlreadyReset)) //or a row reset
                    )) 
                {//found a original 0
                    if (!rowAlreadyReset)
                    {
                        //set all left cells to zero
                        ResetCellsInRow(matrix, row, firstColumn, column);
                        //Set right cells to 0 if non zero and -1 if zero
                        AltResetCellsInRow(matrix, row, column + 1, columnCount, altLookupValue);
                        rowAlreadyReset = true;
                    }
                    else if (!columnAlreadyReset)
                    {
                        //Set all cells above to zero, this will flag column reset because it update row 1
                        ResetCellsInColumn(matrix, column, firstRow, row);
                        //Set down cells to 0 if non zero and -1 if zero
                        AltResetCellsInColumn(matrix, column, row + 1, rowCount, altLookupValue);                                
                    }
                    //make sure we overwrite temporary -1 values
                    matrix[row, column] = 0;
                }
            }
        }
        if (firstRowHasZero)
        {
            //set all records in the first row to zero if first row had zeros orignially
            for (column = firstColumn; column < columnCount; column++)
            {
                matrix[firstRow, column] = lookupValue;
            }
        }
    }
    return matrix;
}

//Set the value of all cells between start index and end index in the row to zero
private void ResetCellsInRow(int[,] matrix, int row, int start, int end)
{
    for (; start < end; start++)
    {
        matrix[row, start] = 0;
    }
}
//Set the non zero value of all cells between start index and end index in the row 
//to zero. Set zero values to -1  to memorize it for latter processing
private void AltResetCellsInRow(int[,] matrix, int row, int start, int end, int altValue)
{
    for (; start < end; start++)
    {
        //If the cell is zero then set it to -1 to memorize it for latter processing
        if (matrix[row,start] == 0)
        {
            matrix[row, start] = altValue;
        }
        else
        {
            matrix[row, start] = 0;
        }
    }
}
//Set the value of all cells between start index and end index in the column to zero
private void ResetCellsInColumn(int[,] matrix, int column, int start, int end)
{
    for (; start < end; start++)
    {
        matrix[start, column] = 0;
    }
}
//Set the non zero value of all cells between start index and end index in the column 
//to zero. Set zero values to -1  to memorize it for latter processing
private void AltResetCellsInColumn(int[,] matrix, int column, int start, int end, int altValue)
{
    for (; start < end; start++)
    {
        //If the cell is zero then set it to -1 to memorize it for latter processing
        if (matrix[start, column] == 0)
        {
            matrix[start, column] = altValue;
        }
        else
        {
            matrix[start, column] = 0;
        }
    }
}

- IC October 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a rather straightforward java solution which avoids recursion and runs in optimal time proportional to the size of the matrix(the number of elements).

public static void processMatrix(int[][] matrix) {
		Set<Integer> visitedCol = new HashSet<>();
		Set<Integer> visitedRow = new HashSet<>();
		
		for (int row = 0; row < matrix.length; row++) {
			if (visitedRow.contains(row)) continue;
			for (int col = 0; col < matrix[row].length; col++) {
				if (visitedCol.contains(col)) continue;
				if (matrix[row][col] == 0) {
					setEachRowEntryToZero(row, matrix);
					setEachColEntryToZero(col, matrix);
					visitedRow.add(row);
					visitedCol.add(col);
					break;
				}
			}
		}
	}
	
	private static void setEachRowEntryToZero(int row, int[][] matrix) {
		for (int i = 0; i < matrix[row].length; i++) {
			matrix[row][i] = 0;
		}
	}
	
	private static void setEachColEntryToZero(int col, int[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			matrix[i][col] = 0;
		}
	}

- Anonymous October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a rather straightforward java solution which runs in time proportional to the number of entries in the matrix.

public static void processMatrix(int[][] matrix) {
		Set<Integer> visitedCol = new HashSet<>();
		Set<Integer> visitedRow = new HashSet<>();
		
		for (int row = 0; row < matrix.length; row++) {
			if (visitedRow.contains(row)) continue;
			for (int col = 0; col < matrix[row].length; col++) {
				if (visitedCol.contains(col)) continue;
				if (matrix[row][col] == 0) {
					setEachRowEntryToZero(row, matrix);
					setEachColEntryToZero(col, matrix);
					visitedRow.add(row);
					visitedCol.add(col);
					break;
				}
			}
		}
	}
	
	private static void setEachRowEntryToZero(int row, int[][] matrix) {
		for (int i = 0; i < matrix[row].length; i++) {
			matrix[row][i] = 0;
		}
	}
	
	private static void setEachColEntryToZero(int col, int[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			matrix[i][col] = 0;
		}
	}

- Anon October 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>

typedef std::vector<int> ROW_TYPE;
typedef std::vector<ROW_TYPE> MATRIX_TYPE;

void MakeMatrixColoumnValuesZero(MATRIX_TYPE& matrix, int i, int j)
{
    for (int k = i - 1; k >= 0; --k)
    {
        matrix[k][j] = 0;
    }
}

void MakeMatrixRow0(MATRIX_TYPE& matrix, int i)
{
    int coloumnCount = matrix[0].size();
    for (int j = 0; j < coloumnCount; ++j)
    {
        matrix[i][j] = 0;
    }
}

int FindLastIndexInMatrixColoumnThatIsZero(const MATRIX_TYPE& matrix, int j)
{
    int rowCount = matrix.size();

    for (int i = 0; i < rowCount; ++i)
    {
        if (matrix[i][j] != 0)
        {
            return i - 1;
        }
    }
}

void ProcessMatrix(MATRIX_TYPE& matrix)
{
    int rowCount = matrix.size();
    int coloumnCount = matrix[0].size();
    
    for (int i = 0; i < rowCount; ++i)
    {
        for (int j = 0; j < coloumnCount; ++j)
        {
            if (matrix[i][j] == 0)
            {
                MakeMatrixColoumnValuesZero(matrix, i, j);
            }
        }
    }

    for (int i = 0; i < rowCount; ++i)
    {
        for (int j = 0; j < coloumnCount; ++j)
        {
            if (matrix[i][j] == 0 && i == FindLastIndexInMatrixColoumnThatIsZero(matrix, j))
            {
                MakeMatrixRow0(matrix, i);
                MakeMatrixColoumnValuesZero(matrix, rowCount, j);
            }
        }
    }    
}

int main()
{
    MATRIX_TYPE matrix;
    ROW_TYPE row = { 1, 2, 3, 4, 5 };
    matrix.push_back(row);
    row = { 2, 0, 4, 6, 6 };
    matrix.push_back(row);
    row = { 2, 3, 4, 0, 6 };
    matrix.push_back(row);
    row = { 2, 7, 4, 6, 6 };
    matrix.push_back(row);
    row = { 2, 7, 4, 6, 6 };
    matrix.push_back(row);

    int rowCount = matrix.size();
    int coloumnCount = matrix[0].size();


    for (int i = 0; i < rowCount; ++i)
    {
        for (int j = 0; j < coloumnCount; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    std::cout << std::endl;

    ProcessMatrix(matrix);

    for (int i = 0; i < rowCount; ++i)
    {
        for (int j = 0; j < coloumnCount; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

}

- This is in two passes and O(1) space October 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use one integer O(n) in binary format (e.g.: 0b01101) to save which row or columns need to be set to zero during first full scan. Position 0->N used for columns, and N+1->M for rows, and 1 means to set to zero. And with the integer we can set the rows/columns to zero directly. The sample code is below:

int pos = 0; // Low bits for columns
            for (int r = 0; r < rows; r++)
            {
                for (int c = 0; c < cols; c++)
                {
                    if (matrix[r][c] == 0)
                    {
                        // Save bits
                        pos |= (1 << c);
                        pos |= (1 << (r + cols));
                    }
                }
            }

            for (int c = 0; c < cols && pos > 0; c++)
            {
                if (0 < (pos & (1 << c)))
                {
                    for (int r = 0; r < rows; r++)
                    {
                        matrix[r][c] = 0;
                    }
                }
            }

            for (int r = 0; r < rows && pos > 0; r++)
            {
                if (0 < (pos & (1 << (cols + r))))
                {
                    for (int c = 0; c < cols; c++)
                    {
                        matrix[r][c] = 0;
                    }
                }
            }

- renbin October 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.shortestPath;

public class CodeMatrix {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

int m[][]={{1,   2 ,  3,1},{5 ,  6,   0,1 },{9,   10,  1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1; 
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
	System.out.println("==="+i+":::::"+j);
    if(m[i][j]==0)
       {
    	
         while(flag)
          {
        	 //System.out.println(col+"::"+n+":::::"+j); 
        	 try{
            f[i][col]=0; 
        	 }
        	 catch(Exception e){
        		 
        	 }
        	 try{
            f[n][j]=0 ; 
        	 }
        	 catch(Exception e){
        		 
        	 }
               col--;
               n--;
               max--;
               if(max<0)flag=false;
               
          }

           

       }
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
	
{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
	}

}

- kirti............ December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.shortestPath;

public class CodeMatrix {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

int m[][]={{1,   2 ,  3,1},{5 ,  6,   0,1 },{9,   10,  1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1; 
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
	System.out.println("==="+i+":::::"+j);
    if(m[i][j]==0)
       {
    	
         while(flag)
          {
        	 //System.out.println(col+"::"+n+":::::"+j); 
        	 try{
            f[i][col]=0; 
        	 }
        	 catch(Exception e){
        		 
        	 }
        	 try{
            f[n][j]=0 ; 
        	 }
        	 catch(Exception e){
        		 
        	 }
               col--;
               n--;
               max--;
               if(max<0)flag=false;
               
          }

           

       }
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
	
{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
	}

}

- kirti............ December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class CodeMatrix {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

int m[][]={{1,   2 ,  3,1},{5 ,  6,   0,1 },{9,   10,  1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1; 
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
	System.out.println("==="+i+":::::"+j);
    if(m[i][j]==0)
       {
    	
         while(flag)
          {
        	 //System.out.println(col+"::"+n+":::::"+j); 
        	 try{
            f[i][col]=0; 
        	 }
        	 catch(Exception e){
        		 
        	 }
        	 try{
            f[n][j]=0 ; 
        	 }
        	 catch(Exception e){
        		 
        	 }
               col--;
               n--;
               max--;
               if(max<0)flag=false;
               
          }

           

       }
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
	
{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
	}

}

- kirti............ December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int m[][]={{1,   2 ,  3,1},{5 ,  6,   0,1 },{9,   10,  1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1; 
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
	System.out.println("==="+i+":::::"+j);
    if(m[i][j]==0)
       {
    	
         while(flag)
          {
        	 //System.out.println(col+"::"+n+":::::"+j); 
        	 try{
            f[i][col]=0; 
        	 }
        	 catch(Exception e){
        		 
        	 }
        	 try{
            f[n][j]=0 ; 
        	 }
        	 catch(Exception e){
        		 
        	 }
               col--;
               n--;
               max--;
               if(max<0)flag=false;
               
          }

           

       }
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
	
{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
	}

- Kirti December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{

while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){

}
try{
f[n][j]=0 ;
}
catch(Exception e){

}
col--;
n--;
max--;
if(max<0)flag=false;

}



}
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)

{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
}

- Kirti December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int m[][]={{1, 2 , 3,1},{5 , 6, 0,1 },{9, 10, 1,1}};
int r=3;
int c=4;
int max=0;
if(r>c)max=r;else max=c;

int f[][]=m;
int n=r-1;
int col=c-1;
boolean flag=true;
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
System.out.println("==="+i+":::::"+j);
if(m[i][j]==0)
{

while(flag)
{
//System.out.println(col+"::"+n+":::::"+j);
try{
f[i][col]=0;
}
catch(Exception e){

}
try{
f[n][j]=0 ;
}
catch(Exception e){

}
col--;
n--;
max--;
if(max<0)flag=false;

}



}
}
}


for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)

{

System.out.print(" "+f[i][j]);

}
System.out.println(" ");
}
}

- Kirti December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

jghjkhyi

- Anonymous December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Are you sure this is possible? I don't think you can do it in just one pass. You can't set the elements in a row and column to zero as you go. If you do, you'll just end up setting the entire matrix to 0

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

You are right, I don't see how we can solve this in a single pass. I think the solution I suggested does it in 2 passes. There's an O(n^2) solution as well but that too doesn't solve it in a single pass.

- justaguy September 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The interviewer was pretty sure that it is possible.

- codealtecdown September 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

with the help of recursion i can read once each array and put it in stack and once i find a zero i will go on writing till the length of i and j and agin from the position i found the zero till the recursion stack is empty

- bridge September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

But the space complexity wouldn't be on O(1), in your case it would be O(n).

- justaguy September 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

recursion is not allowed. its O(n) on stack

- codealtecdown September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This seems like one of those really impossible questions to see how you squirm...

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

I think this is a trick. If one element in the matrix is 0, then the entire matrix will have only zeros. So just search for a zero and return a matrix with zeros.

- Hari Krishna September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Hari Krishna
I don't get your point. If one element is 0, why would the entire matrix be only zeros? Only that row and column should be 0.

- codealtecdown September 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

ArrayList colArr = new ArrayList();
for(int row = 0; row< totalRows; row++)
{
	for(int col= 0; col< totalCols; col++)
	{
		if ( matrix[i][j] == 0)
		{
			makeRowZero(row);
			colArr.add(col);
			break;
		}
	}
}

makeColZero(colArr );

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

That's O(n) space, isn't it?

- yayaha October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If it is o(n) memory, then lets do this:

1. Create an array of same size, say n * n, with all elements set to logic 1. Let's call it array B.

2. Iterate through every element in the initial matrix, lets call it array A. When see a zero, set the corresponding entry in B matrix to zero, and also every element in the same row and column in B.

3. And matrix A and B. This should set all the right entries in A to zero.

It is doing more than one pass on B for sure, but only one pass on A. Hahaha

- H.W September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this isnt space complexity of O(1)

- Marwan October 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this isnt space complexity of O(1)

- Marwan October 09, 2015 | 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