Microsoft Interview Question Software Engineer / Developers
<pre lang="" line="1" title="CodeMonkey98044" class="run-this">import java.util.Arrays;
public class MatrixProblem {
public static void doIt(int[][] arr, int updateValue) {
int rowCount = arr.length;
int colCount = arr[0].length;
int[] rowSum = new int[rowCount];
int[] colSum = new int[colCount];
Arrays.fill(rowSum, 0);
Arrays.fill(colSum, 0);
for (int row = 0; row < rowCount; ++row) {
for (int col = 0; col < colCount; ++col) {
rowSum[row] += arr[row][col];
colSum[col] += arr[row][col];
}
}
for (int row = 0; row < rowCount; ++row) {
if (rowSum[row] < colCount) {
Arrays.fill(arr[row], updateValue);
}
}
for (int col = 0; col < colCount; ++col) {
if (colSum[col] < rowCount) {
for (int row = 0; row < rowCount; ++row) {
arr[row][col] = updateValue;
}
}
}
}
private static String twoDimensionnalArrayToString(int[][] arr) {
StringBuilder sb = new StringBuilder();
for (int[] row : arr) {
sb.append(Arrays.toString(row));
sb.append('\n');
}
return sb.toString();
}
public static void main(String args[]) {
int[][] arr = { { 0, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 1, 1, 1, 1 } , { 1, 1, 1, 1, 1 }};
int[][] arr2 = { { 0, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1 }, { 1, 1, 1, 1, 1 } , { 1, 1, 1, 1, 1 }};
System.out.println(twoDimensionnalArrayToString(arr));
doIt(arr, 0);
System.out.println("Set to 0");
System.out.println(twoDimensionnalArrayToString(arr));
doIt(arr2, 1);
System.out.println("Set to 1");
System.out.println(twoDimensionnalArrayToString(arr2));
}
}</pre>
for any array[i][j]; perform the following calc:
for (col = 0; col < NUMCOLS; ++col)
{
array[i][j] &&= array[i][col];
}
for (row = 0; row < NUMROWS; ++row)
{
array[i][j] &&= array[row][j];
}
i.e. simply AND the array element with all elements in its row and column.
For outputing 1, elemnts should be OR ed instead of AND
for any array[i][j]; perform the following calc:
for (col = 0; col < NUMCOLS; ++col)
{
array[i][j] &&= array[i][col];
}
for (row = 0; row < NUMROWS; ++row)
{
array[i][j] &&= array[row][j];
}
i.e. simply AND the array element with all elements in its row and column.
For outputing 1, elemnts should be OR ed instead of AND
I dont think this will work if you start updating the given matrix itself. I guess your approach will work when u start filling up a new matrix of the same size with calculating every element in it. Please respond.
public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
column[j] = 1;
}
}
}
// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
}
I transform every rows and columns into bit vectors and do & operation, just to find python is much easier to do this job :)
1 def Matrix():
2 L = [
3 [1,1,1,1,1,1],
4 [1,0,1,1,1,1],
5 [1,1,1,1,1,1],
6 [1,1,1,0,1,1],
7 [1,1,1,1,1,1],
8 ]
9 for i in L:
10 print i
11
12 x = int("".join([str(v) for v in L[0]]),2)
13 for l in L[1:]:
14 x &= int("".join([str(v) for v in l]),2)
15 row = list(str(bin(x))[2:])
16
17 x = int("".join([str(v[0]) for v in L]), 2)
18 for i in xrange(1, len(L[0])):
19 x &= int("".join([str(v[i]) for v in L]), 2)
20 col = list(str(bin(x))[2:])
21
22 print "--------------------------"
23 R = []
24 for i in xrange(len(L)):
25 if col[i] == '0':
26 R.append([0]*len(row))
27 else:
28 R.append([int(v) for v in row])
29 for v in R:
30 print v
31
32 if __name__ == "__main__":
33 Matrix()
public class Cell
{
public int Row { get; set; }
public int Col { get; set; }
public Cell(int i, int j)
{
Row = i;
Col = j;
}
}
public class MatrixProblem
{
private static void Display2DArray(int[][] arr)
{
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine();
Console.Write("\t [ ");
for (int j = 0; j < arr[0].Length; j++)
{
Console.Write(string.Format("{0}{1} ", arr[i][j], (j < arr[0].Length - 1) ? "," : ""));
}
Console.Write("]");
}
Console.WriteLine();
}
public static List<Cell> Scan2DArrayForZero(int[][] arr)
{
List<Cell> cells = new List<Cell>();
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr[0].Length; j++)
{
if (arr[i][j] == 0)
{
Cell newCell = new Cell(i, j);
cells.Add(newCell);
}
}
}
return cells;
}
public static void ConvertRowColOf2DArrayForZero(int[][] arr, List<Cell> cells)
{
foreach (Cell cell in cells)
{
for (int i = 0; i < arr[0].Length; i++)
{
arr[cell.Row][i] &= arr[cell.Row][cell.Col];
}
for (int j = 0; j < arr.Length; j++)
{
arr[j][cell.Col] &= arr[cell.Row][cell.Col];
}
}
}
public static void Main()
{
int[][] arr = new int[][]
{
new int[] { 1, 1, 1, 1, 1 },
new int[] { 1, 0, 1, 1, 1 },
new int[] { 1, 1, 1, 1, 1 },
new int[] { 1, 1, 1, 0, 1 },
new int[] { 1, 1, 1, 1, 1 }
};
Console.WriteLine("\n\n\t Original Matrix:");
Display2DArray(arr);
List<Cell> cells = Scan2DArrayForZero(arr);
ConvertRowColOf2DArrayForZero(arr, cells);
Console.WriteLine("\n\n\t Resultant Matrix:");
Display2DArray(arr);
Console.WriteLine();
}
}
public class Cell
{
public int Row { get; set; }
public int Col { get; set; }
public Cell(int i, int j)
{
Row = i;
Col = j;
}
}
public class MatrixProblem
{
private static void Display2DArray(int[][] arr)
{
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine();
Console.Write("\t [ ");
for (int j = 0; j < arr[0].Length; j++)
{
Console.Write(string.Format("{0}{1} ", arr[i][j], (j < arr[0].Length - 1) ? "," : ""));
}
Console.Write("]");
}
Console.WriteLine();
}
public static List<Cell> Scan2DArrayForZero(int[][] arr)
{
List<Cell> cells = new List<Cell>();
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr[0].Length; j++)
{
if (arr[i][j] == 0)
{
Cell newCell = new Cell(i, j);
cells.Add(newCell);
}
}
}
return cells;
}
public static void ConvertRowColOf2DArrayForZero(int[][] arr, List<Cell> cells)
{
foreach (Cell cell in cells)
{
for (int i = 0; i < arr[0].Length; i++)
{
arr[cell.Row][i] = 0;
}
for (int j = 0; j < arr.Length; j++)
{
arr[j][cell.Col] = 0;
}
}
}
public static void Main()
{
int[][] arr = new int[][]
{
new int[] { 1, 1, 1, 1, 1 },
new int[] { 1, 0, 1, 1, 1 },
new int[] { 1, 1, 1, 1, 1 },
new int[] { 1, 1, 1, 0, 1 },
new int[] { 1, 1, 1, 1, 1 }
};
Console.WriteLine("\n\n\t Original Matrix:");
Display2DArray(arr);
List<Cell> cells = Scan2DArrayForZero(arr);
ConvertRowColOf2DArrayForZero(arr, cells);
Console.WriteLine("\n\n\t Resultant Matrix:");
Display2DArray(arr);
Console.WriteLine();
}
}
Output:
=======
Original Matrix:
[ 1, 1, 1, 1, 1 ]
[ 1, 0, 1, 1, 1 ]
[ 1, 1, 1, 1, 1 ]
[ 1, 1, 1, 0, 1 ]
[ 1, 1, 1, 1, 1 ]
Resultant Matrix:
[ 1, 0, 1, 0, 1 ]
[ 0, 0, 0, 0, 0 ]
[ 1, 0, 1, 0, 1 ]
[ 0, 0, 0, 0, 0 ]
[ 1, 0, 1, 0, 1 ]
#include <stdio.h>
void change(int (*M)[5])
{
int flagrow=1,flagcol=1,i,j;
for(i=0;i<5;i++)
flagrow&=M[0][i];
for(i=0;i<5;i++)
flagcol&=M[i][0];
for(i=1;i<5;i++)
{
for(j=1;M[i][0] && j<5;j++)
M[i][0]&=M[i][j];
}
for(i=1;i<5;i++)
{
for(j=1;M[0][i] && j<5;j++)
M[0][i]&=M[j][i];
}
for(i=1;i<5;i++)
{
for(j=1;j<5;j++)
if(M[i][j]==1 && M[i][0]==0 || M[0][j]==0 )
M[i][j]=0;
}
if(flagrow==0)
for(i=0;i<5;i++)
M[0][i]=0;
if(flagcol==0)
for(i=0;i<5;i++)
M[i][0]=0;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
printf("%d ",M[i][j]);
printf("\n");
}
}
int main()
{
int arr[][5]={{1, 1, 1, 1, 1 },
{ 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1 },
{ 1, 1, 1, 1, 1 }};
change(arr);
return 0;
}
No, the algo will not change. When updating place 1 in place with 0.
<pre lang="" line="1" title="CodeMonkey72046" class="run-this">My algorithm:
- Anonymous April 16, 20111. iterate through the matrix and look for cell that contain 0.
2. Add the row and the col index to row arraylist and column arraylist for which the cell is 0;
3. After the iteration is done. update the matrix by passing the row, col (found earlier) and the value that needs to be inserted in the matrix in this case 0.
4. Update matrix using the row number, iterate in all the cols for that particular row and update the matrix with new value, same for the col iterate thru all the rows for a particular col and update the matrix with new value.
I think there should be a cleaner and better way of doing this, can anyone tell??
following is the code that I tried:
import java.util.ArrayList;
public class MatrixProblem {
public static int rows=3;
public static int cols=3;
public static void main (String args[])
{
int[][] matrix= new int[rows][cols];
matrix[0][0]=1;
matrix[0][1]=0;
matrix[0][2]=1;
matrix[1][0]=0;
matrix[1][1]=0;
matrix[1][2]=1;
matrix[2][0]=1;
matrix[2][1]=1;
matrix[2][2]=0;
ArrayList row = new ArrayList();
ArrayList col = new ArrayList();
display(matrix);
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
if(matrix[i][j]==0)
{
row.add(i);
col.add(j);
}
}
}
for(int i=0;i<row.size();i++)
{
matrix=updateMatrix(matrix, (Integer)row.get(i),(Integer)col.get(i),0);
}
display(matrix);
}
private static void display(int[][] matrix) {
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
System.out.println(" "+matrix[i][j]+ " ");
}
}
}
private static int[][] updateMatrix(int[][] matrix, int row, int col,int updateValue) {
for(int j=0 ;j<cols;j++)
{
matrix[row][j]=updateValue;
}
for(int k=0;k<rows;k++)
{
matrix[k][col]=updateValue;
}
return matrix;
}
}
</pre>