Microsoft Interview Question Tech Leads
Team: Bing
Country: India
Interview Type: In-Person
Working code in c++.
void MakeZeroRowCol(vector< vector<int> >& V)
{
int rows = V.size();
int cols = V[0].size();
int row[rows];
int col[cols];
for(int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (V[i][j] == 0)
{
row[i] = 0;
col[j] = 0;
}
}
}
for(int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (row[i] == 0 || col[j] == 0)
{
V[i][j] = 0;
}
}
}
for(int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
cout << B[i][j] << ", ";
}
cout << endl;
}
}
What do you mean by traverse? Because you can traverse matrix in different ways.
For example if you traverse it from top-left corner to down right going row by row you can do this by looking for first 0. Ones you meet it that is it, just fill all columns right to it with 0 and all rows below it with 0. I mean
if A[i][j] == 0 then A[k][l] = 0 if k>=i || l >=j
Find the first ZERO element in the matrix, then when we find, the make that row and column to ZERO's, then choose either the row or column, then make the rest ZERO's since we have already made the ZERO's, but finding the first ZERO is the catch !.
What do you say ?
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_ROW 5
#define MAX_COL 6
void print_matrix(int matrix[MAX_COL][MAX_ROW])
{
int i=0,j=0;
for (i=0;i<MAX_COL;i++)
{
for(j=0;j<MAX_ROW;j++)
{
printf(" %d",matrix[i][j]);
}
printf("\r\n");
}
printf("\r\n");
}
void main()
{
int matrix[MAX_COL][MAX_ROW] =
{{1,1,1,1,1},
{1,1,1,1,1},
{1,1,0,1,1},
{1,1,1,0,1},
{1,1,1,1,1},
{1,1,1,1,1}};
int i=0,j=0;
char a;
print_matrix(matrix);
for (i=0;i<MAX_COL;i++)
{
for(j=0;j<MAX_ROW;j++)
{
if(matrix[i][j] == 0)
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// print_matrix(matrix);
for (i=0;i<MAX_COL;i++)
{
if(matrix[i][0] == 0)
{
for(j=0;j<MAX_ROW;j++)
{
matrix[i][j] = 0;
}
}
}
for (j=0;j<MAX_ROW;j++)
{
if(matrix[0][j] == 0)
{
for(i=0;i<MAX_COL;i++)
{
matrix[i][j] = 0;
}
}
}
print_matrix(matrix);
scanf("%c",&a);
// getch();
}
Pseudo:
1. let M be a bits array of size of m
2. let N be a bits array of size of n
3. traverse through all of the matrix' cells:
3.1 for each cell[i, j] that its value is 0 do
3.1.1 set M[i] <- 1
3.1.2 set N[j] <- 1
4. traverse array M:
4.1 for each M[i] equals 1 do
4.1.1 set col i on matrix to 0
5. traverse array N:
5.1 for each N[j] equals 1 do
5.1.1 set row j on matrix to 0
running time := n*m + n + m + n*m + m*n = O(m*n)
memory cost := 2 additional arrays = m + n
Time complexity O(m*n)
Space complexity O(1)
The basic idea is to use space inside the matrix itself to mark whether to set a column/row to zero, thus avoiding extra space cost.
void setZeroes(vector<vector<int> > &matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return;
}
//special variable to record whether to set the first column 0
int column1 = 1;
for (int i = 0 ; i < matrix.size() ; i++) {
if (matrix[i][0] == 0) {
column1 = 0;
}
for (int j = 1 ; j < matrix[i].size() ; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//set columns to zero except column1
for (int i = 1 ; i < matrix[0].size() ; i++) {
if (matrix[0][i] == 0) {
for (int j = 1 ; j < matrix.size() ; j++) {
matrix[j][i] = 0;
}
}
}
//set rows to zero
for (int i = 0 ; i < matrix.size() ; i++) {
if (matrix[i][0] == 0) {
for (int j = 1 ; j < matrix[i].size() ; j++) {
matrix[i][j] = 0;
}
}
}
//set first column
if (column1 == 0) {
for (int i = 0 ; i < matrix.size() ; i++) {
matrix[i][0] = 0;
}
}
}
public void Matrix0s(int[,] A, int n, int m)
{
List<int> r = new List<int>();
List<int> c = new List<int>();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (A[i,j] == 0)
{
if (!r.Contains(i))
r.Add(i);
if (!c.Contains(j))
c.Add(j);
}
}
}
for (int i = 0; i < r.Count(); i++)
{
for (int j = 0; j < m; j++)
A[r[i], j] = 0;
}
for (int i = 0; i < c.Count(); i++)
{
for (int j = 0; j < n; j++)
A[j,c[i]] = 0;
}
}
Uses boolean arrays, but can be substituted for bit vector.
m below the matrix - int[][]
boolean zeroRow[] = new boolean[m.length];
boolean zeroCol[] = new boolean[m[0].length];
for (int row = 0; row < m.length; row++) {
// if this row is a zero row, skip it
if (zeroRow[row]) {
continue;
}
for (int col = 0; col < m[0].length; col++) {
// if this col is a zero row or col skip it
if (zeroRow[row] || zeroCol[col]) {
continue;
}
// if we are here, then let's check the element value
if (m[row][col] == 0) {
zeroRow[row] = true;
zeroCol[col] = true;
// make all elements in the above row,col zero
// row elements
for (int i = 0; i < m[0].length; i++) {
m[row][i] = 0;
}
// col elements
for (int i = 0; i < m.length; i++) {
m[i][col] = 0;
}
}
}
}
1. First record the number of 0's in rows and columns by initializing rows[array.length] and columns[array[0].length]
- BoredCoder December 19, 20122. Now,
for(r=0; r<array.length; r++)
for(c=0; c<array[0].length; c++)
if(array[r][c] == 0)
columns[c] = 1;
rows[r] = 1;
3. Next step;
for(int r=0; r<rows.length; r++)
for(int c=0; c<columns.length; c++)
if(rows[r] == 1 || columns[c] == 1)
array[r][c] = 0;
Time-complexity: Linear O(mn); two times sweep of the entire 2d array
Space-Complexity: Num of column + Num of rows - O(m+n)