## Microsoft Interview Question for Software Engineer / Developers

• 6

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

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?

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

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.

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

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.
|_____________|

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

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?

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

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.

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

The idea of using Dynamic programming is good but I think it is still O(n^3) time complexity, because you have to check if the right line exists, if not decrease the size.... so it gets O(n) for each top left corner

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

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.

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

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

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

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.

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

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)???

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

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)

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

also check max..at every loop

if i < max
do not store
else max = new max

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

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

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

For subsquare, N^2 is enough. What if it is not subsquare?

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

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.

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

at least n^3

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

Using Dynamic programming, can it be done like...
for each cell
n = calculate size of square it's forming using black border
SquareSize = (n-2);
if(maxSquareSize < SquareSize)
maxSquareSize = SquareSize;

print "maxSquareSize"

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

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"

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

formatting has ruined the square I am trying to display. Consider right vertical edge such that width = height = 5

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

_ _ _ _
| /\ |
| / \ |
| / \ |
|/ \|
|\ /|
| \ / |
| \ / |
|_ _\/_ _|

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

_ _ _ _
| /\ |
| / \ |
| / \ |
|/ \|
|\ /|
| \ / |
| \ / |
| \/ |
- - - -

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

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.

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

so the size of possible white subsqures should be
0, 4=2*2, 9=3*3, 16=4*4.

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

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.

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

there is an O(n^2) algo with O(n^2) space.

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

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

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

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

<a href="http://khmyzszs.com">yuuyu</a> http://khmyzszs.com [url=http://khmyzszs.com]yuuyu[/url]

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

<a href="http://khmnhrzs.com">hgryu</a> http://khmnhrzs.com [url=http://khmnhrzs.com]hgryu[/url]

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

<a href="http://khmnhrzs.com">hgryu</a> http://khmnhrzs.com [url=http://khmnhrzs.com]hgryu[/url]

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

<a href="http://khmnhrzs.com">hgryu</a> http://khmnhrzs.com [url=http://khmnhrzs.com]hgryu[/url]

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

doors.txt;5

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

doors.txt;5

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

doors.txt;5

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

doors.txt;5

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

doors.txt;10

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

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)

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

public static int findLargestSquare(int[][]test) {
int largest = 0;
printMatrix(test);
for (int y = test.length-1; y>=0; y--) {
for (int x = test.length-1; x >=0; x--) {
if (x != test.length-1 && y != test.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.length-1; j >=0; j--) {
if (test[i][j] > largest) {
largest = test[i][j];
}
}
}
return largest;
}

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

``````// 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 = ver = (mat == '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;
}``````

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

O(n^2) solution is available for the problem in "cracking the code interview" book. chapter : 20 (problem 20.11)

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

That solution is not actually O(n^2). If you analyze it a little bit more it is O(n^4) worst case. there are 3 loops in which there is a call to a method which also has a loop. All of these depend on n.

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

(n-1) x (n-1) will be the sub square

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

Worked for me. could solve the problem in O(1) time.

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

yea awesome solution man...

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.