Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
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.
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.
Implementation by modification of BFS
public static int countSameColorConnectedCell(char[][] a, Cell start)
{
if (a == null || (a.length == 0 && a[0].length == 0) || start == null)
{
return 0;
}
int count = 0;
Queue<Cell> queue = new LinkedList<>();
queue.add(start);
int row = a.length;
int col = a[0].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))
{
queue.add(new Cell(x, y, start.color));
}
}
}
}
}
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;
}
}
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)) {
done.Add(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[0] = "000000";
lines[1] = "0RRRR0";
lines[2] = "0R00R0";
lines[3] = "0R00R0";
lines[4] = "0RRRR0";
lines[5] = "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
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.
@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.
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?
Ok guys, as requested I put further clarifications to your questions in the original post.
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);
}
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 :)
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[0].length];
int maxArea = 0;
for(int i = 0; i < matrix.length; i++) {
for(int j = 0;j<matrix[0].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[0].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;
}
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[0]-1>=0:
if M[po[0]-1,po[1]]==1 and (po[0]-1,po[1]) not in list1 :
list1.append((po[0]-1,po[1]))
sum1=sum1+1
sum1=self.backtrack([po[0]-1,po[1]],list1,M,sum1)
if po[0]+1<=2:
if M[po[0]+1,po[1]]==1 and (po[0]+1,po[1]) not in list1:
list1.append((po[0]+1,po[1]))
sum1=sum1+1
sum1=self.backtrack([po[0]+1,po[1]],list1,M,sum1)
if po[1]-1>=0:
if M[po[0],po[1]-1]==1 and (po[0],po[1]-1) not in list1:
list1.append((po[0],po[1]-1))
sum1=sum1+1
sum1=self.backtrack([po[0],po[1]-1],list1,M,sum1)
if po[1]+1<=5:
if M[po[0],po[1]+1]==1 and (po[0],po[1]+1) not in list1:
list1.append((po[0],po[1]+1))
sum1=sum1+1
sum1=self.backtrack([po[0],po[1]+1],list1,M,sum1)
return sum1
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.
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][0]-1>=0:
if M[new[i][0]-1,new[i][1]]==1 and (new[i][0]-1,new[i][1]) not in new and (new[i][0]-1,new[i][1]) not in old and (new[i][0]-1,new[i][1]) not in current:
current.append((new[i][0]-1,new[i][1]))
if new[i][0]+1<=b:
if M[new[i][0]+1,new[i][1]]==1 and (new[i][0]+1,new[i][1]) not in new and (new[i][0]+1,new[i][1]) not in old and (new[i][0]+1,new[i][1]) not in current:
current.append((new[i][0]+1,new[i][1]))
if new[i][1]-1>=0:
if M[new[i][0],new[i][1]-1]==1 and (new[i][0],new[i][1]-1) not in new and (new[i][0],new[i][1]-1) not in old and (new[i][0],new[i][1]-1) not in current:
current.append((new[i][0],new[i][1]-1))
if new[i][1]+1<=l:
if M[new[i][0],new[i][1]+1]==1 and (new[i][0],new[i][1]+1) not in new and (new[i][0],new[i][1]+1) not in old and (new[i][0],new[i][1]+1) not in current:
current.append((new[i][0],new[i][1]+1))
for x in new:
old.append(x)
if not current:
break
new=[]
for y in current:
new.append(y)
current=[]
print len(old)
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)
public class GoogleAreaMatrix {
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);
}
}
}
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) {
LinkedList<int[]> queue = new LinkedList<int[]>();
boolean[][] visited = new boolean[matrix.length][matrix.length];
int[] pair = {row, col};
queue.addFirst(pair);
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[0] + dr[i];
int newC = point[1] + 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};
queue.addFirst(next);
}
}
return area;
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[0].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{
// reach a dead end
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;
}
}
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.
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.
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.
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[10][10] = { 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[][10], 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);
}
BFS
- Anonymous May 09, 2014