Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
8
of 10 vote

BFS

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

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

You really want to review your understanding about basic graph algorithms, Sweetheart, this is by no mean could possibly be a breadth first search, it's depth first search. And given the data structure, it's not efficient to go with graph algorithms.

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

I believe he meant "BFS-like" that uses a Queue. It surely works. Have another [N][N] array where you mark whether a cell is counted, start from "s", and check for adjacent cells. Mark, count, and enqueue if the color matches, repeat until the queue becomes empty.

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

Implementation by modification of BFS

public static int countSameColorConnectedCell(char[][] a, Cell start)
{
if (a == null || (a.length == 0 && a.length == 0) || start == null)
{
return 0;
}

int count = 0;

int row = a.length;
int col = a.length;

boolean[][] visited = new boolean[row][col];

int iMove[] = { -1, 1, 0, 0 };
int jMove[] = { 0, 0, -1, 1 };

while (!queue.isEmpty())
{
Cell current = queue.poll();

int curI = current.i;
int curJ = current.j;

if (!visited[curI][curJ])
{
count++;
visited[curI][curJ] = true;
for (int i = 0; i < iMove.length; i++)
{
for (int j = 0; j < jMove.length; j++)
{
int x = curI + iMove[i];
int y = curJ + jMove[j];
if (isSafe(a, x, y, visited, start, row, col))
{
}
}
}

}
}
return count;
}

private static boolean isSafe(char[][] a, int i, int j, boolean[][] visited, Cell start, int row, int col)
{
if ((i >= 0 && i < row) && (j >= 0 && j < col) && (!visited[i][j]) && (a[i][j] == start.color))
{
return true;
}
return false;
}

public class Cell
{

int i;
int j;
char color;

public Cell(int i, int j, char color)
{
this.i = i;
this.j = j;
this.color = color;
}
}

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

My solution in C#

int CountArea(char [,] m, int N, char color, Tuple<int,int> s) {
if(m == null || N < 1)
throw new Exception("Wrong input");

var pending = new Queue<Tuple<int,int>>();
var done = new HashSet<Tuple<int,int>>();

Func<Tuple<int,int>, bool> eval = (candidate) => {
int a = candidate.Item1, b = candidate.Item2;
if(a >= 0 && a < N && b >= 0 && b < N &&
m[a,b] == color &&
!done.Contains(candidate) &&
!pending.Contains(candidate)) {
return true;
}
else
return false;
};

int i,j;
pending.Enqueue(s);
while(pending.Count != 0) {
var curr = pending.Dequeue();
if(eval(curr)) {
i = curr.Item1;
j = curr.Item2;
pending.Enqueue(new Tuple<int,int>(i-1, j)); //1. UP
pending.Enqueue(new Tuple<int,int>(i, j+1)); //2. RIGHT
pending.Enqueue(new Tuple<int,int>(i+1, j)); //3. DOWN
pending.Enqueue(new Tuple<int,int>(i, j-1)); //4. LEFT
}
}

return done.Count;
}

While the main method can be something like this:

static void Main(string[] args)
{
int N = 6;
char[,] matrix = new char[N,N];
string [] lines = new string [N];
lines = "000000";
lines = "0RRRR0";
lines = "0R00R0";
lines = "0R00R0";
lines = "0RRRR0";
lines = "000000";

for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
matrix[i, j] = lines[i][j];
}
}

Console.WriteLine(CountArea(matrix, N, '0', new Tuple<int, int>(0, 0)));
}

--

Indra Bayu
Vrije Universiteit Brussel

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

Looking at your code I have an impression that you are just counting adjacent cells which have the same color. It's not the shape.

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

This seems to fail for the second example, your counting all cells of the same color in the entire matrix regardless if they are connected to the starting point.

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

Connected components solution should work here.

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

@DotQ: Can you explain why the shape in you example is 10? You can create many shapes starting from (0,0) e.g first row shape = 9 or first column = 5.

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

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

is the area in the example is like 3 *4 - 2 = 10?
I mean its an area of a rectangle.
what will be the area of an irregular shape?

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

Yes that's one way to do it but programmatically you should be able to calculate the area in other ways, that's part of the problem to solve.

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

Can a cell be half colored I mean how can you form a circle out of equal sized squares

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

Can a cell be half colored I mean how can you form a circle out of equal sized squares

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

Ok guys, as requested I put further clarifications to your questions in the original post.

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

Sorted for you, originally it was intentionally made small to make it compact but I fixed now if it causes confusion.

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

C++ solution. Obviously it would require some exceptions for error checks but, good to go.

int  find_area_helper(char matrix[][N], bool visited_list[][N], int i,
int j) {
if (i < 0 || i == N || j < 0 || j == N)
return -1;
if (visited_list[i][j])
return 0;

int area = 1;
visited_list[i][j] = true;

for (int m = -1; m <= 1; m++) {
for (int n = -1; n <= 1; n++) {
if ((i + m < 0 || j + n < 0) || i + m == N || j + n == N)
continue;
if (m == 0 && n == 0)
continue;

if (!visited_list[i + m][j + n] && matrix[i + m][j + n] == 'R') {
area +=  find_area_helper(matrix, visited_list, i + m, j + n);
}
}
}

return area;
}

int find_area(char matrix[][N], int i, int j) {
if (matrix[i][j] != 'R')
return 0;

bool visitedList[N][N];

for (int m = 0; m < N; m++) {
for (int n = 0; n < N; n++) {
visitedList[m][n] = false;
}
}

return find_area_helper(matrix, visitedList, i, j);

}

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

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

It is a modified version of BFS. Since you have been given a starting point (node)
find its neighbors which match the value of the starting node. (top left down right) we don't need diagonal since the top left down right will cover those cases.

Save the nodes you have visited in a parent hashmap so that you don't visit them again. and just count the number of nodes in the parent hashmap in the end for the area :)

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

This code is tested and works, just using '1' instead of 'R's

public  int getMaxArea(int[][] matrix) {
boolean[][] used = new boolean[matrix.length][matrix.length];
int maxArea = 0;
for(int i = 0; i < matrix.length; i++) {
for(int j = 0;j<matrix.length;j++) {
if(matrix[i][j] == 1 && !used[i][j]) {
int curArea = areaCalc(matrix,i,j,used);
System.out.println("Cur area is: " +curArea);
if(curArea > maxArea)
maxArea = curArea;
}
}
}
return maxArea;
}

private int areaCalc(int[][] matrix, int x, int y , boolean[][] used) {
if(x < 0 || y < 0 || x > matrix.length-1 || y > matrix.length-1)
return 0;
if(matrix[x][y]!=1)
return 0;
int curArea=0;
if(matrix[x][y]==1 && !used[x][y]) {
curArea++;
used[x][y]=true;
int temp = matrix[x][y];
matrix[x][y]=-1;
curArea = 1 +  (areaCalc(matrix,x-1,y,used) + areaCalc(matrix,x+1,y,used)+
areaCalc(matrix,x,y-1,used) +areaCalc(matrix,x,y+1,used));
//System.out.println("Max area is: " + maxArea);
matrix[x][y]=temp;

return curArea;
}
return curArea;

}

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

class ar:
def __init__(self):
M=np.matrix('0,1,1,1,1,0;0,1,1,1,1,0;0,1,1,1,1,0')
spos=[0,2]

list1=[(0,2)] #starting position
sum1=1
sum1=self.backtrack(spos,list1,M,sum1)
print sum1

def backtrack(self,spos,list1,M,sum1):
b=2
l=5
po=spos

if po-1>=0:
if M[po-1,po]==1 and (po-1,po) not in list1 :
list1.append((po-1,po))
sum1=sum1+1

sum1=self.backtrack([po-1,po],list1,M,sum1)

if po+1<=2:
if M[po+1,po]==1 and (po+1,po) not in list1:
list1.append((po+1,po))
sum1=sum1+1
sum1=self.backtrack([po+1,po],list1,M,sum1)

if po-1>=0:
if M[po,po-1]==1 and (po,po-1) not in list1:
list1.append((po,po-1))
sum1=sum1+1
sum1=self.backtrack([po,po-1],list1,M,sum1)

if po+1<=5:
if M[po,po+1]==1 and (po,po+1) not in list1:
list1.append((po,po+1))
sum1=sum1+1

sum1=self.backtrack([po,po+1],list1,M,sum1)

return sum1

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

The matrix in the above code has 1 instead of R's.I have used the backtracking appproach to count the number of all the adjacent 1's .
b and l in the code are the matrix dimensions.Just change b and l according to the matrix you take as an example.

Time Complexity----
O(n) as we are taking into account all the adjacent 1's one by one.
Here n is the number of adjacent 1's in the matrix.

Space Complexity---
O(n) as we are storing the position of every adjacent 1 in the matrix.

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

import numpy as np

class ar:
def __init__(self):
M=np.matrix('0,1,1,1,1,0;0,1,1,1,1,0;0,1,1,1,1,0')
spos=[0,2]

list1=[(0,2)]
sum1=1

self.diffusion(list1,M)

def diffusion(self,list1,M):
old=[]
new=[(0,2)]
current=[]
b=2
l=5
while True:

for i in range(len(new)):
if new[i]-1>=0:
if M[new[i]-1,new[i]]==1 and (new[i]-1,new[i]) not in new and (new[i]-1,new[i]) not in old and (new[i]-1,new[i]) not in current:
current.append((new[i]-1,new[i]))

if new[i]+1<=b:
if M[new[i]+1,new[i]]==1 and (new[i]+1,new[i]) not in new and (new[i]+1,new[i]) not in old and (new[i]+1,new[i]) not in current:
current.append((new[i]+1,new[i]))

if new[i]-1>=0:
if M[new[i],new[i]-1]==1 and (new[i],new[i]-1) not in new and (new[i],new[i]-1) not in old and (new[i],new[i]-1) not in current:
current.append((new[i],new[i]-1))

if new[i]+1<=l:
if M[new[i],new[i]+1]==1 and (new[i],new[i]+1) not in new and (new[i],new[i]+1) not in old and (new[i],new[i]+1) not in current:
current.append((new[i],new[i]+1))

for x in new:
old.append(x)

if not current:
break
new=[]
for y in current:
new.append(y)

current=[]

print len(old)

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

The above code has used the diffusion method to count all the adjacent ones.
1) Maintain old,new and current lists.
2)Initially old list will be empty,new list will contain the starting position and current list will be empty.
3)Now in every iteration you calculate the positions of all the neighbours of all the elements present in new list and then store all these positions in the current list.
4)After that you merge the old and new list together.This merged list will become the old list and then you transfer all the elements of current list to new list and then empty the current list.So now you have all the three lists ready for the next iteration.
5)Repeat the entire process till the current list becomes empty.

Time Complexity---
1) O(n) as you are focussing on all the elements in new list to calculate their neighbours and the elements in new list are the ones which you are counting.
Here n is the number of adjacent ones which you will count.

2)Space Complexity---
O(n)

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

public static int[] ax={-1,-1,-1, 0, 0, 1, 1, 1};
public static int[] ay={-1, 0, 1,-1, 1,-1, 0, 1};
public static int area=0;
public static HashMap<String, Boolean> visited=new HashMap<String,Boolean>();
public static void main(String[] args) {
char[][] matrix=
{

{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','R','R','R','R','0','0','0','0','0','0','0'},
{'0','0','R','0','0','R','0','0','0','R','R','0','0'},
{'0','0','R','R','R','R','0','0','0','R','R','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
{'0','0','0','0','0','0','0','0','0','0','0','0','0'},
};
shape(matrix,5,2,13);
System.out.println(area);
}
public static void shape(char[][] matrix,int x, int y,int size){
String key=""+x+"_"+y;
if(visited.containsKey(key))return;
if(x>=size || y>=size)return;
if(matrix[x][y]!='R')return;
area++;
visited.put(key,true);
for(int i=0;i<ax.length;i++){
shape(matrix,x+ax[i], y+ay[i], size);
}
}

}

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

Simple BFS

private static int dr[] = {-1, 0, 1, 0};
private static int dc[] = {0, 1, 0, -1};
public static int getArea(char[][] matrix, int row, int col) {
boolean[][] visited = new boolean[matrix.length][matrix.length];
int[] pair = {row, col};
visited[row][col] = true;
int area =  0;
char color = matrix[row][col];
while (!queue.isEmpty()) {
int[] point = queue.removeLast();
area++;
for (int i=0; i<dr.length; i++) {
int newR = point + dr[i];
int newC = point + dc[i];
if (newR < 0 || newC < 0 || newR >= matrix.length || newC >= matrix.length || visited[newR][newC] || matrix[newR][newC] != color) {
continue;
}
visited[newR][newC] = true;
int[] next = {newR, newC};
}
}
return area;

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

Fast Union Find Algorithm if we need to get area for different shapes:

* index all separate sets by Union-By-Size, with merging by elements count / rank O(α(N ^ 2))
* by providing any coordinates we area in O(1)

For only one shape with on point: DFS or BFS

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

Since the shape can be a circle, do we need to detect that it is a circle and use formula for area of circle. Most of the code submitted here just calculate number of adjacent 1s which would not be correct for a circle?

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

Strongly connected components at work.

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

This can be solved as a back tracking problem. Basically we make an agreement on the order of directions for checking the next step, use a stack to track the steps we are passed, update possible directions for the current step when move on to the next step and whenever there is a new step, check if it is back to the start point.

This problem can also been seen as a graph DFS problem. Basically we are looking for the longest cycle in a undirected unweighted graph. But since the data structure doesn't support graph DFS algorithm and it's too much work to create an adjacency list from this input matrix, the back tracking way is easier.

int FindCycle(int[][] M, int i, int j){
if(M == null)
return 0;

int m = M.length();
int n = M.length();
if(i > m - 1 || j > n - 1 || i < 0 || j < 0)
return 0;

Stack<Step> s = new Stack<Step>();
int count = 1;
boolean isBack = false;
int startI = i;
int startJ = j;

Step start = new Step(i, j, true, true, true, true);// all four directions are enabled
while(s.size() > 0 && !isBack){
Step cur = s.pop();
if(cur.right && j+1 < n && isPath(M[i][j+1]){
int i = cur.row;
int j = cur.column;
cur.right = false;
Step next = new Step(i, j+1, true, true, false, true);// disable the left direction
if(i == startI and j == startJ){
isBack = true;
break;
}else{
count++;
s.push(next);
}
}else if(cur.down && i+1 < n && canBeIncluded(M[i+1][j]){
// move down. the directions should be set to true, true, true, false
}else if(cur.left && j-1 >= 0 && canBeIncluded(M[i][j-1]{
// move left. the directions should be false, true, true, true
}else if(cur.up && i-1 >= 0 && canBeIncluded(M[i-1][j]){
// move up. the directions should be true, false, true, true
}else{
s.pop();
count--;
}
}

if(isBack){
return count;
}

}

boolean canBeIncluded(int value){
// check if the current element can be included
}

Class Step{
int row;
int column;
boolean right;
boolean down;
boolean left;
boolean up;

public Step(int i, int j, boolean r, boolean d, boolean l, boolean u){
this.row = i;
this.column = j;
this.right = r;
this.down = d;
this.left = l;
this.up = u;
}
}

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

what will be the the output of this? if starting point is at (0,0)
RRR0000000
R0RRRRRRR
R0R0000000
RRR0000000
??

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

Here's my solution to this problem. Please correct me if I'm wrong, but I see the following points to this problem:

1. di --> rate of change in the array indexes is 1. Therefore,
2. The LxW of a single pixel should be 1x1, with an area of 1 for a single pixel. That said:
0 R 0 --> Area = 1, R R 0 --> area = 1x2 = 2

0 R 0				0 R 0
R 0 R --> Area = 4   	R R R  --> Area = 5
0 R 0 				0 R 0

My algorithm sums the colored pixels by row and sums for the area (given a start point or not).

That said:

int start_row = 3, start_col = 4, N = 5; //assume NxN matrix
int matrix [][[] = {{.......}};

int iterator = start_col, area = 0;

//Start counting backwards from start column
while(iter >= 0){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter--;
}
iter = scol + 1;
while(iter < N){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter++;
}

cout << area<<endl;

Each pixel is a 1x1 block of area 1, therefore simply counting the blocks with colors will give you the total area of the shape.

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

Here's my solution to this problem. Please correct me if I'm wrong, but I see the following points to this problem:

1. di --> rate of change in the array indexes is 1. Therefore,
2. The LxW of a single pixel should be 1x1, with an area of 1 for a single pixel. That said:
0 R 0 --> Area = 1, R R 0 --> area = 1x2 = 2

0 R 0				0 R 0
R 0 R --> Area = 4   	R R R  --> Area = 5
0 R 0 				0 R 0

My algorithm sums the colored pixels by row and sums for the area (given a start point or not).

That said:

int start_row = 3, start_col = 4, N = 5; //assume NxN matrix
int matrix [][[] = {{.......}};

int iterator = start_col, area = 0;

//Start counting backwards from start column
while(iter >= 0){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter--;
}
iter = scol + 1;
while(iter < N){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter++;
}

cout << area<<endl;

Each pixel is a 1x1 block of area 1, therefore simply counting the blocks with colors will give you the total area of the shape.

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

Here's my solution to this problem. Please correct me if I'm wrong, but I see the following points to this problem:

1. di --> rate of change in the array indexes is 1. Therefore,
2. The LxW of a single pixel should be 1x1, with an area of 1 for a single pixel. That said:
0 R 0 --> Area = 1, R R 0 --> area = 1x2 = 2

0 R 0				0 R 0
R 0 R --> Area = 4   	R R R  --> Area = 5
0 R 0 				0 R 0

My algorithm sums the colored pixels by row and sums for the area (given a start point or not).

That said:

int start_row = 3, start_col = 4, N = 5; //assume NxN matrix
int matrix [][[] = {{.......}};

int iterator = start_col, area = 0;

//Start counting backwards from start column
while(iter >= 0){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter--;
}
iter = scol + 1;
while(iter < N){
for(int i = 0;i < N;i++){ if( matrix[iter][i] != 0)area +=1;}//Assuming 2. (above stands)
iter++;
}

cout << area<<endl;

Each pixel is a 1x1 block of area 1, therefore simply counting the blocks with colors will give you the total area of the shape.

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

Do in 2 pass - first set all ajacent elements in -1 and then count all -1.

int countArea(int x, int y, int value){
// area
int arr = { 0,0,0,0,0,0,0,0,0,0,
0,1,1,0,1,0,1,0,0,0,
0,1,0,1,0,0,1,1,1,0,
0,1,1,1,0,1,0,0,0,0,
1,1,1,0,1,0,0,0,0,0,
1,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0 };

pass1(arr, x, y, value);

int count = 0;
for(int i=0; i < 10; i++){
cout << "row:" << i << ":";
for(int j=0;j < 10; j++){
cout << arr[i][j] << ",";
if(arr[i][j] == -1)
count++;
}
cout << "\n";
}

return count;
}

void pass1(int arr[], int x, int y, int value){
// pass 1
if(x < 0 || y < 0)
return;
if(arr[x][y] == 0)
return;
else if(arr[x][y] == value)
arr[x][y] = -1;

if(arr[x][y+1] == 1)
pass1(arr, x,y+1, value);
if(arr[x][y-1] == 1)
pass1(arr, x,y-1, value);
if(arr[x+1][y+1] == 1)
pass1(arr, x+1,y+1, value);
if(arr[x+1][y-1] == 1)
pass1(arr, x+1,y-1, value);
if(arr[x-1][y+1] == 1)
pass1(arr, x-1,y+1, value);
if(arr[x-1][y-1] == 1)
pass1(arr, x-1,y-1, value);
if(arr[x+1][y] == 1)
pass1(arr, x+1,y, value);
if(arr[x-1][y] == -1)
pass1(arr, x-1,y, value);
}

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

This is horroable...

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.