## Google Interview Question for Software Engineer / Developers

• -6

Country: United States
Interview Type: In-Person

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

the idea is use DP to find the height, left, right for each element.

if(matrix[i][j] == '0'){
height[i][j] = 0; left[i][j] = 0; right[i][j] = 0; //because it's an obstacle
}
else{
height[i][j] = 1 --- if matrix[i-1][j] == '0';
height[i][j] = matrix[i-1][j] + 1 --- otherwise

left[i][j] = max(left[i-1][j], the index of the first obstacle on the element's left);
right[i][j] = min(right[i-1][j], the index of the first obstacle on the element's right)
}

then we just go through the elements and find the max area, which is height*(right-left).

idea from: hi.baidu.com/mzry1992/item/030f9740e0475ef7dc0f6cba

``````//oj.leetcode.com/problems/maximal-rectangle/
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix.length==0){
return 0;
}
else{
int row = matrix.length;
int col = matrix.length;
int[][] lefts = new int[row][col];
int[][] rights = new int[row][col];
int[][] heights = new int[row][col];
int[] leftObs = new int[col];
int[] rightObs = new int[col];

findLeftRightObs(0, matrix, leftObs, rightObs);

for(int i=0; i<col; i++){
if(matrix[i] != '0'){
heights[i] = 1;
lefts[i] = leftObs[i];
rights[i] = rightObs[i];
}
}

for(int i=1; i<row; i++){
findLeftRightObs(i, matrix, leftObs, rightObs);
for(int j=0; j<col; j++){
if(matrix[i][j] != '0'){
if(matrix[i-1][j] == '0'){
heights[i][j] = 1;
lefts[i][j] = leftObs[j];
rights[i][j] = rightObs[j];
}
else{
heights[i][j] = 1+heights[i-1][j];
lefts[i][j] = (int)Math.max(lefts[i-1][j], leftObs[j]);
rights[i][j] = (int)Math.min(rights[i-1][j], rightObs[j]);
}
}
}
}
int max = 0;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if((rights[i][j]-lefts[i][j])*heights[i][j]>max){
max = (rights[i][j]-lefts[i][j])*heights[i][j];
}
}
}
return max;
}
}

public void findLeftRightObs(int row, char[][] matrix, int[] leftObs, int[] rightObs){
int obs = 0;
for(int i=0; i<matrix.length; i++){
if(matrix[row][i] == '0'){
leftObs[i] = i;
obs = i+1;
}
else{
leftObs[i] = obs;
}
}
obs = matrix.length;
for(int i=matrix.length-1; i>=0; i--){
if(matrix[row][i] == '0'){
rightObs[i] = obs;
obs = i;
}
else{
rightObs[i] = obs;
}
}
}``````

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

For the solution, since the problem description says that all 1 are connected, it is not necessary to obtain leftObs[] and rightObs[] in the way described.

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

How many google interviews are you having the last few weeks? WOAH.

Comment hidden because of low score. Click to expand.
3
of 5 vote

hi Obiwana/GZPenny

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

``````int min_i = w;
int min_j = h;
int max_i = 0;
int max_j = 0;

for ( int i = 0; i < min_i; ++i )
{
int j = 0;
while ( j < min_j && a[i][j] == 0 )
{
j++;
}
min_j = j;

int j2 = w;
while ( j2 > max_j && a[i][j2 - 1] == 0 )
{
j2--;
}
max_j = j2;
}

max_i--;
max_j--;``````

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

Sorry, this does not calculate min_i, max_i

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

Is this question correct Min rectangle?
If you go for min rectangle then it should be of 1x1.

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

Not correct, 1x1 would contain only one black, the request is to contain "all" black.

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

Scan through the array and store the (min_i, min_j) and (max_i, max_j) where a[i][j] == 1

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

int min_i = w;
int min_j = h;
int max_i = 0;
int max_j = 0;

for ( int i = 0; i < h; ++i )
{
int j = 0;
while ( j < min_j && a[i][j] == 0 )
{
j++;
}
min_j = j;

int j2 = w;
while ( j2 > max_j && a[i][j2 - 1] == 0 )
{
j2--;
}
max_j = j2;

if ( j < min_j)
{
min_i = min(i, min_i);
max_i = max(i+1, max_i);
}
}

max_i--;
max_j--;

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

Sorry this is not formatted.

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

``````int min_i = w;
int min_j = h;
int max_i = 0;
int max_j = 0;

for ( int i = 0; i < h; ++i )
{
int j = 0;
while ( j < min_j && a[i][j] == 0 )
{
j++;
}
min_j = j;

int j2 = w;
while ( j2 > max_j && a[i][j2 - 1] == 0 )
{
j2--;
}
max_j = j2;

if ( j < min_j)
{
min_i = min(i, min_i);
max_i = max(i+1, max_i);
}
}

max_i--;
max_j--;``````

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

This should be the correct one.

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

what if the graph contains multiple blobs?

e.g.

00000
01001
11001
11101

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

I guess the problem is to find out the max rectangle. It can be done with Dynamic Programming.
1) Create an array with size of the given array i.e. Sol[m][n] which is an array of tuple(left, right) and let input array by A[m][n]
2) Outer loop (i) from left to right and inner loop (j) from top to bottom
3) if A[j,i] = 0 then Sol[j,i] = (0,0)
else
Sol[j,i] = (Sol[j,i-1].right+1, Sol[j-1,i].left + 1)
The max rectangle will be where the product of the tuple is max. Here is how the solution array looks like

``````(0,0) (0,0) (0,0) (0,0) (0,0)
(0,0) (1,1) (1,2) (1,3) (0,0)
(0,0) (2,1) (2,2) (0,0) (0,0)
(0,0) (3,1) (0,0) (0,0) (0,0)
(0,0) (0,0) (0,0) (0,0) (0,0)``````

Time Complexity O(mn)
Space Complexity O(mn)

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

Umm... Are you sure? Do you have a proof?

(Even assuming Max).

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

Am not sure how to prove it but the logic is to develop the size of the rectangle of 1's from top to bottom and left to right. At each step i am using information about the rectangles already created (top and left) and expanding it.
I tried it for a few examples and it worked. Now that you have mentioned it I am very eager to find out how to prove it. if you happen to get a proof please share.

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

This is obviously wrong. Just assume that A = 1, your logic will produce S = (2,2), which is wrong.

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

You are right this logic won't work..

Lets try another approach. This problem can be broken down into the subproblem of finding max rectangle area in a histogram.
Preprocessing
Scan the array top to bottom and A[i+1,j] = A[i,j] + A[i+1,j] whenever A[i+1,j] is 1
This will give us the count of continuous 1's associated with a given cell above it. So the array becomes.

``````00000
01110
02200
03000
00000``````

Now each row represents a historgram. We have 2 algorithms to solve this problem O(n) and O(nlogn).
So total time complexity is O(mn) or O(mnlogn).
Space complexity O(n)

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

``````Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  1  1  0
1  1  1  1  1
0  0  0  0  0
The maximum square sub-matrix with all set bits is

1  1  1
1  1  1
1  1  1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a)	Copy first row and first columns as it is from M[][] to S[][]
b)	For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:

0  1  1  0  1
1  1  0  1  0
0  1  1  1  0
1  1  2  2  0
1  2  2  3  1
0  0  0  0  0

---From : geeksforgeeks``````

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

this is wrong, it does not ask for maximum subsquare, but maximum subrectangle !!!!!!

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

trying to shrink the map from the edge to find the rectangle, ideally this won't need to visit all the nodes, worst case if there's only one black in the middle, will need to visit extra 1.5row.

``````#include <iostream>
#include <vector>

void findMinRectangle(const vector<vector<int> > &map) {
const int num_row = map.size();
const int num_column = map.size();

int row_min = 0;
int column_min = 0;
int row_max = num_row - 1;
int column_max = num_column - 1;

// Finds the top.
bool find_black = false;
for (; row_min < num_row; ++row_min) {
for (const auto &c: map[row_min]) {
if (c == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
if (!find_black) {
// There is no black point in the map.
cout << "No black in the map." << endl;
return;
}
// Finds the left.
find_black = false;
for (; column_min < num_column; ++column_min) {
for (int r = row_min; r < num_row; ++r) {
if (map[r][column_min] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
// Finds the bottom.
find_black = false;
for (; row_max > row_min; --row_max) {
for (int c = column_min; c < num_column; ++c) {
if (map[row_max][c] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
// Finds the right.
find_black = false;
for (; column_max > column_min; --column_max) {
for (int r = row_min; r <= row_max; ++r) {
if (map[r][column_max] == 1) {
find_black = true;
break;
}
}
if (find_black) break;
}
cout <<
"(" << row_min << "," << column_min << ") - (" <<
row_max << "," << column_max << ")" << endl;
}``````

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

As everyone else here, I'll assume the problem asks for the maximum rectangle (given by max area) found on the matrix. Also, my approach will only return the area of the max rectangle as opposed to returning the corner indexes (implementing this would be trivial based on my solution):

For each cell, determine the size of the largest row of non-obstacle spaces achievable.

Then, for each cell get the biggest of all possible rectangles created by all non-obstacle cells from the columns that start at the current cell and grow from bottom to top times the minimum of the largest row size (calculated before) of each row in the column.

Example:

0 0 1
0 1 1
1 1 1

Largest rows:
0 0 1
0 1 2
1 2 3

List of all possible max-rectangles per cell:
{ } { } { (1x1) }
{ } { (1x1) } { (2x1), (1x2) }
{ (1x1) } { (2x1), (1x2) } { (3x1), (2x2), (1x3) }

The maximum rectangle area is 4 because at cell (2,2) there exists a column of size 2 with widest achievable row of 2.

Time complexity: O(n^3) // Assuming board is nxn
Space complexity: O(n^2)

Code:

``````bool board [MAX_WIDTH][MAX_HEIGHT];
int max_rows [MAX_WIDTH][MAX_HEIGHT];

int rect_max_area(bool board [][MAX_HEIGHT], const int width, const int height)
{
memset(max_rows, 0, width * height * sizeof(int));

int max_area = 0;
for (int row_index = 0; row_index < height; row_index++)
for (int col_index = 0; col_index < width; col_index++)
if (board[row_index][col_index])
{
max_rows[row_index][col_index] = 1;
if (col_index > 0 && board[row_index][col_index - 1])
max_rows[row_index][col_index] +=
max_rows[row_index][col_index - 1];

int height = 1;
int local_max_area = 0;
int h_index = row_index;
int min_width = max_rows[row_index][col_index];
while (h_index >= 0 && board[h_index][col_index])
{
local_max_area = max(local_max_area, height * min_width);

height++;
h_index--;
min_width = min(min_width, max_rows[h_index][col_index]);
}

max_area = max(max_area, local_max_area);
}

return max_area;
}``````

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

The statement of the question is not clear. The clear statement should be: Find the largest rectangle that contains only 1's. For example, in the following case:
01
10
The largest one is only 1 because that the largest rectangle we can find that contains only 1's.

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

This is just Connected Component of graph theory problem I think (unless I am missing something?). So the solution would be to scan for the first black node, and then from there it's just a breadth or depth first search of "connected' nodes (that is, adjacent black ones) where that node hasn't already been visited. A recursive call passing int references for the min/max of x/y will yield the min rectangle coordinates. I did this is C# and can post that or convert to C++ since that seems to be preferred here. From wikipedia on Connected Component "It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning."

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

in C#

static int[][] PreCompute(int[][] matrix)
{
int rank = matrix.Length;
int[][] sum = new int[matrix.Length][];
for (int i = 0; i < matrix.Length; ++i)
{
sum[i] = new int[rank];

for (int j = 0; j < matrix.Length; ++j)
{
if (i == 0)
{
sum[i][j] = matrix[i][j];
}
else
{
sum[i][j] = sum[i-1][j] + matrix[i][j];
}
}
}

return sum;
}

static int FindMaxBlacks(int[][] matrix)
{
int[][] sum = PreCompute(matrix);
int x1 = 0;
int x2 = 0;
int y1 = 0;
int y2 = 0;
int maxSum = 0;
for (int i = 0; i < matrix.Length; ++i)
{
for (int j = i; j < matrix.Length; ++j)
{
int currentSum = 0;
int start = -1;
int end = -1;
for (int k = 0; k < matrix.Length; ++k)
{
int value = sum[j][k] - sum[i][k] + matrix[i][k];
if (value == j - i + 1)
{
if (start == -1)
{
start = k;
end = k;
}
else
{
end = k;
}
currentSum += value;
}
else
{
if (currentSum > maxSum)
{
x1 = i;
x2 = j;
y1 = start;
y2 = end;
maxSum = currentSum;
}

currentSum = 0;
start = -1;
end = -1;
}
}
}
}
Console.WriteLine("start = ({0}, {1}), end = ({2}, {3})", x1, y1, x2, y2);
return maxSum;
}

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

``````import sys

min_x = min_y = sys.maxint
max_x = max_y = -1

cur_y = -1

for line in sys.stdin:
cur_y = cur_y + 1
nodes = [int(token) for token in line.strip().split()]
if 1 in nodes:
max_y = cur_y
if min_y == sys.maxint:
min_y = cur_y
if nodes.index(1) < min_x:
min_x = nodes.index(1)
nodes.reverse()
i = len(nodes) - 1 - nodes.index(1)
if i > max_x:
max_x = i

print min_x, min_y, max_x, max_y``````

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

#include<stdio.h>

void findSmallestRect(int matrix, int rows, int cols);

int main(void)
{

int matrix =
{
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};

findSmallestRect(matrix, 6, 6);

return 0;

}

void findSmallestRect(int matrix, int rows, int cols)
{

bool rectCreated = false;

int top;
int bottom;

int left;
int right;

for(int row = 0; row < rows; row++)
{

for(int col = 0; col < cols; col++)
{

if(matrix[row][col])
{

if(!rectCreated)
{

top = row;
bottom = row;

left = col;
right = col;

rectCreated = true;

}
else
{

if(row < top)
{
top = row;
}
else if(row > bottom)
{
bottom = row;
}

if(col < left)
{
left = col;
}
else if(col > right)
{
right = col;
}

}

}

}

}

printf("Top: %d\n", top);
printf("Bottom: %d\n", bottom);

printf("Left: %d\n", left);
printf("Right: %d\n", right);

}

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

``````#include<stdio.h>

void findSmallestRect(int matrix, int rows, int cols);

int main(void)
{

int matrix =
{
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0}
};

findSmallestRect(matrix, 6, 6);

return 0;

}

void findSmallestRect(int matrix, int rows, int cols)
{

bool rectCreated = false;

int top;
int bottom;

int left;
int right;

for(int row = 0; row < rows; row++)
{

for(int col = 0; col < cols; col++)
{

if(matrix[row][col])
{

if(!rectCreated)
{

top = row;
bottom = row;

left = col;
right = col;

rectCreated = true;

}
else
{

if(row < top)
{
top = row;
}
else if(row > bottom)
{
bottom = row;
}

if(col < left)
{
left = col;
}
else if(col > right)
{
right = col;
}

}

}

}

}

printf("Top: %d\n", top);
printf("Bottom: %d\n", bottom);

printf("Left: %d\n", left);
printf("Right: %d\n", right);

}``````

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

``````package com.google.practice;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Pointe implements Comparable<Pointe>{
int x;
int y;
int pointSpot;
public Pointe(int x,int y,int pointSpot){
this.x = x;
this.y = y;
this.pointSpot = pointSpot;
}
@Override
public int compareTo(Pointe o) {
// TODO Auto-generated method stub
return Double.compare(this.pointSpot, o.pointSpot);
}
}

public class BlacknWhite {
public static void main(String[] arg){
int n=5,m=5;
int[][] board = {{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,0},
{0,0,0,0,1}};

findMinRec(board,n,m);
}

public static void findMinRec(int[][] board,int n,int m){
List<Pointe> corner = findTopCorner(board,n);
Collections.sort(corner);
if(corner.size()==0)
System.out.println("No Black found");
else if(corner.size()==1)
printResult(corner.get(0).x, corner.get(0).y, corner.get(0).x, corner.get(0).y);
else if(corner.size()==4 || (corner.get(0).pointSpot==1 && corner.get(1).pointSpot==2)){
int x1 = corner.get(0).x,y1= corner.get(0).y,x2 = corner.get(1).x,y2 = corner.get(1).y;
if(corner.size()==4 || corner.size()==3){
if( corner.size()==3){
if(corner.get(2).pointSpot==3){
}else
Collections.sort(corner);
}
if(corner.get(3).y < corner.get(0).y)
y1 = corner.get(3).y;

if(corner.get(2).x<corner.get(0).x)
x1 = corner.get(2).x;

if(corner.get(2).y>corner.get(1).y)
y2 = corner.get(2).y;

if(corner.get(3).x>corner.get(1).x)
x2 = corner.get(3).x;

}
printResult(x1, y1, x2, y2);
}else{
if(corner.size()==3){
if(corner.get(0).pointSpot==1){
printResult(corner.get(0).x, corner.get(0).y, corner.get(1).y, corner.get(2).x);
}else{
printResult(corner.get(1).x, corner.get(2).y, corner.get(0).x, corner.get(0).y);
}
}else {
if(corner.get(0).pointSpot==2)
printResult(corner.get(1).x, corner.get(1).y, corner.get(0).x, corner.get(0).y);
else
printResult(corner.get(0).x, corner.get(0).y, corner.get(1).x, corner.get(1).y);
}
}
}

public static List<Pointe> findTopCorner(int[][] board,int n){
List<Pointe> points = new ArrayList<Pointe>();

boolean topLeft=false;Pointe tLeft = new Pointe(-1,-1,1);
boolean topRight=false;Pointe tRight = new Pointe(-1,-1,3);
boolean bottomLeft=false;Pointe bLeft = new Pointe(-1,-1,4);
boolean bottomRight=false;Pointe bRight = new Pointe(-1,-1,2);

for(int i1=0,i2=n-1;i1<=n/2;i1++,i2--){
for(int j1=0,j2=n-1;j1<=n/2;j1++,j2--){
if(points.size()==4)
return points;
if(!topLeft){
if(board[i1][j1]==1 || board[j1][i1]==1){
topLeft = true;
if(board[i1][j1]==1){
tLeft.x = i1;
tLeft.y = j1;
}
else{
tLeft.x = j1;
tLeft.y = i1;
}
}
}
if(!topRight){
if(board[i1][j2]==1 || board[j1][i2] == 1){
topRight = true;
if(board[i1][j2]==1){
tRight.x = i1;
tRight.y = j2;
}
else{
tRight.x = j1;
tRight.y = i2;
}
}
}
if(!bottomLeft){
if(board[i2][j1]==1 || board[j2][i1]==1){
bottomLeft = true;
if(board[i2][j1]==1){
bLeft.x = i2;
bLeft.y = j1;
}
else{
bLeft.x = j2;
bLeft.y = i1;
}
}
}
if(!bottomRight){
if(board[i2][j2]==1 || board[j2][i2]==1){
bottomRight = true;
if(board[i2][j2]==1){
bRight.x = i2;
bRight.y = j2;
}
else{
bRight.x = j2;
bRight.y = i2;
}
}
}
}
}
return points;
}

public static void printResult(int x1,int y1,int x2,int y2){
System.out.println("("+x1+","+y1+")-("+x2+","+y2+")");
}
}``````

Good or bad, this also works for 1's that are not connected. Finds the enclosing minimum rectangle. O(n^2) but pruned to 1/4th of total time.

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.