Microsoft Interview Question Software Engineer / Developers
for (int i=0; i<m;i++){
for (int j = 0; j<n; j++){
if (a[i][j] == 0){
for (int temp = 0;temp<m;temp++)
b[temp][j] = 0;
for (int temp = 0; temp<n;temp++)
b[i][temp] = 0;
}
}
}
for (int i=0;i < m; i++)
for(int j =0; j< n;j++)
a[i][j] = b[i][j]
there is one piece of info i want, consider your example itself, since u have set first row and second column as 0s should u now consider the additional zeros you have insterted as well(for eg: there is now a 0 in (1,1))...if u need to consider this also, then the simplest solution is if u encounter a o anywhere in the matrix, simply make all the elements in the matrix as 0..try it out urself......if however, new zeors should not be considered, then buzz here.......
1) take M+N flags. (init with false)
2) travers all the elements in the matrix once and set the appropriate flages (Mth and Nth flags) to true. when ever you find zero in matrix.
3) go through the each flag and make all the elements in that row or column as zeros when ever you find that flag in set condition as true
here is the solution. i am using 2 hash tables to keep track of which row and column have 0 element.
Void makeZero(int[][] a)
{
int i,j;
int hash_m[M];
int hash_n[N];
for(i=0;i<M;i++)
hash_m[i] = 1;
for(i=0;i<N;i++)
hash_n[i] = 1;
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
if(a[i][j] == 0)
{
hash_m[i] = 0;
hash_n[j] = 0;
}
}
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
if(!(hash_m[i] == 1 && hash_n[j] == 1))
a[i][j] = 0;
}
}
opps. somehow it didn't completely uploaded my code. i will try again.
Void makeZero(int[][] a)
{
int i,j;
int hash_m[M];
int hash_n[N];
for(i=0;i<M;i++)
hash_m[i] = 1;
for(i=0;i<N;i++)
hash_n[i] = 1;
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(a[i][j] == 0)
{
hash_m[i] = 0;
hash_n[j] = 0;
}
}
}
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
if(!(hash_m[i] == 1 && hash_n[j] == 1))
a[i][j] = 0;
}
}
}
i think just storing the column index of the zero & setting rows during the intial look-up will do.
{{
void setZero(int idx, int colMax, int rowMax, bool isRow = true)
{
int max = (isRow)?rowMax:colMax;
for(int i=0; i < max; i++)
{
int curR = (isRow)?idx : i;
int curC = (!isRow)?idx : i;
arr[curR][curC] = 0;
}
}
void matrixZero(int colMax, int rowMax)
{
//column zero index array
int zero[colMax]; //set the array zero to all zeros by memset.
for(int i=0; i < rowMax; i++)
{
for(int j=0; j < colMax; j++)
{
if(arr[i][j]==0)
{
zero[j] = 1;
setZero(arr, i, colMax, rowMax, true);
break;
}
}
}
for(int i=0; i < colMax; i++)
{
if(zero[i]== 1)
{
setZero(i, colMax, rowMax, false);
}
}
}
}}
i think just storing the column index of the zero & setting rows during the intial look-up will do.
void setZero(int idx, int colMax, int rowMax, bool isRow = true)
{
int max = (isRow)?rowMax:colMax;
for(int i=0; i < max; i++)
{
int curR = (isRow)?idx : i;
int curC = (!isRow)?idx : i;
arr[curR][curC] = 0;
}
}
void matrixZero(int colMax, int rowMax)
{
//column zero index array
int zero[colMax]; //set the array zero to all zeros by memset.
for(int i=0; i < rowMax; i++)
for(int j=0; j < colMax; j++)
if(arr[i][j]==0)
{
zero[j] = 1;
setZero(arr, i, colMax, rowMax, true);
break;
}
for(int i=0; i < colMax; i++)
{
if(zero[i]== 1)
setZero(i, colMax, rowMax, false);
}
}
Another Solution:
#include<stdio.h>
int main()
{
int a[10][10];
int i,j,k=0,row[10],col[10],rowi,coli,m;
for(j=0;j<10;j++){
for(i=0;i<10;i++){
a[j][i]=k;
k++;
}
}
printf("\n");
printf("\nThe array elements are\n");
for(j=0;j<10;j++)
{
for(i=0;i<10;i++){
{
printf("%d ",a[j][i]);
}
}
printf("\n");
}
//now let me add some zeros randomly
a[1][3]=0;
a[2][4]=0;
//checking which row and col are zeros
k=0;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
if(0==a[i][j])
{
row[k]=i;
col[k]=j;
k++;
}
// now make the corresponding rows and cols zero
for(i=0;i<k;i++)
{
rowi=row[i];
for(m=0;m<10;m++)
a[rowi][m]=0;
}
for(j=0;j<k;j++)
{
coli=col[j];
for(m=0;m<10;m++)
a[m][coli]=0;
}
printf("\nThe array elements with row column zeros are\n");
for(j=0;j<10;j++)
{
for(i=0;i<10;i++){
{
printf("%d ",a[i][j]);
}
}
printf("\n");
}
return 0;
}
Well take two hashtables for row and column instead of saving the zero positions and later going thru' the array ...
Whenver you see a zero check for the corresponding row and col. in hash table if they are null then add the corresponding row and col.
In this way we are not going to see the row and col which are set to zero previously.
I cogitate this is efficient than the above solutions
void setMatrix(int arr[M][N]){
Hashtable r=new Hashtable();
Hashtable c=new Hashtable();
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(a[i][j]==0 && r.get(i)==NULL || c.get(j)==NULL){
int rval=i,cval=j;
for(int i=0;i<M;i++){
if(r.get(rval)==NULL)
arr[rval][i]==0;
if(c.get(cval)==NULL)
arr[i][cval]==0;
}
r.put(i,1);
c.put(j,1);
}
else if(arr[i][j]=0){
if(r.get(i)==1){
i+=1;
break;
}
else if(c.get(j)==1)
break;
else{
}
}
}
}
}
This will do it in one traverse... Ofcourse we have to traverse the row and column to make zero.
2 hashtables one for row and one for column.
Initially while checking for zero I'm finding out if the corresponding row or column is NULL and the corresponding value is zero ...if so I'm making the corresponding row and column to zero and at the same time I'm saving the row and column in the hashtable with value as 1 and key as the row/column and whenever I find a value zero,I would first see if the particular row and column are set to zero by checking with value in hashtable if 1 break else go ahead. Herez the code,, hope I phrased it right.
void setMatrix(int arr[M][N]){
Hashtable r=new Hashtable();
Hashtable c=new Hashtable();
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(a[i][j]==0 && r.get(i)==NULL || c.get(j)==NULL){
int rval=i,cval=j;
for(int i=0;i<M;i++){
if(r.get(rval)==NULL)
arr[rval][i]==0;
if(c.get(cval)==NULL)
arr[i][cval]==0;
}
r.put(i,1);
c.put(j,1);
}
else if(arr[i][j]=0){
if(r.get(i)==1){
i+=1;
break;
}
else if(c.get(j)==1)
break;
else{
}
}
}
}
}
I am using additional memory but we can do it without using additional memory in that case we will have to scan through the entire array twice..In that case in first scan we replace all zeroes in the array by a special character and in the second scan we replace each row and column containing that special character to Zero..
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100][100];
int n;
printf("Enter the number of elements of the array in one dimension\n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d", &a[i][j]);
int * i_index = (int *) malloc(sizeof(int) * n);
int * j_index = (int *) malloc(sizeof(int) * n);
for(int i=0;i<n;i++)
{
i_index[i] = -1;
j_index[i] = -1;
}
for(int i =0; i< n;i++)
for(int j=0;j<n;j++)
{
if(a[i][j] == 0)
{
i_index[i] = 0;
j_index[j] = 0;
}
}
for(int i=0;i<n;i++)
{
if(i_index[i] == 0)
for(int j=0;j<n;j++)
a[i][j] = 0;
if(j_index[i] == 0)
for(int j=0;j<n;j++)
a[j][i] = 0;
}
printf("The new elements of the array are \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d", a[i][j]);
printf("\n");
}
}
I am using additional memory but we can do it without using additional memory in that case we will have to scan through the entire array twice..In that case in first scan we replace all zeroes in the array by a special character and in the second scan we replace each row and column containing that special character to Zero..
#include<stdio.h>
#include<stdlib.h>
void main()
{
int a[100][100];
int n;
printf("Enter the number of elements of the array in one dimension\n");
scanf("%d", &n);
printf("Enter the elements of the array \n");
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d", &a[i][j]);
int * i_index = (int *) malloc(sizeof(int) * n);
int * j_index = (int *) malloc(sizeof(int) * n);
for(int i=0;i<n;i++)
{
i_index[i] = -1;
j_index[i] = -1;
}
for(int i =0; i< n;i++)
for(int j=0;j<n;j++)
{
if(a[i][j] == 0)
{
i_index[i] = 0;
j_index[j] = 0;
}
}
for(int i=0;i<n;i++)
{
if(i_index[i] == 0)
for(int j=0;j<n;j++)
a[i][j] = 0;
if(j_index[i] == 0)
for(int j=0;j<n;j++)
a[j][i] = 0;
}
printf("The new elements of the array are \n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%d", a[i][j]);
printf("\n");
}
}
your inplace solution...you just moved the problem from detecting 0s to detecting the special character in the second pas...not sure how that helps?
an inplace solution is as follows:
iterate through the matrix and change those that's nonzero but will become zero to a special character C. For example, if (i,j) is zero, going through column i and j, mark those nonzeros to be C. During the iteration, if you ever encounter C, treated it as nonzero. Then on your second pass, change these special character C to 0.
int i,j,k;
- Rakesh December 30, 2006int count = 0;
int zero_m[M];
int zero_n[N];
// scan through and get the number of zeros and their places
for(i=0;i<M;i++)
for(j=0;j<N;j++)
{
if(arr[i][j] == 0)
{
zero_m[count] = i;
zero_n[count] = j;
count ++;
}
}
// go through the zero values and make rows and col zero
for(i=0;i<count;i++)
{
// M values (rows)
for(j=0;j<N;j++)
arr[zero_m[i]][j] = 0;
// N values (columns)
for(j=0;j<M;j++)
arr[j][zero_n[i]]=0;
}
my two cents ...