Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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
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);
}
/*
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
*/
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;
}
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];
}
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()
}
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()
}
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);
}
}
}
}
}
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);
}
}
}
}
}
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;
}
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);
}
Use DFS to follow the pattern of x and count the number of 'x' s. you can also use BFS
- Anonymous September 21, 2017