Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

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

- Anonymous September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This should do the job in O(row * column) = O(tot_element) using BFS

def get_max_shapes(grid: [[str]]) -> int:
    seen = set()
    max_shapes = 0
    for row_index in range(len(grid)):
        for shape_index in range(len(grid[row_index])):
            if grid[row_index][shape_index] == 'X' and (row_index, shape_index) not in seen:
                queue = collections.deque([[(row_index, shape_index)]])
                seen.add((row_index, shape_index))
                path_shapes = 0
                while queue:
                    path = queue.popleft()
                    i, j = path[-1]
                    path_shapes += 1
                    cand_moves = ((i - 1, j), (i + 1, j), (i, j + 1), (i, j - 1))
                    for can in cand_moves:
                        if can not in seen and -1 < can[1] < len(grid[i]) and -1 < can[0] < len(grid):
                            if grid[can[0]][can[1]] == 'X':
                                queue.append(path + [can])
                                seen.add(can)
                if path_shapes > max_shapes:
                    max_shapes = path_shapes
    return max_shapes

- nicolarusso March 08, 2020 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

can you define what contiguous shape is? Thanks!

- tiandiao123 September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 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);
}

- Chris September 21, 2017 | Flag Reply
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

*/

- Makarand September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

cant quite get the question. please explain

- Gurmeet Singh September 21, 2017 | Flag Reply
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;
}

- Alex September 22, 2017 | Flag Reply
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];
    
  }

- sudip.innovates September 22, 2017 | Flag Reply
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){
visited.add(node);
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)){
nbrs.add(new Node(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()
}

- random September 22, 2017 | Flag Reply
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){
		visited.add(node);
		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)){
					nbrs.add(new Node(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()
	}

- random September 22, 2017 | Flag Reply
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);
					}
				}
			}
		}
	}

- ELDVN October 23, 2017 | Flag Reply
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);
					}
				}
			}
		}
	}

- ELDVN October 23, 2017 | Flag Reply
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;

}

- Anonymous October 24, 2017 | Flag Reply
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.

- koustav.adorable September 21, 2017 | Flag Reply
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);

}

- Anonymous September 26, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More