Microsoft Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
Why do you return an array S[n][m]? You were supposed to return a location and dimensions of the one max square.
Can you please put a comment what you store in array S?
This is code I had written for the DP problem. When you get matrix S, you find the maximum number in it and this maximum number will be at the bottom right corner of the square and the number will tell you how big the square is.
let's say you have
1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 0
then your answer matrix S should be
S[0, 0] = 1, S[0, 1] = 2, S[0, 3] = 3 etc..
I think once you change that your could should give you correct output.
note.. i haven't run your code but it seems there is some problem there.
for matrix like
1, 1, 1, 1
0, 0, 0, 0
your answer matrix should be populated like
s[0, 0] = 1, s[0, 1] = 2, s[0, 2] = 3 etc.
I haven't run your code but i think that should be causing you issue to get correct answer
@SK
We have to evolve the recursive solution(used in your DP) more preciously covering all possible cases,
Currently it looks like this soluton does not work quite well, take any complex problem, where 0's and 1's are randomly distributed
In above solution, at each node of the S, instead of storing a single value, you need to store two values.
So use the following class
@Value
Class Entry {
int rowCount,
int colCount
}
then
S = new Entry[row_size][col_size]
S[i][j]= new Pair(Math.min(S[i-1][j].getRowCount, S[i][j-1].getColCount())+1, S[i][j-1].getRowCount() + 1) // if mat[i][j] == 1
or else
S[i][j] = new Pair(0,0)
This solution gives both the max square and rectangle size. Traverse the matrix again to get whichever value you want. If you need the exact coordinates, store those values too in the Entry class.
Time complexity = O(row_size * col_size)
Space complexity = O(row_size * col_size)
In above solution, at each node of the S, instead of storing a single value, you need to store two values.
So use the following class
@Value
Class Entry {
int rowCount,
int colCount
}
then
S = new Entry[row_size][col_size]
S[i][j]= new Pair(Math.min(S[i-1][j].getRowCount, S[i][j-1].getColCount())+1, S[i][j-1].getRowCount() + 1) // if mat[i][j] == 1
or else
S[i][j] = new Pair(0,0)
This solution gives both the max square and rectangle size. Traverse the matrix again to get whichever value you want. If you need the exact coordinates, store those values too in the Entry class.
Time complexity = O(row_size * col_size)
Space complexity = O(row_size * col_size)
This is just a different way of asking the problem "Finding the maximum size square matrix with all zero's in a given matrix of 0's and 1's". Where I's can be considered as matrix points covered by buildings and otherwise.
This solution has runtime O(4^N) for N buildings and there must be a more optimal way to do this, but right now I can't think of a better solution other than brute force.
public class Square {
public final int x;
public final int y;
public final int length;
public Square(int x, int y, int length) {
this.x = x;
this.y = y;
this.length = length;
}
}
public class Rectangle {
public final int x;
public final int y;
public final int width;
public final int height;
public Rectangle(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
}
public Square largestSquare(Rectange plot, Rectangle[] buildings) {
return largestSquare(plot, buildings, 0);
}
public Square largestSquare(Rectange plot, Rectangle[] buildings, int index) {
if (index >= buildings.length) {
return new Square(plot.x, plot.y, Math.min(plot.width, plot.height));
}
Rectangle building = buildings[index];
// Left of building
Square s1 = largestSquare(new Rectangle(plot.x, plot.y, building.x-plot.x, plot.height), buildings, index+1);
// Below building
Square s2 = largestSquare(new Rectangle(plot.x, plot.y, plot.width, building.y-plot.y), buildings, index+1);
// Right of building
Square s3 = largestSquare(new Rectangle(building.x+building.width, plot.y, plot.width-building.x-building.width, plot.height), buildings, index+1);
// Above building
Square s4 = largestSquare(new Rectangle(plot.x, plot.y, plot.width, plot.height-building.y-building.height), buildings, index+1);
// Return max possible size square
return max(s1, s2, s3, s4);
}
public static Square max(s1, s2, s3, s4) {
Square max1 = s1.length > s2.length ? s1 : s2;
Square max2 = s3.length > s4.length ? s3 : s4;
return max1.length > max2.length ? max1 : max2;
}
This could be done in O(nmn) time where n is the size of the smaller dimension and m is the size of the larger dimension by simply quantizing the space and seeing how large a rectangle could be made at each point (n, m) in the rectangle with the point as a corner.
However, I think it could probably be improved by doing something like DP somehow.
If you think of the plot as a matrix of 1s and 0s, where 1s are available land and 0s are unavailable land (land with buildings already there), then this problem reduces to finding the maximum size square submatrix. Which has a dynamic solution of O(n^2)
- SK May 19, 2015public int[][] findMaxSubmatrix(int[][] mat) { int[][] S = new int[mat.length][mat[0].length]; for (int i = 0; i < S[0].length; i++) { S[0][i] = mat[0][i]; } for (int j = 1; j < S.length; j++) { S[j][0] = mat[j][0]; } for (int i = 1; i < S.length; i++) { for (int j = 1; j < S[0].length; j++) { if (mat[i][j] == 0) { continue; } S[i][j] = Math.min(Math.min(S[i][j - 1], S[i-1][j]), S[i-1][j - 1]) + 1; } } return S; }