Microsoft Interview Question for SDE-2s

• 1
of 1 vote

Team: Powerpoint
Country: United States

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

At every cell, there are two diagonals that pass through this cell, one going from top-left corner of the matrix to bottom-right corner and the other going from top-right to bottom-left corner. The idea is to keep a matrix of the same size as the input matrix, each entry represents the the number of consecutive ones in the diagonal going from top-left to bottom-right corner such that the sequence of ones starts at the top left of current cell and ends at the current cell, similarly we keep 3 other matrices, one for sequences of ones in the diagonal going from top-left to bottom-right but starting at a cell that is at the bottom right of the current cell. The other 2 matrices are kept from the other diagonal going from top-right to bottom-left corner.
for example, consider the matrix:
0 1 1 1 0 0 0
0 1 0 0 0 0 0
0 1 1 0 1 0 1
1 0 0 1 1 1 0
1 0 1 1 0 1 0
1 1 1 1 1 0 1

top-left matrix keeping counts of ones starting at top left and ending at each cell:
0 1 1 1 0 0 0
0 1 0 0 0 0 0
0 1 2 0 1 0 1
1 0 0 3 1 2 0
1 0 1 1 0 2 0
1 2 1 2 2 0 3

bottom-left
0 1 2 1 0 0 0
0 1 0 0 0 0 0
0 2 1 0 4 0 2
1 0 0 3 3 1 0
1 0 2 2 0 2 0
1 1 1 1 1 0 1

top-right
0 1 1 1 0 0 0
0 2 0 0 0 0 0
0 1 1 0 1 0 1
2 0 0 2 1 2 0
1 0 3 2 0 1 0
1 4 3 1 2 0 1

bottom-right
0 1 1 1 0 0 0
0 3 0 0 0 0 0
0 1 2 0 2 0 1
1 0 0 1 3 1 0
2 0 2 2 0 2 0
1 1 1 1 1 0 1

and then at each cell[i,j] in the original matrix, get length of sequences of ones ending at the 4 neighboring diagonal cells from the matrices computed above, namely [i-1, j-1], [i-1, j+1], [i+1, j-1], [i+1, j+1], compute "minValue" which is the minimum of these values.
size of an X with center at the current cell is 2*minValue+1.
time complexity O(n*m), space Complexity O(n*m).

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

this might be a good solution too.. :) check out the dfs solution and kindly post comments. Considering '1' is a node and 0 is null, we recurse until we hit a '0' while doing current cell's value = 1+recurse(cell in left or right diagonal direction)

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

This is fantastic.
O(n^2) time & space

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

Can you explain the O(n*m)

I thought counting the diagonals would take O(max(M,N)) as for each cell you need to count the diagonals, wouldn't the run time be O(m*n*max(m,n)) for simplicity m=n wouldn't that be O(n^3 + n^2) = O(n^3)?

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

I have implemented your algorithm, and it seems to work fine! I really like your solution, easy to implement and very effective!

int findGreatestX(bool **matrix, int m, int n) {
int **topLeft = new int*[m];
for (int i = 0; i < m; i++)
topLeft[i] = new int[n];

int **topRight = new int*[m];
for (int i = 0; i < m; i++)
topRight[i] = new int[n];

int **botLeft = new int*[m];
for (int i = 0; i < m; i++)
botLeft[i] = new int[n];

int **botRight = new int*[m];
for (int i = 0; i < m; i++)
botRight[i] = new int[n];

// Calculating topLeft
for (int i = 0; i < m; i++)
topLeft[i] = matrix[i];

for (int i = 0; i < n; i++)
topLeft[i] = matrix[i];

for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
topLeft[i][j] = (matrix[i][j]) ? topLeft[i-1][j-1] + 1 : 0;

// Calculating topRight
for (int i = 0; i < m; i++)
topRight[i][n-1] = matrix[i][n-1];

for (int i = 0; i < n; i++)
topRight[i] = matrix[i];

for (int i = 1; i < m; i++)
for (int j = n-2; j >= 0; j--)
topRight[i][j] = (matrix[i][j]) ? topRight[i-1][j+1] + 1 : 0;

// Calculating botLeft
for (int i = 0; i < m; i++)
botLeft[i] = matrix[i];

for (int i = 0; i < n; i++)
botLeft[m-1][i] = matrix[m-1][i];

for (int i = m-2; i >= 0; i--)
for (int j = 1; j < n; j++)
botLeft[i][j] = (matrix[i][j]) ? botLeft[i+1][j-1] + 1 : 0;

// Calculating botRight
for (int i = 0; i < m; i++)
botRight[i][n-1] = matrix[i][n-1];

for (int i = 0; i < n; i++)
botRight[m-1][i] = matrix[m-1][i];

for (int i = m-2; i >= 0; i--)
for (int j = n-2; j >= 0; j--)
botRight[i][j] = (matrix[i][j]) ? botRight[i+1][j+1] + 1 : 0;

int maxMinVal = 0;
int curMinVal;

for (int i = 1; i < m-1; i++) {
for (int j = 1; j < n-1; j++) {
curMinVal = min(min(botRight[i+1][j+1],
botLeft[i+1][j-1]),
min(topRight[i-1][j+1],
topLeft[i-1][j-1]));
if (curMinVal > maxMinVal)
maxMinVal = curMinVal;
}
}

return (2*maxMinVal) + 1;
}

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

As explanation for the runtime, the solution is T(n, m) = 5*n*m which is O(n*m). The 5 is since we have 5 n*m loops. And memory is M(n, m) = 4*n*m which is O(n*m), just like OP mentioned. Again, great solution!

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

The question says "2 equally sized diagonals that share a single 1". So do we need to apply the calculation on "each cell[i,j]" or just cell[i,j] which is 1?

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

We need to calculate min only for the cells which are 1 .

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

great thinking, a small optimization........

after creating the 4 matrices(say br, bl, tr, tl), find min = min(br[i][j], bl[i][j], tr[i][j], tl[i][j]);

length of cross with centre at i,j = 2 * min - 1

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

As I see it, this question is really about your attention to detail in relation to the question asked and the requirements. Here are the key points:

1. Bits: only 1's or 0's will be allowed.
2. Equally sized diagonals: they must be the exact same length (see assumption below to see why this is critical)
3. Share a common mid-point: the middle 1 must be present in both diagonals.

We can get some good operational savings by applying these parameters. First off, we are scanning for diagonals that share a common mid-point, so we need not scan the first or last row nor column as they can't be a mid-point. This gets us some major performance gains on smaller matrices (N < 5 or M < 5) as it limits the possible mid-points substantially, which will reduce the number of 'check for diagonal' scans that must be done.

Secondly, the output of this operation is an integer value of the longest diagonal, so there is no need to store the length of all diagonals or use any type of dynamic programming methodology (if we wanted the locations of the longest diagonal then we would). We merely need to find all of the X's as defined above, measure the length of the diagonals, and keep a running tracker of the max length to return at the end, knowing that a return of 0 means there is not an X present. In this sense, our algorithm will actually be in-place, or O(1) as we only use a small number of additional constant variables to track our progress.

One last assumption I will make is that unequal lengths will disqualify an X, even in this case:
1 0 1 0
0 1 0 0
1 0 1 0
0 0 0 1

Now with a clear operational definition, we can proceed with our pseudo:

1. Scan through each matrix entry starting with 1,1 (not 0,0) and ending at n-1,m-1 (not n,m) so that we only scan entries that can be a mid-point.
2. If we encounter a 1, check for diagonals via a quick if to see if the 4 diags contain a 1. If any of them contain 0's, return to step 1 and continue. Otherwise proceed with:
2a. traverse each directional diagonal (up-right, up-left, down-right, down-left) till you find a 0 or edge, count it's value (without the mid-point)
2b. Add together the opposite diags (up-right + down-left and up-left + down-right), add 1 to account for the mid-point and compare sizes
2c. If sizes are the same, compare to maxDiag variable, else go back to step 1
2d. If it's larger, update maxDiag to equal this diagonal length, otherwise leave it at current value
3. Once all entries are scanned, return maxDiag.

Our running time is between O( (nm)^2) and O(nm) because while our primary loop only touches each entry once (excluding the outer edge), there is the possibility to scan each node multiple times depending on the number of diagonals present in the matrix. However, given the constraints, I believe a safe upper notation would be O((nm)^2), knowing that across random distribution of matrices we will get better performance, particularly on smaller matrices due to our "exempt outer edge" scan.

[I hope to come back and edit this with a live code example once I get a chance to write one up]

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

Here's one approach:

Traverse the whole matrix and store all diagonals according to size. If the array size is (n, m), then the diagonal size can range from 1 to min(n, m)

Make two arrays of vectors which will store the two kinds of diagonals.

For example, something like(some kind of pseudo-code):

class Point {
int x, y;
}

Vector<1> front_diags[min(n,m)]
Vector<1> back_diags[min(n,m)]

front_diags will store all diagonals of type / and size 4 as a vector

So if you have the matrix
00100001
00010010
00001100
00001100
00010010
00100001

front_diag =
[[], [], [], [], [], [Point(7, 0)]]
back_diag =
[[], [], [], [], [], [Point(2, 0)]]

because there is only one front diagonal(size 6, starting from (7, 0)) and only one back diagonal(size 6, starting from (2, 0))

Now iterate through min(n,m)-1 to 0, trying to find pairs of the same size that intersect. The first pair you find should be the largest intersecting X in the matrix.

for size = min(n,m)-1 to 0:
for front in front_diag[size]:
for back in back_diag[size]:
if((front.x + back.x - front.y + back.y)%2==0): Intersection point's x coordinate is an integer
if((-front.x + back.x + front.y + back.y)%2==0): //Intersection point's y coordinate is an integer
if((front.x - back.x + front.y - back.y)/2 >= size): //Intersection point is not more than size away from front's start
if((front.x - front.y - back.x + back.y)/2 >= size): // Intersection point is not more than size away from back's start
return size;

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

Is it going to work, when the diagonals create not a valid X? Like in the example in the question, when there is an intersection, but X is not valid because the intersection point is wrapped by some other 1s?

To my mind you should add a checking after all if the found intersection is valid or not.

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

@joe kidd: My condition for intersection is that that intersection must be a valid point. I have checked whether the intersection is a valid point or not in the last part of my answer(2 out of the 4 if conditions)

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

Small mistake in the code above: replace >= by < in the 2nd and 3rd last lines

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

what is the cost of constructing the front_diag and back_diag ?

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

The time to construct front_diag and back_diag is O(m*n)

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

Since the diagonals may share only a single '1', you want to scan the matrix in one direction, looking for, in each row (or column), all pairs of 1's that are separated by an odd number of 0's or 1's only. You would then look for a chain of these pairs where the interval of separation descends to a 'singularity' (the single '1' at the center) and then ascends back to the original interval of separation.

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

an O(n^3) algorithm.
we can use a function to calculate the longest X fron each i , j in the matrix.
for each cell = 1 in the matrix, find the long X.
return the longest X from all the cells in the matrix.

int longX(int a[n][m], int n, int m, int i, int j){
{ int k = 1;}
{ while (1){}
{ if (i+k > n || j+k > m || i-k < 0 || j-k < 0)}
{ return k;}
{ if (a[i+k][j+k] != 1 || a[i-k][j+k] != 1 || a[i-k][j+k] != 1 || a[i-k][j-k] != 1)}
{ return k;}
{ k++;}
{ }}
}

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

the question needs some clarification on the definition of an X. Do the lines have to cross at mid-points? For example, do two lines that are orthogonal to each other but form a "T" count as an X or not? According to your definition, it does, but logically it should not.

Either way, we need to start at one corner and iterate through all elements in the matrix in a sequential way. For each "1", assume it is the crossing point of the "X":
- check the length of the longest line that crosses that point
- do we have a line that is perpendicular to the initial line. If yes, calculate its length and return the minimum of the two, else return 1.

This will yield a O(n^3) solution. Sounds bad but in this case, I think this is the best available solution

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

I wonder if we could do a depth first search on the matrix from top of matrix to bottom and then in the reverse direction. We store the top to bottom: (right, left) diagonal length values and the bottom to top: (left, right) diagonal length values originating from each cell. Then we traverse these ~nm values to find the cell whose pair of values from above are the same.

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

#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
int a,i,j,k,l,count=0;
cout<<"entr the array";
for(i=0;i<5;i++)
{for(j=0;j<4;j++)
cin>>a[i][j];
}
for(i=0;i<4;i++)
{
for(j=0;j<3;j++)
{ k=l=0;
if(a[i][j]==1)
{while(++k)
{
if(a[i+k][j+k]==0 || (i+k)>=5 || (j+k)>=4)
{k--;
break;
}
}
}
if(a[i][j+k]==1)
{
while(++l)
{
if(a[i+l][j+k-l]==0 || (i+k)>=5 || (j+k)>=4)
{l--;
break;
}
}
}
if(k>=l && l>=count)
count=l+1;
if(l>=k && k>=count)
count=k+1;
if(count>(4-count-j))
break;
}
if(count>(5-count-i))
break;
}
if(count==1)
count=0;
cout<<count;
getch();
}

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

void FindLargestX()
{
int i,j,k,p,max=-1,flag,q,r;
int I=-1,J=-1;
int start=-1;
int end=-1;
for(i=0;i<row;i++)
{
q=0;
flag=1;
for(j=0;j<col;j++)
{
if(a[i][j]==1)
{
k=j+1;
while(a[i][k]!=1)
k++;
q=k-j+1;
if(i+q-1<=row)
{
r=i;
for(p=j;p<j+q;p++)
{
if(a[r][p]!=1)
{
flag=0;
break;
}
r++;
}
if(flag==1)
{
r=i;
for(p=j+q-1;p>=j;p--)
{
if(a[r][p]!=1)
{
flag=0;
break;
}
r++;
}
}
if(flag==1)
{
if(q>max)
{
max=q;
I=i;
J=j;
}
}
}
}
}
}

if(I!=-1 && J!=-1)
{
for(i=I;i<I+max;i++)
{
for(j=J;j<J+max;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
}
}

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

I feel like the real exercise is understanding your solution.

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

@ Jon Cole, I am sorry Jon, you are right, I should have been more clear!
In a nut shell, we are only start checking only if there is a potential match i.e., if an entry is 1. If found, we move on that particular column until next 1 is encountered. If it is found we make sure that the column distance fits the remainder of the rows (i.e., q=k-j+1 -- k is the next 1 and j is where we encountered first 1). Now, we simply check the two diagonals (i,j) - (i+q,j+q) and then (i,j+q) - (i+q,j). If it is satisfied i.e., if we found that the matrix formed by above indices actually contains an X then we check the column distance i.e., q against the previously found value and keep the larger one. The variable "flag" ensures that we only check the opposite diagonal if the previous diagonal is a right one + if both diagonals form an X. I hope this helps! :)

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

Amr Gamals solution has an optimal asymtotic time complexity. Do you see how to revise the algorithm so that the time complexity is O(nxm/k) on a k-processor machine?

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

int find(int a)
{
int m=5, n =5;
int count = 0;
int xpos, ypos;
int ulx, urx, llx, lrx;
int uly, ury, lly, lry;

for(int i=0; i<m;i++)
{
for(int j=0; j<n; j++) {
if(a[i][j]==1)
{ xpos =i;
ypos = j;
ulx = xpos -1; uly = ypos -1; urx = xpos+1; ury = ypos+1;
llx = xpos+1; lly = ypos-1; lrx = xpos-1; lry = ypos+1;

while(a[ulx][uly] == 1 &&
a[urx][ury] == 1 &&
a[llx][lly] == 1 &&
a[lrx][lry] == 1) {
count += 2;
ulx--; uly--; urx++; ury++; llx++; lly--; lrx--; lry++;

}
}
}
//cout<<count<<endl;
}
cout<<count+1<<endl;

}
int main()
{
int a[]={
{0,0,1,0,0,0,0,1},
{0,0,0,1,0,0,1,0},
{0,0,0,0,1,1,0,0},
{0,0,0,0,1,1,0,0},
{0,0,0,1,0,0,1,0},
{0,0,1,0,0,0,0,0}};

int b[] = {
{1,0,0,0,1},
{0,1,0,1,0},
{0,0,1,0,0},
{0,1,0,1,0},
{1,0,0,0,0}
};

find(b);

return 0;
}

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

int find(int a)
{
int m=5, n =5;
int count = 0;
int xpos, ypos;
int ulx, urx, llx, lrx;
int uly, ury, lly, lry;

for(int i=0; i<m;i++)
{
for(int j=0; j<n; j++) {
if(a[i][j]==1)
{   xpos =i;
ypos = j;
ulx = xpos -1; uly = ypos -1; urx = xpos+1; ury = ypos+1;
llx = xpos+1; lly = ypos-1; lrx = xpos-1; lry = ypos+1;

while(a[ulx][uly] == 1 &&
a[urx][ury] == 1 &&
a[llx][lly] == 1 &&
a[lrx][lry] == 1) {
count += 2;
ulx--; uly--; urx++; ury++; llx++; lly--; lrx--; lry++;

}
}
}
//cout<<count<<endl;
}
cout<<count+1<<endl;

}
int main()
{
int a[]={
{0,0,1,0,0,0,0,1},
{0,0,0,1,0,0,1,0},
{0,0,0,0,1,1,0,0},
{0,0,0,0,1,1,0,0},
{0,0,0,1,0,0,1,0},
{0,0,1,0,0,0,0,0}};

int b[] = {
{1,0,0,0,1},
{0,1,0,1,0},
{0,0,1,0,0},
{0,1,0,1,0},
{1,0,0,0,0}
};

find(b);

return 0;
}

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

Why do we need such complex algo. It can be solved in O(n*m) .Here is the code.

#include<stdio.h>
#include<conio.h>
#define R 6
#define C 8
#define X 2
void printMax(int M[R][C])
{
int i,j,ctr=0;
for(i=0;i<R;i++)
{
int ctr1=1;
for(j=0;j<C;j++)
{
if(M[i][j]==1)
{
if(M[i+1][j+1]==1 && M[i-1][j-1]==1 && M[i+1][j-1]==1 && M[i-1][j+1]==1)
ctr1+= X;
if(ctr<ctr1)
ctr=ctr1;
}
}
}
printf("%d", ctr);
}
int main()
{
int M[R][C]={{0,0,1,0,0,0,0,1},
{0,0,0,1,0,0,1,0},
{0,0,0,0,1,1,0,0},
{0,0,0,0,1,1,0,0},
{0,0,0,1,0,0,1,0},
{0,0,1,0,0,0,0,1}};
printMax(M);
getch();
return 0;

}

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

public static int bigX(int [][] n){
int max = 0;
for(int i = 0; i <n.length; i++ ){
for(int j = 0 ; j < n.length; j++ ){
int c = 0;
if ( n[i][j] == 1){
c = 1;
int ti = i;
int tj = j;
while ( ti - c >= 0 && ti + c< n.length && tj - c >= 0 && tj + c < n.length){
if ( n[ti-c][tj-c] == 1 && n[ti-c][tj+c] == 1 &&
n[ti+c][tj-c] == 1	&& n[ti+c][tj+c] == 1 )
c+=2;
}
}
if ( c > max )
max = c;
}
}
return max;
}

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

what is the meaning of "equally sized diagonals"

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

Two diagonals of 1's that are of the same size.
101
010
100
Doesn't not have equally sized diagonals

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.