## Microsoft Interview Question

• 0

Country: United States

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

Assuming matrix is 0-based, i.e. the first element is at mat

1. Use the first row and first column as table headers to contain row and column info respectively.
1.1 Note the element at mat. If it is 1, it will require special handling at the end (described later)
2. Now, start scanning the inner matrix from index up to the last element
2.1 If the element at[row][col] == 1 then update the table header data as follows
Row: mat[row] = 1;
Column: mat[col] = 1;
At this point we have the complete info on which column and row should be set to 1
3. Again start scanning the inner matrix starting from mat and set each element
to 1 if either the current row or column contains 1 in the table header:
if ( (mat[row] == 1) || (mat[col] == 1) ) then set mat[row][col] to 1.

At this point we have processed all the cells in the inner matrix and we are
yet to process the table header itself
If the matt == 1 then set all the elements in the first column and first
row to 1
5. Done

Time complexity O(2*((n-1)(m-1)+(n+m-1)), i.e. O(2*n*m - (n+m) + 1), i.e. O(2*n*m)
Space O(1)

And here is the link to my iplementation of the above algo:

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

ans should be same for this matrix also

0 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

but according to ashot's algo ans is cmng wrong

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

Keep two extra variables isRow and isColumn. For the first row and the column if there is a one, mark the corresponding bool value. Use this to update the row and column values in the end.

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

Hello Mrs. Dear Achillies,
Nice idea though...but it will not work in case of -ve integers...

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

This code will fail for following case:
0 1 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Please correct me if I am wrong

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

ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1315147537

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

1. use first as a bit map: bit 0 - there is 1's in column 0; bit 1 - there is 1's in row 0.
2. for each arr(i,j), where i,j > 0, if it is 1, set arr(0,j) and arr(i,0) to 1.
3. for each arr(i,j), where i,j > 0, if arr(0,j) or arr(i,0) is 1, set it to 1.
4. if bit 0 in first is 1, set all the elements in the column 0 to 1; if bit 1 in first 1, set all the elements in the row 0 to 1.
5. print out the 2d array.

O(2n*m) time and O(1) space

``````int[][] arr= new int[][] {{0,1,0,0}, {0,1,0,0}, {0,0,0,0}, {1,0,0,0}, {0,1,1,0}};
int first = 0;
for (int i = 0; i<arr.length; i++)
if (arr[i] == 1) first |= 1;
for (int i = 0; i<arr.length; i++)
if (arr[i] == 1) first |= 2;

for (int row = 1; row < arr.length; row++) {
for (int col = 1; col < arr.length; col++) {
if (arr[row][col]==1) {
arr[col] = 1;
arr[row] = 1;
}
}
}

for (int i=1; i<arr.length; i++) {
for (int j=1; j<arr.length; j++) {
if (arr[j] == 1 || arr[i] == 1) arr[i][j] = 1;
}
}
if ((first & 1) != 0) for (int i = 0; i<arr.length; i++) arr[i] = 1;
if ((first & 2) != 0) for (int i = 1; i<arr.length; i++) arr[i] = 1;

for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr.length; j++) {
System.out.print(arr[i][j] + ",");
}
System.out.println();
}``````

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

Could you plz write down the algorithm in words rather than the code...understanding the code takes more time...

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

Find out which are the intersections of zero rows and columns.

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

``````char[][] arr= new char[][] {{'1','1','0','1'}{ '0','0','0','0'}{ '0','0','0','1'}{ '0','0','0','1'}{ '0','1','1','0'}};
for (int row = 0; row < arr.length; row++) {
for (int col = 0; col < arr[row].length; col++) {
if(arr[row][col]=='1')
{
for(int j=0;i<arr[row].length;j++)
if(a[row][j]=='0')
a[row][j]^=arr[row][col];
break;
}
} }``````

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

Sorry for wrong answer.The xor operation here with chars is not correct.

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

``````int[][] arr= new int[][] {{1,1,0,1}{ 0,0,0,0}{ 0,0,0,1}{ 0,0,0,1}{ 0,1,1,0}};
for (int row = 0; row < arr.length; row++) {
for (int col = 0; col < arr[row].length; col++) {
if(arr[row][col]==1)
{
for(int j=0;i<arr[row].length;j++)
if(a[row][j]==0)
a[row][j]^=arr[row][col];
break;
}
} }``````

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

i think the complexity is O(n*n*m) and we require O(n*m)

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

``````public static void updateMatrix(int a[][]) {
int N = a.length;
int M = a.length;

int a1[] = new int[N];// N
int b1[] = new int[M];// M

int i = 0, j = 0;
//We store the 'OR' of rows in a1 and 'OR' of coulmns in b1
for (i = 0; i < N; ++i)
for (j = 0; j < M; ++j) {
a1[i] |= a[i][j];
b1[j] |= a[i][j];
}
//update the original array with a1|b1
for (i = 0; i < N; ++i)
for (j = 0; j < M; ++j) {
a[i][j] = a1[i] | b1[j];
}
}``````

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

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

Yes you are right this soln is not O(1). One change is to use a bit set to reduce the memory instead of the in array I have used.To keep it O(1), we can use the two bit set vectors of size 2^31-1, assuming the size of N and M are 32 bit, and this will remain constant irrespective of M and N values.. But this is not a good solution, since it will use a lot of memory even if the M and N are small. I cant think of any better O(1) space soln.

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

Use bitset class in c++. This will save the space too.

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

two way solving would if we forget the condition right now would be
1) take a bit array of o(n) as soon. start traversing row-wise. As soon as u get a 1 make all elements of row as 1. and also make bit_arr[i]=1. After row 1 check for the current element and bit_array[i] for 1. So complexity o(n*m) space complexity o(n)

2) second way is trivial solution in to traverse the matrix and each time find a 1 go to all the elements in the row and column and make them 1. Hell complexity

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

stackoverflow.com/questions/10840044/microsoft-interview-transforming-a-matrix

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

I guess this only needs O(nm) time and no extra space. Isn't it obvious this has to be the element which falls on the intersection of an all zero row and an all zero column?

If you want explanation: What exactly is happening in this situation if a position i,j has a 1 then the ith row and the jth column is transformed to all 1s.

So which element will be untouched? The one which lies in the all zero rows and all zero columns. Hence the one at the intersection.

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

Yes you're right but how would you do it in O(m*n)? You need two extra inner loops to traverse through the corresponding ith row and jth column.

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

1. Take the dot product of each row by itself and take its minimum with 1, this way we obtain 1 or 0 and we can make up bit by bit an unsigned integer (call it RowElements)

2. Repeat the same with columns (call it ColElements). In this way the storage requirement is 2 integers.

3. Now we set all entries in the matrix to be 1 except those where RowElements bit =0 and ColElements bit =0

Why: A*A'=0 only if we have a row of zeroes and A'*A=0 only for a column of zeroes. (transpose is A')

( we do not need actually dot product but the solution can be justified nicely this way, we can just get the bits together in one integer and if it is nonzero the corresponding bit in the auxiliary integer is set to 1, and if it is 0 then it is set to 0).

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

use of first row and column in matrix to remember whether this row/col should be marked all ones'

``````void fill_matrix_row_col(int **m, int h, int w){
if(!m || !h || !w) return;
bool rowones=false, colones=false;
for(int i=0;i<h;++i)
if(m[i]){
colones=true;
break;
}
for(int j=0;j<w;++j)
if(m[j]){
rowones=true;
break;
}
for(int i=1;i<h;++i){
for(int j=1;j<w;++j){
if(m[i][j]) m[j]=m[i]=1;
}
}
for(int i=1;i<h;++i){
for(int j=1;j<w;++j)
if(m[i] || m[j]) m[i][j]=1;
}
for(int i=0;i<h;++i)
if(colones)
m[i]=1;
else
m[i]=0;
for(int j=0;j<w;++j)
if(rowones)
m[j]=1;
else
m[j]=0;

}``````

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

``````package com.careercup.book.four.one;

public class MatrixTransformer {

private int[][] a;
private int m;
private int n;

public MatrixTransformer(int[][] _a, int _m, int _n) {
a = _a;
m = _m;
n = _n;
}

private int scanRow(int i) {
int allZero = 0;
for (int k = 0; k < n; k++)
if (a[i][k] == 1) {
allZero = 1;
break;
}

return allZero;
}

private int scanColumn(int j) {
int allZero = 0;
for (int k = 0; k < m; k++)
if (a[k][j] == 1) {
allZero = 1;
break;
}

return allZero;
}

private void setRowToAllOnes(int i) {
for (int k = 0; k < n; k++)
a[i][k] = 1;
}

private void setColToAllOnes(int j) {
for (int k = 0; k < m; k++)
a[k][j] = 1;
}

// # we're going to use the first row and column
// # of the matrix to store row and column scan values,
// # but we need aux storage to deal with the overlap
// firstRow = scanRow(0)
// firstCol = scanCol(0)
//
// # scan each column and store result in 1st row - O(mn) work

public void transform() {
int firstRow = scanRow(0);
int firstCol = scanColumn(0);

for (int k = 0; k < n; k++) {
a[k] = scanColumn(k);
}

// now row 0 tells us whether each column is all zeroes or not
// it's also the correct output unless row 0 contained a 1 originally

for (int k = 0; k < m; k++) {
a[k] = scanRow(k);
}

a = firstCol | firstRow;

for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
a[i][j] = a[j] | a[i];

if (firstRow == 1) {
setRowToAllOnes(0);
}

if (firstCol == 1)
setColToAllOnes(0);
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(a[i][j] + ", ");
}
sb.append("\n");
}

return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
int[][] a = { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0 }, { 1, 0, 1, 1, 0 } };
MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
mt.transform();
System.out.println(mt);
}

}``````

Source: stackoverflow.com/questions/10840044/microsoft-interview-transforming-a-matrix

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

for(i=0;i<row;i++)
for(j=0;j<coloum;j++)
if (A[i][j] = =1)
row_col_fill(A,i,j,row,coloum);

for(i=0;i<row;i++)
for(j=0;j<coloum;j++)
if (A[i][j] = =2)
A[i][j] = 1;

void row_col_fill( int *A , int i,intj,int row,int coloum)
{
for(o=0;o<coloum;o++)
A[i][o] = 2;
for(o=0;o<row;o++)
A[o][j] = 2;
}

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

i guess the solution given by dharmendra is perfect :
there is no point pasting code .. just explain your algorithm , others can easily code your algorithm ..

I guess this only needs O(nm) time and no extra space. Isn't it obvious this has to be the element which falls on the intersection of an all zero row and an all zero column?

If you want explanation: What exactly is happening in this situation if a position i,j has a 1 then the ith row and the jth column is transformed to all 1s.

So which element will be untouched? The one which lies in the all zero rows and all zero columns. Hence the one at the intersection.

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

hey buddy ...what u and dharmendra have written is absolutely correct and but obvious..... but the thing is how to code it with O(n*m) and O(1) constraints...just suggesting an algorithm our task is not finished...we have to code it...because that is where we will face difficulty... if you think it is easy to code this problem then please paste your code here..

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TransformMatrix
{
class Program
{
static void Main(string[] args)
{
int[,] A = new int[,] { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0 }, {1, 0, 1, 1, 0} };
Console.WriteLine("Original Matrix:");
DisplayMatrix(A);
TransFormMatrix(A);
Console.WriteLine("\n\nTransformed Matrix:");
DisplayMatrix(A);
}

static void DisplayMatrix(int[,] A)
{
int rows = A.GetLength(0);
int cols = A.GetLength(1);

for (int i = 0; i < rows; i++)
{
Console.WriteLine("\n");
for (int j = 0; j < cols; j++)
{
Console.Write("\t{0}",A[i,j]);
}
}
}

static void TransFormMatrix(int[,] A)
{
int rows = A.GetLength(0);
int cols = A.GetLength(1);
int firstRow = 0;
int firstCol = 0;

for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
if (A[i, j] == 1)
{
if (A[0, j] == 1) firstRow = 1;
A[0, j] = 1;
if (A[i, 0] == 1) firstCol = 1;
A[i, 0] = 1;
}
}
}

for (int i = 1; i < rows; i++)
{
if (A[i, 0] == 1)
{
for (int j = 1; j < cols; j++)
{
A[i, j] = 1;
}
}
}

for (int j = 1; j < cols; j++)
{
if (A[0, j] == 1)
{
for (int i = 1; i < rows; i++)
{
A[i, j] = 1;
}
}
}

if (A[0, 0] == 1)
{
for (int i = 0; i < rows; i++)
{
A[i, 0] = 1;
}

for (int j = 0; j < cols; j++)
{
A[0, j] = 1;
}
}
else
{
if (firstRow == 1)
{
for (int i = 0; i < rows; i++)
{
A[i, 0] = 1;
}
}
if (firstCol == 1)
{
for (int j = 0; j < cols; j++)
{
A[0, j] = 1;
}
}
}

}
}
}``````

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

Assume n,m<=32, my solution use bitmap:
Firstly we need to scan the the matrix and record down which rows and cols need to be set. Then for the second scanning we set the element according to the record done before.

int N, int M;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(a[i][j] == 1) {
N = N | (0x01 << i);
M = M | (0x01 << j);
}
}
}

for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if((N & (0x01 << i)) || (M & (0x01 << j)))
a[i][j] = 1;
}
}

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

The idea is traversing the matrix twice.
The first one starts from cell  and ends at [n-1][m-1]
The next one is just the opposite order.

If you are going down and if a[i][j] is 1, then set these to 1:
a[i][j+1] and a[i+1][j]

If you are going up and if a[i][j] is 1, then set these to 1:
a[i][j-1] and a[i-1][j]

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

public class MatrixZeroColumnRows {

public static void main(String[] args) {

int[][] matrix = { { 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, }, { 0, 1, 0, 0, 0, }, { 1, 0, 1, 1, 0, } };

printMatrix(matrix);

int[] result = zeroIntersection(matrix);

System.out.println(" row number : " + result);
System.out.println("Column number : " + result);

}

public static void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
System.out.print(" " + matrix[i][j] + " ");

}
System.out.println();
}

}

public static int[] zeroIntersection(int[][] matrix) {
int[] arr = new int;
int row = 0;
int column = 0;

for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][j] != 0) {
break;
} else {
row++;
}
}
if (row == matrix.length) {
arr = i;

}
row = 0;

}

for (int j = 0; j < matrix.length; j++) {
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][j] != 0) {
break;
} else {
column++;
}
}
if (column == matrix.length) {
arr = j;

}
column = 0;

}

return arr;
}

}

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

Now once you get the row and column number , fill the matrix with 1 except matrix =0 ;

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.