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)
                    {
                        list.Add(i);
                        list.Add(j);
                    }
                    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");
                }
            }

}

- Jeanclaude February 07, 2014 | Flag Reply
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)?

- Jeanclaude February 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Sunny February 08, 2014 | Flag
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...

- Jeanclaude February 08, 2014 | Flag Reply
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)

- Anonymous February 08, 2014 | Flag Reply
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
        }
    }
}

- Westlake February 08, 2014 | Flag Reply
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).

- Yo Yo Honey Singh February 08, 2014 | Flag Reply
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)

- lakshaman February 08, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More