Microsoft Interview Question Software Engineer / Developers
I am thinking; consider we have the nxn in an array a[][], assume a[i][j].color gives us the color.
1. Max spiral size ms = 0;
1. For each element starting from a[0,0], until last;
2. Assume a funtiona Spiral which does the followig:
The moment we hit a white color cell we will try to go as far(distance d) to the right and go down d and go up distance d in a spiral fashion. We continue until the spiral hits the smallest possible spiral updating localms, in the process if we hit a black cell we set localms =0 and quit,else return localms.
3. If localms > ms then ms = localms
3. If Go to step 1 with the next element.
4. return ms
If the actual sub square is required in terms of the array indices (left top/right bottom pair), we need to store that too in function spiral.
I guess the spiral has an issue.. The above method will help u in finding squares within squares... But what about a sub-square on left/right corner?
______________
| | |
| | |
|____| |
| |
| |
|_____________|
______________
| |
| _______ |
| | | |
| | | |
| |______| | ====> Your Spiral model will generate this.
|_____________|
use dynamic programming.
keep two values right and down that tells how many consecutive black pixles are in that direction including the current pixel.
Compute this using bottom up approach.
Then, use these values to compute the maximum square length at each pixel. Should run in O(n*n) time and memory.
What do u guys think?
Good idea, Raghu !
I guess you need left and up values as well, It would be when your algo is crunching in the middle of the matrix. but ya .. it would work in O(n^2) space and time ... but thats acceptable .. n^2 time is definitely needed to read every pixel... its linear in terms of the number of cells.
Assume the matrix to be a binary tree, where each cell is a node connected to 2 other nodes (down & right). Do a DFS based on this tree structure and determine borders.
1. keep a count of consecutive black pixels along one direction(if its less than the max found so far, then forget it).. else its a potential candidate, so explore other borders
2. still dont know how to avoid redundancy in checking ..
3. one spl case would be that if you find a square of side n/2 .. u can stop ..! :D .. pretty obvious !
... i know its kinda vague .. but seems like the right direction.
using a devide and counter method could yield between O(n*lgn) and O(n^2);
FindMaxSquare(matrix,1,n){
sqr1=FindMaxSquare(matrix,1,n/2);
sqr2=FindMaxSquare(matrix,n/2+1,n);
borderLength=max(sqr1.borderLength,sqr2.borderLength);
sqr3=FindMaxSqaureAlongAxis(n/2,borderLength+1);
if(sqr3!=null)return sqr3;
else return max(sqr1,sqr2);
}
master theorem T(n)=2T(n/2)+f(n);
here f(n) is the complexity of FindMaxSqaureAlongAxis, so if we could prove that complexity of FindMaxSqaureAlongAxis is between O(n) and O(n^2), then the total time we need is between O(n*lgn) and O(n^2).
Complexity of FindMaxSqaureAlongAxis is O(borderLength*n), since borderLength could be a constant, or could be proportional to n, so O(n)=<O(borderLength*n)=<O(n^2). done
I think we will use dynamic programming here.I agree with raghu.
let the size of square be N.
pseudocode:
for each cell
{
calculate the black cell along its right.Let it ne Nr.
Calculate the white cells along downside.
Let it be Nd
length = Min(Nr,Nd)
for i =1 to length
{
check the subcell i*i has blackborder
if yes.
max=cell id and i
}
}
return Max
It will have complexity of order N^N.
why is this O{n^2}?
for each cell // n
{
calculate the black cell along its right.Let it ne Nr. //n
Calculate the white cells along downside. Let it be Nd //n
length = Min(Nr,Nd) // 1
for i =1 to length //n
{
check the subcell i*i has blackborder //n^2
if yes.
max=cell id and i
}
}
return Max
It should be O(n*(n+n+1+n*n^2)) = O(n^4)???
What raghu means, is calculating out the right, down of each cell in pre-processing, not inside the loop. your code is O(n^4).
Besides right and down, I think also left and up is needed. So each cell will have four values. These four values can be calculated out in four O(N^2) process.
Then traverse all cells from left to right, up to down.
Foreach cell c
int len = Min(c.right, c.down)
for(i = 0; i < len; ++i){
check whether the square using c as left top point and border length = i exists.
}
It's not dynamic programming. Time complexity is bigger than O(N^2) but smaller than O(N^3)
Apply dynamic programming to compute Max length for row & columns
1) Initialize
maxRowLen[ k ] [ n-1 ] = (arr[ k ][ n -1 ] == 0 ?1:0)
maxColLen[ n-1 ] [ k ] = (arr[ n-1 ][ k ] == 0 ?1:0)
For each element in arr[k][j] (k = n-2 to 0) (j = n-2 to 0)
2) if arr[ k ] [ j ] == 1
maxRowLen[ k ] [ j ] = 0
3) else // i.e arr[ k ] [ j ] == 0
maxRowLen[ k ][ j ] = maxRowLen[k][j+1] + 1
Compute Max length for Column
4) if arr[ k ] [ j ] == 1
maxLen[ k ][ j ] = 0
5) else // i.e arr[j] == 0
maxColLen[ k ][ j ] = maxColLen[k+1][j] + 1
6) maxSqLen = 0
Now iterate either of max length row or max length col & for each (either of) maxRowLen or maxColLen ---
Lets take maxRowLen
7) lenOfSquare = Minimum( maxRowLen[k][j], maxColLen[k][j] )
8) if lenOfSquare > maxSqLen
9) Now, check if a square is formed
if( maxColLen[ k ][ j+ lenOfSquare ] == lenOfSquare &&
maxRowLen[ k + lenOfSquare ][ j ] == lenOfSquare )
{
maxSqRowStart = k;
maxSqColStart = j;
maxSqLen = lenOfSquare ;
}
Space - 2 dimension array for maxRolLen & maxColLen i.e O(2 * N square )
Time - O( 2 * N square )
1) Compute maxRowLen & maxColLen for each element of arr[n * n] +
2) Compute if square with max len is formed for each element (either of) maxRowElem or maxColLen
The output should be a subsquare surrounded by all black pixels. This can be done by keeping a list of all white squares and running BFS from each white square. The white squares can not be from first row or column and last row or column. When running BFS pick up any one node and travel level by level eliminating branches that cannot satisfy the constraints. Also eliminate these nodes from the list of white squares. If you are able to find an enclosed boundary then just check if the enclosed boundary has k*k dimensions.This can be done by keeping track how much we have moved in y direction and x direction.
Using Dynamic programming, can it be done like...
for each cell
n = calculate size of square it's forming using black border
(for this need to check all 4 sides of square so that they have
equal nos. of black pixels)
O->->->->->
| |
| | here n = 5;
| | squareSize = 3
| |
| |
->->->->->
SquareSize = (n-2);
if(maxSquareSize < SquareSize)
maxSquareSize = SquareSize;
print "maxSquareSize"
The easiest and O(n~n*n)way is:
Look for pure white subsqures instead of black frames.
------------------------------
Initialization：MaxLength=0;
------------------------------
step 1: for every cell, if cell=white go to step 2
------------------------------
step 2: take the current cell as the leftup corner of the subsqure, and length=1+MaxLength, is the subsqure pure white? If yes, go to step 3, else go to step 1;
------------------------------
step 3: is the squre surrounded by black frame? If yes,MaxLength++, and go back to step2; If no, go back to step 1.
I can think of 2 methods. One is a simple to implement brutish method, while the other is more efficient but harder to implement.
Method 1: Simply test for sub-squares starting with S (length of side) = N, and continue till S = 2 i.e. S = N -> 2. For each S test each pixel in the matrix as the top corner of S. This is O(n^3), but it is simple to understand and gauranteed to work for complex configurations.
Method 2: As some have already mentioned, one can go through the matrix keeping a list of horizontal black lines (only need to store to coords - the start and end of the line). Then do similar to get a list of verticle lines. Note that one has to keep every single line and not just the max length lines because there are various combinations of lines that can form a square - Note: horizontal lines and verticle lines may intersect each other to form a square that is smaller then the length of each individual line. So from here I am not sure how to easily look at intersection points to identify the larger square.
I like my method 1 because it is simple and given be visually animated to show that it is scanning correctly.
white = 0 black = 1
1. construct a row and a col matrix to record the # of consecutive "1" from current node to left, and up, respectively.
e.g.:
Original (A):
11111
11101
10111
01011
row:
12345
12301
10123
01012
col:
11111
22202
30313
01024
int maxsize = 0;
for i=0; i<N; i++
for j=0; j<N, j++{
if (A[i,j]==1){
for (int k=min(i,j); k>maxsize; k--){ //min(i,j) is the maximum possible square size from i,j to 0,0
if ((row[i,j] - row[i,j-k] == k) &&
(row[i-k,j] - row[i-k,j-k] == k) &&
(col[i,j] - col[i-k,j] == k) &&
(col[i-k,j] - col[i-k,j-k] == k) &&
)
maxsize=k;
break;
}
}
}
still O(n^3) though
Read Matrix and store all black in sorted order in an array. After that it is just finding consecutive blacks.....
e.g. a 3*3 matrix like this
www
bbw
bbw
can be stored as 10,11,20,21
Now foreach element
1. count consecutive number e.g. for 10 it is {10,11} = 2( lets call it len)
2.now we know that for this entry we can at max a square of length 2(len).
3.now go downwards. for first and last number in above set and keep going for len-1 entries. so try to find 20(y) in above array and then 21(k). As it is sorted array, binary search will do
4. if above test is successful, travel from y -> k with y++ in each step and try to find it(y).
if we have success we located a square of length len for first entry.
5. Now feel free to skip len-1 entries and proceed
Time complexity should be less than n^3. in worst case(all blacks) should be around nLog(n)
public static int findLargestSquare(int[][]test) {
int largest = 0;
printMatrix(test);
for (int y = test[0].length-1; y>=0; y--) {
for (int x = test.length-1; x >=0; x--) {
if (x != test.length-1 && y != test[0].length -1 &&
test[x][y] !=0) {
int bottom = test[x][y+1];
int right = test[x+1][y];
int bottomRight = test[x+1][y+1];
test[x][y] = Math.min(bottom, Math.min(right, bottomRight))+1;
}
}
}
for (int i = test.length - 1; i >=0; i--) {
for (int j = test[0].length-1; j >=0; j--) {
if (test[i][j] > largest) {
largest = test[i][j];
}
}
}
return largest;
}
// A C++ program to find the largest subsquare
// surrounded by 'X' in a given matrix of 'O' and 'X'
#include<iostream>
using namespace std;
// Size of given matrix is N X N
#define N 6
// A utility function to find minimum of two numbers
int getMin(int x, int y) { return (x<y)? x: y; }
// Returns size of maximum size subsquare matrix
// surrounded by 'X'
int findSubSquare(int mat[][N])
{
int max = 1; // Initialize result
// Initialize the left-top value in hor[][] and ver[][]
int hor[N][N], ver[N][N];
hor[0][0] = ver[0][0] = (mat[0][0] == 'X');
// Fill values in hor[][] and ver[][]
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
if (mat[i][j] == 'O')
ver[i][j] = hor[i][j] = 0;
else
{
hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;
ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;
}
}
}
// Start from the rightmost-bottommost corner element and find
// the largest ssubsquare with the help of hor[][] and ver[][]
for (int i = N-1; i>=1; i--)
{
for (int j = N-1; j>=1; j--)
{
// Find smaller of values in hor[][] and ver[][]
// A Square can only be made by taking smaller
// value
int small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure that there is a right
// vertical line and bottom horizontal line of length
// at least 'small'.
// We found a bigger square if following conditions are met:
// 1)If side of square is greater than max.
// 2)There is a left vertical line of length >= 'small'
// 3)There is a top horizontal line of length >= 'small'
if (small > max && ver[i][j-small+1] >= small && hor[i-small+1][j] >= small)
max = small;
}
}
return max;
}
// Driver program to test above function
int main()
{
int mat[][N] = {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
cout << findSubSquare(mat);
return 0;
}
O(n^2) solution is available for the problem in "cracking the code interview" book. chapter : 20 (problem 20.11)
Could you clarify the question a bit more? Do the number of black pixels and white pixels have to be equal? Also, are subsquared filled with one color only?
- nunbit romance June 11, 2007