## ADP Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the one I have come up with... it's of the order N^2. But coming to space, although I have used an additional list, it's not as big as the input array... Please let me know if we can do this in O(N) and without using extra space (list, array or any other variables)?

``````class Program
{
static void Main()
{
Program pob = new Program();
int[,] a = new int[5, 5] { { 0, 1, 1, 3, 4 }, {1, 0, 3, 2, 4 }, {1, 2, 0, 1, 4}, {1, 2, 3, 0, 4}, {1, 2, 3, 4, 0} };
pob.IfAnElementis0FillCorrespondingRowsAndColsTo0s(a);
}

public void IfAnElementis0FillCorrespondingRowsAndColsTo0s(int[,] a)
{
int r = 5, c = 5;
int i = 0, j = 0;
//   a = new int[3, 3] { { 2, 1, 0 }, { 3, 2, 4 }, { 2, 1, 1 } };

List<int> list = new List<int>();

//This iteration is required to mark the row & col positions where we have 0s in original array. Add those positions to a list.
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
if (a[i, j] == 0)
{
}
else
{
continue;
}
}
}

//This iteration actually updates original matrix with 0s wherever applicable.
int k = 0;

for(i= 0; i < list.Count; i+=2)
{
for(j = 0; j < c; j++)
{
a[list[i], j] = 0;
}

for (k = 0; k < r; k++)
{
a[k, list[i+1]] = 0;

}
}

//just prints the modified matrix.
for(i=0; i< r; i++)
{
for(j=0; j < c; j++)
{
Console.Write(a[i,j] + " ");
}
Console.WriteLine("\n");
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Clarification - my friend also came up with an O(N^2) solution and the interviewer does not seem to have asked for a linear solution.. however out of my curiosity, I'm asking you folks to tell me if there is a way to do this in O(N)?

Comment hidden because of low score. Click to expand.
0

How can you do better than O(N^2) when you have to iterate through all the elements just to see which one is a zero?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I thought so, but then was wondering if there is any algo (that I'm not aware of) and could do that... Thanks anyway...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Phase 1: If a given cell is 0, set the first location of the corresponding row and column to 0.

Phase 2: Go over all starting cells of rows and set the entire row to 0 where the starting cell is 0. Similarly for columns.

Complexity: O(n^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int C[N] = { 1 };
int R[N] = { 1 };

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (m[i][j] == 0) {
R[i] = 0;
C[j] = 0;
}
}
}

for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (R[i] * C[j] == 1) {
m[i][j] = 0
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The complexity will remain O(n^2) in the worst case but in other cases I guess it can be improved by maintaining two separate arrays(one for rows and other for columns) for keeping track of which column or row has been already worked on(I mean made 0).

Comment hidden because of low score. Click to expand.
0
of 0 vote

The current solutions posted above are all O(n) only.

If the problem were on a 3 D matrix and you iterate over it. It does not become O(n^3)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.