|
|
Given a matrix of 1s and 0s. ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
98. Given a matrix of 1s and 0s. ....
Question:
Given a matrix of 1s and 0s. Implement an algorithm that sets all cells of row i and column j to 0 if the original matrix has a 0 in cell (i,j). Would the algo change if you have to set it to 1 instead of 0?
maybe an answer:
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 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 ]
|
(Continued on next question...)
Other Interview Questions
|
