Microsoft Interview Question SDE1s
Country: United States
Interview Type: Phone Interview
Actually its O(n) memory because you need to allocate 2 arrays of n size for rows and columns.
no, you don't. you can just use the first row and column of the matrix. O(1) extra space. You have the code in the link given above. It has 2 solutions i think, one of them is this one.
First we go through all cells in the matrix. If cell[i][j] is zero, we put cell[i][0] and cell[0][j] equal to zero. This runs in O(n^2).
Then we process the first row. If cell[0][j] is 0, then nullifyColumn(j) is called which just sets all values in that column to 0. nullifyColumn runs in O(n) and there are n columns so this takes at most O(n^2).
Likewise, we do the same for the first column and nullify the rows. This takes at most O(n^2).
O(n^2 + n^2 + n^2) is O(n^2) time. We use the first row and first column to store the zeros, so O(1) extra space.
Scan matrix for zeroes and remember rows and columns containing 0,
in second path update matrix. Computational complexity O(n^2), memory complexity O(n)
def mat_zero(mat, n):
"""Zero columns and rows which contains at least one zero
Example:
>>> mat_zero([[1, 2, 3, 4],
... [5, 6, 7, 8],
... [9, 0, 1, 0],
... [3, 4, 5, 6]], 4)
[[1, 0, 3, 0], [5, 0, 7, 0], [0, 0, 0, 0], [3, 0, 5, 0]]
"""
cols, rows = [False] * n, [False] * n
for i in range(n):
for j in range(n):
if mat[i][j] == 0:
cols[i], rows[j] = True, True
for i in range(n):
for j in range(n):
if cols[i] or rows[j]:
mat[i][j] = 0
return mat
void setZero(int, int,int *, int);
int main(){
const int n = 4;
int array[n][n]={{1, 1, 3, 1}, {5, 9, 0, 8}, {1, 2, 3, 4}, {3, 2, 5, 9}};
// creating a copy of matrix for locating zero in the original
int array_2[n][n];
for(int i = 0; i<n; i++){
for(int j=0; j<n;j++){
array_2[i][j] = array[i][j];}}
//locating and assigning zeros
for(int i=0; i<n; i++){
for(int j=0; j<n; j++)
if(array_2[i][j]==0) setZero(i, j, &array[0][0], n);
}
//printing matrix
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
cout<<setw(6)<<array[i][j];}
cout<<endl;}
_getch();
return 0;
}
void setZero(int row, int column, int *ptr, const int size){
int *a = ptr + column; //will be used to modify row to zero
int *b = ptr + row*size; //will be used to modify column to zero
for(int i=0; i<(size); i++){
ptr = a;
*ptr = 0;
a += size;}
column = 0;
while(column<size){
ptr = b;
*ptr = 0;
b++;
column++;}
}
void SetZeros(int Matrix[][],int rowSize, int colSize)
{
int rowMask = 0;
int colMast = 0;
for(int i = 0; i < rowSize; i++)
{
for(int j=0; j < colSize; j++)
if(Matrix[i][j] == 0)
{
rowMask |= 1 << i;
colMast |= 1 << j;
}
}
for(int i = 0; i < rowSize; i++)
{
for(int j=0; j < colSize; j++)
if(rowMask & 1 << j && colMask & 1 << j)
{
Matrix[i][j] = 0;
}
}
} - At least algorithm should work.
//Lets define 3* 3 matrix
int n=3;
//this is the multidimensional array here3 dimensional is used
int[,] matrixValues = new int[n, n];
//add any values to the matrix
for (int f = 0; f < n; f++)
{
for (int g = 0; g < n; g++)
{
matrixValues[f, g] = f + 3;
}
}
//My Matrix will look like
//[ 3 3 3 ]
// [ 4 4 4 ]
// [ 5 5 5 ]
//Add static values 0 to 2*1 index
//and any random values to see the diff
matrixValues[0, 0] = 2;
matrixValues[0, 1] = 7;
matrixValues[1, 0] = 4;
matrixValues[2, 1] = 0;
//now here comesw the logic
for (int i = 0; i <n; i++)
{
for (int j = 0; j < n; j++)
{
if (matrixValues[i, j] == 0)
{
for (int k = 0; k < n; k++)
{
matrixValues[i, k] = 0;
}
}
}
}
number_of_rows = 4
matrix = [[1, 2, 3, 4],
[5, 6, 0, 0],
[9, 0, 1, 0],
[3, 4, 5, 6]]
marked_rows = []
marked_columns = []
for i in (0..number_of_rows-1) do
for j in (0..number_of_rows-1) do
if matrix[i][j] == 0
marked_rows << i unless marked_rows.include? i
marked_columns << j unless marked_columns.include? j
elsif marked_columns.include?(j)
break
end
end
end
for i in (0..number_of_rows-1) do
for j in (0..number_of_rows-1) do
matrix[i][j] = 0 if marked_rows.include?(i) or marked_columns.include?(j)
end
end
p marked_rows
p marked_columns
p matrix
=begin
marked_row : [1, 2]
marked_column : [2, 3, 1]
matrix : [[1, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[3, 0, 0, 0]]
=end
The below implementation does it with O(n) time and O(n) space complexity. Algorithm is in comments.
/**
TASK: Given an n X n matrix, find all elements which are zero, when found
set all the elements in that row and column to zero.
ALGORITHM:
1. Do a single table traversal and collect the information on the rows
and columns to be zero'ed
2. Do another traversal of the table to zero the cells
*/
void zero_cells(int arr[5][5])
{
int cols[5] = {0};
int rows[5] = {0};
// collect table statistics
for (int j = 0; j < 5; ++j){
for (int i = 0; i < 5; ++i)
if (arr[j][i] == 0){
cols[i] = 1;
rows[j] = 1;
}
// zero out cells and rows
for (int j = 0; j < 5; ++j){
for (int i = 0; i < 5; ++i){
if (cols[i] == 1 || rows[j] == 1)
arr[j][i] = 0;
}
The algorithm uses the fist row with the zero found in it (if it is one) as a temporary storage to mark rows, that need to be zeroed in the future.
This is completely in memory solution, which doesn't require any additional dynamic allocation.
class NxNMatrixColAndRowToZero
{
// private static int[][] M = {{1, 2, 0}, {4, 5, 6}, {7, 8, 9}};
// private static int[][] M = {{1, 2, 3}, {4, 0, 6}, {7, 8, 9}};
// private static int[][] M = {{1, 0, 3}, {4, 5, 6}, {7, 8, 0}};
// private static int[][] M = {{1, 2, 0}, {4, 5, 6}, {7, 8, 0}};
// private static int[][] M = {{0, 2, 3}, {4, 0, 6}, {7, 8, 0}};
private static int[][] M = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
private static int N = M.length;
private static int firstZeroRow = -1;
static public void main (String args[])
{
System.out.println(
"Given an n X n matrix, find all elements which are zero, " +
"when found set all the elements in that row and column to zero.");
for(int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (M[i][j] == 0)
{
zeroRowAndMarkColumn(i, j);
j = N;
}
}
}
if (firstZeroRow >= 0)
{
for(int j = 0; j < N; j++)
{
if (M[firstZeroRow][j] == 1)
{
for(int i = 0; i < N; i++)
{
M[i][j] = 0;
}
}
}
}
for(int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
System.out.print(M[i][j] + "\t");
}
System.out.println();
}
}
private static void zeroRowAndMarkColumn(int r, int c)
{
for(int j = 0; j < N; j++)
M[r][j] = 0;
if (firstZeroRow < 0)
firstZeroRow = r;
M[firstZeroRow][c] = 1;
}
}
public class PlaceZero{
int x;
int y;
public PlaceZero(int i,int j){
this.x=i;
this.y=j;
}
}
public int[][] checkAndSetZero(int[][] arr) {
ArrayList<PlaceZero> p = new ArrayList<PlaceZero>();
int n = arr.length;
// find zeros in matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0) {
PlaceZero z = new PlaceZero(i, j);
p.add(z);
}
}
}
for (int k = 0; k < p.size(); k++) {
int l=p.get(k).x;
int m=p.get(k).y;
for (int i = 0; i < n; i++) {
arr[l][i]=0;
arr[i][m]=0;
}
}
return arr;
}
package org.avnish.javabrain;
public class SetArrayToZero {
/**
* @param args
*/
public static void main(String[] args) {
int n = 4;
int a[][]={{1, 1, 3, 1}, {5, 9, 7, 8}, {1, 0, 3, 4}, {3, 2, 5, 9}};
printArray(a,n);
a=setToZero(a,n);
printArray(a,n);
}
public static void printArray(int a[][], int size){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
System.out.print(a[i][j] + " ");
}
System.out.println("");
}
System.out.println("\n");
}
public static int[][] setToZero(int[][] a, int size){
int[] zeroArrayRow = new int[size];
int[] zeroArrayCol = new int[size];
for(int k=0;k<size;k++){
for(int i=0;i<=k;i++){
if(a[i][k]==0){
zeroArrayRow[i] = 1;
zeroArrayCol[k] = 1;
}
if(a[k][i]==0){
zeroArrayCol[i] = 1;
zeroArrayRow[k] = 1;
}
}
}
for(int i=0;i<size;i++){
if(zeroArrayRow[i]==1){
a=zeroRow(a,i, size);
}
if(zeroArrayCol[i]==1){
a=zeroCol(a, i, size);
}
}
return a;
}
public static int[][] zeroRow(int[][] a, int r, int size){
for(int i=0;i<size;i++){
a[r][i]=0;
}
return a;
}
public static int[][] zeroCol(int[][] a, int c, int size){
for(int i=0;i<size;i++){
a[i][c]=0;
}
return a;
}
}
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;
int _tmain(int argc, _TCHAR* argv [])
{
int n = 0;
int testCase[9][9] = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 0, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 0, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, };
bool col[9] = { false, false, false, false, false, false, false, false, false };
bool row[9] = { false, false, false, false, false, false, false, false, false };
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (testCase[i][j] == 0)
{
col[i] = true;
row[j] = true;
break;
}
}
}
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (col[i] || row[j])
{
cout << 0 << " ";
}
else
{
cout << testCase[i][j] << " ";
}
}
cout << endl;
}
system("pause");
return 0;
}
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;
int _tmain(int argc, _TCHAR* argv [])
{
int n = 0;
int testCase[9][9] = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 0, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 0, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, };
bool col[9] = { false, false, false, false, false, false, false, false, false };
bool row[9] = { false, false, false, false, false, false, false, false, false };
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (testCase[i][j] == 0)
{
col[i] = true;
row[j] = true;
break;
}
}
}
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (col[i] || row[j])
{
cout << 0 << " ";
}
else
{
cout << testCase[i][j] << " ";
}
}
cout << endl;
}
system("pause");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
void zero(int* array , int n)
{
#define array(i,j) array[i*n+j]
int *row = (int*) malloc (n * sizeof(int));
for(int i=0; i<n; i++)
row[i] = 0;
int *col = (int*) malloc (n * sizeof(int));
for(int i=0; i<n; i++)
col[i] = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(0 == array(i,j))
{
row[i] = 1;
col[j] = 1;
}
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(row[i] == 1 || col[j] == 1)
array(i,j) = 0;
}
}
free(row);
free(col);
}
int main()
{
int a[9] = {1,2,0,4,5,6,7,8,9};
zero(a,3);
for(int i=0; i<9; i++)
printf("%d " , a[i]);
system("pause");
}
similar to ctci solution
public class RowCol {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] a= new int[][]{{1, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 1, 1, 1}};
for (int j = 0; j < a.length; j++) {
System.out.println("");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i][j]);
}
}
System.out.println("");
System.out.println("");
System.out.println("");
RowCol rowCol = new RowCol();
rowCol.check(a);
for (int j = 0; j < a.length; j++) {
System.out.println("");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i][j]);
}
}
}
int[][] findZeros(int[][] matrix) {
for (int i = 0; i < matrix.length; i++)
for (int j = 0; j < matrix.length; j++)
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
return matrix;
}
int[][] check(int[][] matrix) {
matrix = findZeros(matrix);
for (int j = 0; j < matrix.length; j++) {
if (matrix[0][j] == 0)
matrix = nullifyColumn(j, matrix);
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0)
matrix = nullifyRow(i, matrix);
}
return matrix;
}
int[][] nullifyColumn(int j, int[][] matrix) {
if (matrix[0][j] == 0) {
for (int i = 0; i < matrix.length; i++)
matrix[i][j] = 0;
}
return matrix;
}
int[][] nullifyRow(int i, int[][] matrix) {
if (matrix[i][0] == 0) {
for (int j = 0; j < matrix.length; j++)
matrix[i][j] = 0;
}
return matrix;
}
}
@Paul: you could have used this logic instead of zeroRowAndMarkColumn funtion.
for(int i = 0; i < rowSize; i++)
{
for(int j=0; j < colSize; j++)
if(Matrix[i][j] == 0)
{
rowMask |= 1 << i;
colMast |= 1 << j;
}
}
it's on CtCI book and repeated many times
- Miguel Oliveira September 24, 2013careercup.com/question?id=10442525 (switch 0 to 1)
careercup.com/question?id=302724
etc
It's possible to do it in O(n^2) time and O(1) extra memory.
explanation: book errata page 182, ex 1.7
docs.google.com/spreadsheet/pub?hl=en_US&hl=en_US&key=0AuwEKO7o6mrAdFdhZHRlN1JUc3dEVFRNMDJzWlE1VXc&output=html
code: github.com/gaylemcd/ctci/blob/master/java/Chapter%201/Question1_7/Question.java