Microsoft Interview Question SDE-2s
Team: Powerpoint
Country: United States
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)
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)?
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][0] = matrix[i][0];
for (int i = 0; i < n; i++)
topLeft[0][i] = matrix[0][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[0][i] = matrix[0][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][0] = matrix[i][0];
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;
}
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!
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?
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]
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[4] 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;
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.
@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)
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.
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++;}
{ }}
}
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
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.
#include<iostream.h>
#include<conio.h>
void main()
{clrscr();
int a[5][4],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();
}
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");
}
}
}
@ 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! :)
int find(int a[5][5])
{
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[][8]={
{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[][5] = {
{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;
}
int find(int a[5][5])
{
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[][8]={
{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[][5] = {
{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;
}
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;
}
public static int bigX(int [][] n){
int max = 0;
for(int i = 0; i <n.length; i++ ){
for(int j = 0 ; j < n[0].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;
}
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.
- Amr Gamal September 03, 2013for 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).