## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

Use DFS to follow the pattern of x and count the number of 'x' s. you can also use BFS

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

``````/*

This has to be solved by using the flood-fill technique.

First pick a 'X' and flood fill to find all connected
X's and determine size. Call this area A1.

Next pick the next X. Before flood fill is done, check if
this X is in A1. If yes, then skip this X. If not, then
this X is in another disconnected area which has to be
determined. Call this area A2.

Now continue to the next X

In the end you have have areas A1, A2. .. An with sizes
S1, S2 .. Sn

Find max S

Please note that flood-fill will actually need to happen just
once for each disconnected area in the figure

*/``````

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

can you define what contiguous shape is? Thanks!

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

cant quite get the question. please explain

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

You are looking for the largest strongly connected component in that non-directed graph.
This is a linear time algorithm whereas it is linear in the number of vertices in this
example (sparse graph). How ever, to find all vertices you need to look at least once at
each element in the matrix. Therefore it is O(n*m) if n, m are the dimensions of the
matrix. It's easy to show that's the best conceivable runtime, thus no need for much
improvement or dp.

Be aware you do not actually need to construct the graph.

I assume connected means here if left, right, top or bottom square has an X (bottom left,
top right, etc.) is not considered. If that's wanted, just add this "moves" into the MOVE array below.

DFS can be implemented recursive and non-recursive. Below a non-recursive example in
C++ 11, modifying the input array for simplicity to remember visited fields.

``````#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

int getMaxShape(vector<vector<char>>& arr)
{
pair<int, int> MOVES[]{ { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };
int max_comp_size = 0;
for (size_t i = 0; i < arr.size(); ++i) {
for (size_t j = 0; j < arr[i].size(); ++j) {
if (arr[i][j] != 'X') continue;
arr[i][j] = '-';
int comp_size = 1;
stack<pair<size_t, size_t>> s({ {i, j} });
while (!s.empty()) {
auto u = s.top(); s.pop();
for (const auto& m : MOVES) {
pair<size_t,size_t> v { u.first + m.first, u.second + m.second };
if (v.first < arr.size() && v.second < arr[v.first].size()
&& arr[v.first][v.second] == 'X') {
arr[v.first][v.second] = '-'; // do not visit again
s.push(v);
comp_size++;
}
}
max_comp_size = max(max_comp_size, comp_size);
}
}
}
return max_comp_size;
}

int main()
{
vector<vector<char>> tc {
{'.', 'X', 'X', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', '.', 'X', '.', '.', 'X', 'X', '.', '.', 'X' },
{'.', '.', '.', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', 'X', '.', '.', '.', '.', '.', 'X', '.', '.' },
{'.', '.', 'X', 'X', 'X', '.', '.', 'X', 'X', '.', '.' },
{'.', '.', '.', '.', '.', 'X', 'X', '.', '.', '.', '.' }
};
cout << getMaxShape(tc);
}``````

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

``````int MaxShapeFromCell(vector<vector<char>> &m, int r, int c)
{
int size = 0;
stack<pair<int, int>> st;
st.push(pair<int, int>(r, c));
while (!st.empty()) {
auto cell = st.top();
st.pop();
r = cell.first;
c = cell.second;
if (r >= 0 &&
r < m.size() &&
c >= 0 &&
c < m[r].size() &&
m[r][c] == 'X')
{
++size;
m[r][c] = '.';
st.push(pair<int, int>(r + 1, c));
st.push(pair<int, int>(r - 1, c));
st.push(pair<int, int>(r, c + 1));
st.push(pair<int, int>(r, c - 1));
}
}
return size;
}

int MaxShape(vector<vector<char>> &m)
{
int max_size = 0;
for (int r = 0; r < m.size(); ++r) {
for (int c = 0; c < m[r].size(); ++c) {
max_size = max(max_size, MaxShapeFromCell(m, r, c));
}
}
return max_size;
}``````

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

DP Solution O(n2)

``````public static void main(String[] args)
{
char[][] fill = {
{'.', 'X', 'X', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', '.', 'X', '.', '.', 'X', 'X', '.', '.', 'X' },
{'.', '.', '.', 'X', 'X', 'X', 'X', '.', '.', '.', '.' },
{'.', '.', 'X', '.', '.', '.', '.', '.', 'X', '.', '.' },
{'.', '.', 'X', 'X', 'X', '.', '.', 'X', 'X', '.', '.' },
{'.', '.', '.', '.', '.', 'X', 'X', '.', '.', '.', '.' }
};

System.out.println(maxContagiousShape(fill));
}

public static int maxContagiousShape(char[][] fill){
int n = fill.length;
int m = fill[0].length;
int[][] dp = new int[n][m];

//for extreme left corner, max contagious size would be 1 if it is 'X'
if(fill[0][0] == 'X')
dp[0][0] = 1;

//contagious shapes in 1st row
for(int i = 1; i < m; i++){
if(fill[0][i] == 'X')
dp[0][i] = dp[0][i-1] + 1;
else
dp[0][i] = dp[0][i-1];
}

//contagious shapes in 1st column
for(int i = 1; i < n; i++){
if(fill[i][0] == 'X')
dp[i][0] = dp[i-1][0] + 1;
else
dp[i][0] = dp[i-1][0];
}

//fill up the remaining
for(int i = 1; i < n; i++){
int contX = 0;
for(int j = 1; j < m; j++){

if(fill[i][j] == 'X')
contX += 1;
else
contX = 0;

if(fill[i][j] == '.'){
if(fill[i-1][j] == 'X' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) +1;

if(fill[i-1][j] == 'X' && fill[i][j-1] == '.')
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) +1;

if(fill[i-1][j] == '.' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

if(fill[i-1][j] == '.' && fill[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

}else{
if(fill[i-1][j] == 'X' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j]+contX, dp[i][j-1] +1);

if(fill[i-1][j] == 'X' && fill[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j-1] +2);

if(fill[i-1][j] == '.' && fill[i][j-1] == 'X')
dp[i][j] = Math.max(dp[i-1][j]+contX, dp[i][j-1] +1);

if(dp[i-1][j] == '.' && dp[i][j-1] == '.')
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n-1][m-1];

}``````

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

int rows = 0;
int cols = 0;
char[][] arr = null;
getMaxShape(char[][] arr){
this.arr = arr;
Set<Node> visited = new HashSet<Node>();
int maxSize = 0;
rows = arr.length;
cols = arr[0].length;
for(int row = 0; row < arr.length; row++){
for(int col = 0; col < arr[0].length; col++){
if(arr[row][col] == ‘.’){
continue;
}
Node node = new Node(row, col);
if(!visited.contains(node)){
maxSize = Math.max(maxSize,dfs(node,visited)); }
}
return maxSize;
}

}

private int dfs(Node node,Set<Node> visited){
List<Node> nbrs = getNbrs(node);
int size = 1;
for(Node nbr : nbrs){
if(visited.contains(nbr)){
continue;
}
size+=dfs(nbr,visited);
}
return size;
}

private List<Node> getNbrs(Node node){
List<Node> nbrs = new ArrayList<Node>();
for(int i = node.row -1 ; i <= node.row + 1; i++){
for(int j = node.col -1 ; i <= node.col + 1; j++){
if( i==node.row && j == node.col){
continue;
}
if(isValid(i,j)){
}
}
}
return nbrs;
}

private boolean isValid(int row, int col){
return (row >= 0 && row < rows) && (col >=0 && col < cols) && arr[row][col] ==‘X’;
}

class Node {
int row;
int col;
public Node(int row, int col){
this.row = row;
this.col = col;
}
// implement hashCode() and equals()
}

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

``````int rows = 0;
int cols = 0;
char[][] arr = null;
getMaxShape(char[][] arr){
this.arr = arr;
Set<Node> visited = new HashSet<Node>();
int maxSize = 0;
rows = arr.length;
cols = arr[0].length;
for(int row = 0; row < arr.length; row++){
for(int col = 0; col < arr[0].length; col++){
if(arr[row][col] == ‘.’){
continue;
}
Node node = new Node(row, col);
if(!visited.contains(node)){
maxSize  = Math.max(maxSize,dfs(node,visited));			}
}
return maxSize;
}

}

private int dfs(Node node,Set<Node> visited){
List<Node> nbrs = getNbrs(node);
int size = 1;
for(Node nbr : nbrs){
if(visited.contains(nbr)){
continue;
}
size+=dfs(nbr,visited);
}
return size;
}

private List<Node> getNbrs(Node node){
List<Node> nbrs = new ArrayList<Node>();
for(int i = node.row -1 ; i <= node.row + 1; i++){
for(int j = node.col -1 ; i <= node.col + 1; j++){
if( i==node.row && j == node.col){
continue;
}
if(isValid(i,j)){
}
}
}
return nbrs;
}

private boolean isValid(int row, int col){
return (row >= 0 && row < rows) && (col >=0 && col < cols) && arr[row][col] ==‘X’;
}

class Node {
int row;
int col;
public Node(int row, int col){
this.row = row;
this.col = col;
}
// implement hashCode() and equals()
}``````

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

``````bool canMove(int x, int y) {
return (0 <= x and x < n) and (0 <= y and y < m) and (a[x][y] == 'X');
}

int getMaxShape() {
int res = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < m; j++) {
if (a[i][j] == 'X') {
dfs(i, j, cnt);
}
}
res = max(res, cnt);
}

return res;
}

void dfs(int x, int y, int& cnt) {
cnt++;
a[x][y] = '.';
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx * dx + dy * dy == 1) {
if (canMove(dx + x, dy + y)) {
dfs(dx + x, dy + y, cnt);
}
}
}
}
}``````

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

``````bool canMove(int x, int y) {
return (0 <= x and x < n) and (0 <= y and y < m) and (a[x][y] == 'X');
}

int getMaxShape() {
int res = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < m; j++) {
if (a[i][j] == 'X') {
dfs(i, j, cnt);
}
}
res = max(res, cnt);
}

return res;
}

void dfs(int x, int y, int& cnt) {
cnt++;
a[x][y] = '.';
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx * dx + dy * dy == 1) {
if (canMove(dx + x, dy + y)) {
dfs(dx + x, dy + y, cnt);
}
}
}
}
}``````

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

DFS solution for 8-neighbors condition in C++98

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

using namespace std;

#define M  11
#define N  6

void find_max_shape(vector<vector<int> > matrix, vector<vector<bool> >& visited, int row, int col, int& size){
if(row == -1 || col == -1 || row == N || col == M)
return;
if(matrix[row][col] == 1 && visited[row][col] == false){
visited[row][col] = true;
size++;
find_max_shape(matrix, visited, row - 1, col, size);
find_max_shape(matrix, visited, row - 1, col - 1, size);
find_max_shape(matrix, visited, row - 1, col + 1, size);
find_max_shape(matrix, visited, row, col - 1, size);
find_max_shape(matrix, visited, row, col + 1, size);
find_max_shape(matrix, visited, row + 1, col - 1, size);
find_max_shape(matrix, visited, row + 1, col, size);
find_max_shape(matrix, visited, row + 1, col + 1, size);
}
}

template <class T>
void display(vector<vector<T> > matrix){
for(int i = 0; i < matrix.size(); i++){
cout << "[";
for(int j = 0; j < matrix[i].size(); j++){
(j < matrix[i].size() - 1) ? cout << matrix[i][j] << ", " : cout << matrix[i][j];
}
cout  << "]" << endl;
}
}

int main(){
vector<vector<bool> > visited = vector<vector<bool> >(N);
int x[N][M] = {{0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1}, {0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
vector<vector<int> > matrix = vector<vector<int> > (N);
for(int i = 0; i < N; i++){
matrix[i] = vector<int> (x[i], x[i] + sizeof(x[i]) / sizeof(int));
visited[i] = vector<bool>(M, false);
}
display(matrix);
display(visited);
int max_shape = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
int size = 0;
find_max_shape(matrix, visited, i, j, size);
if(size > max_shape)
max_shape = size;
}
}
cout << max_shape << endl;

}``````

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

DP comes into picture only when there are overlapping sub-problems.It can be done through iterative BFS as well.

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

``````public int maxArea(char[][] board) {
int res = 0, curr = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'X) {
if ((i == 0 || board[i - 1][j] == '.') && (j==0 || board[i][j - 1] == '.') {
res = max(res, curr);
curr = 1;
} else {
curr++;
}
}
}
}
return Math.max(res, curr);``````

}

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.