## McAfee Interview Question for Senior Software Development Engineers

Country: India
Interview Type: In-Person

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

Nice problem!

We have a number different approaches for solving this. I've assumed n and m to be equal for the sake of an easier analysis. Inequality of n and m has no effect on the validity of the solutions.

One is the naive approach, which picks two cells at a time and checks if those two cells can be upper left and bottom right cells of a valid rectangle. This solution has a time complexity of O(n^6).

Another approach is a dynamic programming approach. In this approach we first pre-process to calculate for every cell mx(i,j) the number of zeroes in the rectangle defined by (1,1) to (i,j). We do this with the simple formula below using the principle of inclusion and exclusion:

``zeroes(i,j) = zeroes(i-1,j) + zeroes(i,j-1) - zeroes(i-1,j-1)``

After that for every two cells in the matrix, we first check if those two cells define boundary of a rectangle. If they do so, we check if there is zero in between using the information we obtained previously. This approach has a running time of O(n^5).

We can do better, however. We first, pre-process the matrix to obtain the matrix of the number of zeroes like the previous approach. We have an additional pre-processing step here. We calculate for every cell that has a one in it, the number of consecutive ones immediately to the right, left, up, and down of that cell. After that for every two cell A & B we check if they define a valid boundary using the immediate ones information found previously. If they do we check if they enclose a zero similar to the previous solution. This approach runs in O(n^4).

We STILL can do better. This solution is a bit complex and my explanation of what goes in my head may not be comprehensive enough. :-)
We have two pre-processing steps. In the first step, we calculate the number of consecutive ones above every cell leading to that cell. The other pre-processing step is calculating for every cell mx(i,j), the number of zeroes in row i until column j. After that for we do the following operations on every two column i and j. We go forward one row, k, at a time and count the number of valid rectangles that have mx(k,i)---mx(k,j) as their lower edge. Feel free to check my code to get a feeling of how it is calculated. I'll be more than happy to discuss that. :-) This solution has cubic running time, and I cannot think of a better one.

My C++ implementation for the O(n^3) solution:

``````#include <iostream>
#include <algorithm>

using namespace std;

int zerocnt[1010][1010], oneline[1010][1010], fulllines[1010], mtrx[1010][1010];

int solve(int **mx, int n, int m)
{
for (int i = 0; i<n; i++)
{
mtrx[i][0] = 0;
oneline[i][0] = 0;
zerocnt[i][0] = 0;
}
for (int j = 0; j<m; j++)
{
mtrx[0][j] = 0;
oneline[0][j] = 0;
zerocnt[0][j] = 0;
}
for (int i = 0; i<n; i++)
for (int j = 0; j<m; j++)
{
mtrx[i + 1][j + 1] = mx[i][j];
oneline[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 1 ? oneline[i][j + 1] + 1 : 0);
zerocnt[i + 1][j + 1] = (mtrx[i + 1][j + 1] == 0 ? 1 : 0) + zerocnt[i + 1][j];
}

int ans = 0;

for (int i = 1; i <= m - 2; i++)
for (int j = i + 2; j <= m; j++)
{
int closestzero = -1;
fulllines[0] = 0;
for (int k = 1; k <= n; k++)
{
fulllines[k] = fulllines[k - 1];
if (zerocnt[k][j] != zerocnt[k][i])
{
closestzero = k;
continue;
}

++fulllines[k];

int shortline = min(oneline[k][i], oneline[k][j]);

if (closestzero > (k - shortline) + 1)
ans += fulllines[closestzero] - fulllines[(k - shortline)];

}
}

return ans;
}``````

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

I also think that O(n^3) solution is the best we can do.

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

what is singleline n zerocount matrix?
Also, what is closest Zero, could you please tell the logic of this .

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

First of all, I'm really sorry for bad variable naming. Always had problems with that :-D

Let's explain those ugly variables:

1. zerocount(i,j): the number of zeroes in row "i" before and including column "j"

2. oneline(i,j): the length of the line formed in column j by ones including and immediately above the (i, j) cell. In the example below oneline(2,2) = 2, oneline(1,2) = 1, oneline(4,1) = 2, oneline(2,1) = 0, and oneline(1,4) = 1
1 1
0 1
1 0
1 1

3. fulllines(k): the number of full(all ones between column i and j) lines before and including k-th row. This variable is changed for every i and j.

4. closestzero: this variable holds the index of the nearest row above the current row that has a zero in it.

Now what happens in the for(k=1 -> n) loop:
We first check to see if the current row contains all ones between column i and j. We do this using our zerocnt table. If the number of zeroes in row k before column j is not equal to the number of zeroes before column i we know that we have a zero. We set closestzero to the current row index and go to the next row. If we have all ones in the current row, we know that it is a candidate for the bottom edge of a rectangle. We also know that any valid rectangle with this row as its edge should have a top edge that is above closestzero(so it encloses at least a zero). Another observation is that the right and the left edge can have a length of at most the minimum of two lines that extend upwards from mtrx(k,i) and mtrx(k,j). We have information about those two lines in the variable oneline. Now that we know the upper bound and the lower bound for the index of the top edge, we can simply calculate the number of full lines between those two bounds and add to our answer.

If still something is ambiguous, I'd be glad to discuss further.

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

only 3 rectangles are present.

Conditons :
1. The rectangles will always enclose some 0’s. e.g. last two vertical lines does not constitute a rectangle.

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

Compute all possible Vertical/Horizontal lines in this matrix first. Then check overlap b/w horizontal and Vertical lines to detect rectangles.

Integral Image concept is there to compute any rectangle sum (any size, any location) to check whether it contains zeros.

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

Integral Image concept is mentioned in above solution. 3 additions are good enough to computer any rectangle sum.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This traverses n elements twice, so it's O(n)

``````/*
* FindRectangle.cc
*
*  Created on: Apr 21, 2014
*      Author: Tom Tong
*/

#include <iostream>
#include <vector>

using namespace std;

class TrackNode {
public:
TrackNode() : right_(0), below_(0) {}

int getRight() { return right_; }
void addRight(TrackNode n) { right_ += n.getRight() + 1; }
void setRight(int i) { right_ = i; }

int getBelow()  { return below_; }
void addBelow(TrackNode n) { below_ += n.getBelow() + 1; }
void setBelow(int i) { below_ = i; }

protected:
int right_, below_;
};

int main(int , char**)
{
int matrix[][6]=  {0,0,1,1,1,1,
1,1,1,0,1,1,
1,0,1,0,1,1,
1,1,1,0,1,1,
0,0,1,0,1,1,
0,1,1,0,1,1,
0,0,1,1,1,1};

int width = sizeof(matrix[0])/sizeof(matrix[0][0]);
int height = sizeof(matrix)/sizeof(matrix[0]);
cout << "w:" << width << ", h:" << height << endl;

vector<TrackNode> nodes(width*height);
int i, j;
// this is O(n), since it traverses the matrix once.
for(j = height - 1; j >= 0; j--)
for(i = width - 1; i >= 0; i--)
{
if (matrix[j][i] != 0)
{
int pos = j*width+i;
TrackNode& node = nodes[pos]; // 6*6+5 is the last one
if (j == (height-1)) // end of row
node.setBelow(1);
else
if (i == (width-1)) // end of col
node.setRight(1);
else
}
}

// this is just for displaying data, not counted for O().
for(j = 0; j < height; j++)
{
for(i = 0; i < width; i++)
{
cout << nodes[j*width+i].getRight() << "," << nodes[j*width+i].getBelow() << " ";
}
cout << endl;
}

int countRect = 0;
// this is O(n), since it traverses the TrackNode vector once.
for(j = 0; j < height; j++)
{
for(i = 0; i < width; i++)
{
int pos = j*width+i;
TrackNode& node = nodes[pos];
if(node.getRight() > 1 &&
node.getBelow() > 1)
{
TrackNode& left = nodes[pos + node.getRight() - 1];
TrackNode& below = nodes[pos + (node.getBelow() - 1)*width];
if (left.getBelow() >= node.getBelow() &&
below.getRight() >= node.getRight())
{
countRect++;
cout << "rect at corner: " << j << "," << i << endl;
}
}
}
}

cout << "found " << countRect << " rectangles." << endl;

return 0;
}``````

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

Hey buddy, I think you have misunderstood the problem. The answer is also incorrect for the given example.

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

Don't think so. There are a total of 8 rectangles, most of them are nested.

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

only 3 rectangles are present.
Conditons :

1. The rectangles will always enclose some 0’s. e.g. last two vertical lines does not constitute a
rectangle.

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.