Facebook Interview Question
Jr. Software EngineersCountry: United States
@koustav.adorable: I know, it's the geeks4geeks solution. It runs in O(n*m) best and worst case. It's strategy is difficult to understand without description if the "histogram" doesn't jump right at you ;-)
If it's about finding a single rectangle, solutions with significant better average runtime are thinkable that have the same worst case behavior (depends on the rectangle dimensions). Sometimes you would approach a problem differently if you didn't know about "well known problems" ... I think that's the point of the interviews, how does one solve a problem that is new.
public static void main(String[] args) {
int[][] matrix = {
{0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 1, 0}
};
int[] upperLeft = getTopLeft();
int[] bottomRight = getBottomRight();
System.out.println("Top left coordinate: " + upperLeft[0] + ", " + upperLeft[1]);
System.out.println("Height: " + (1 + bottomRight[0] - upperLeft[0]));
System.out.println("Width: " + (1 + bottomRight[1] - upperLeft[1]));
}
public int[] getTopLeft(int[][] matrix) {
int row, col;
for (row = 0; row < matrix.length; row++) {
for (col = 0; col < matrix[row].length; col++) {
if (matrix[row][col] == 1) {
return new int[]{row, col};
}
}
}
throw new IllegalArgumentException("There was no 1 in the given array.");
}
public int[] getBottomRight(int[][] matrix) {
int row, col;
for (row = matrix.length - 1; row >= 0; row--) {
for (col = matrix[row].length - 1; col >= 0; col--) {
if (matrix[row][col] == 1) {
return new int[]{row, col};
}
}
}
throw new IllegalArgumentException("There was no 1 in the given array.");
}
def largestRectangleInMatr(list):
arr = [0 for x in range(0, len(list[0]))];
largestRecArea = 1;
for idx1 in range(0, len(list)):
for idx2 in range(0, len(list[idx1])):
arr[idx2] = 0 if list[idx1][idx2] == 0 else arr[idx2] + list[idx1][idx2];
largestRecArea = max(largestRecArea, computHistArea(arr));
return largestRecArea;
def computHistArea(arr):
stack = [];
area = 1;
idx = 0;
while idx < len(arr):
if len(stack) == 0 or arr[stack[len(stack) - 1]] <= arr[idx]:
stack.append(idx);
idx = idx + 1;
else:
width = stack.pop();
area = max(area, ((arr[width] * idx) if len(stack) == 0 else (arr[width] * (idx - stack[len(stack) - 1] - 1))));
idx = len(arr);
while len(stack) > 0:
width = stack.pop();
area = max(area, ((arr[width] * idx) if len(stack) == 0 else (arr[width] * (idx - stack[len(stack) - 1] - 1))));
return area;
print(largestRectangleInMatr([[1, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1],
[0, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1]]));
do we know there is exactly one rectangle in the matrix or do we need to search the max size rectangle in the matrix? or in other words, do *all* the '1' form a rectangle or do they have a different shape where a rectangle is contained within it?
- Chris July 29, 2017