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

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

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

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

Comment hidden because of low score. Click to expand.
0

elaborate?

Comment hidden because of low score. Click to expand.
0

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

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

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

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

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
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
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++)
{
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
)
)
|| ((matrix[row, column] == altLookupValue) //found a -1
&& (columnAlreadyReset //is this -1 due to a column reset
))
{//found a original 0
{
//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);
}
{
//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;
}
}
}``````

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

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

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

}

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

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

}``````

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

}``````

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

}``````

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

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

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

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

jghjkhyi

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

The interviewer was pretty sure that it is possible.

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

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

makeColZero(colArr );``````

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

this isnt space complexity of O(1)

Comment hidden because of low score. Click to expand.
0

this isnt space complexity of O(1)

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.

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