## Google Interview Question for Applications Developers

• 2

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 9 vote

flood fill algo.

Comment hidden because of low score. Click to expand.
5
of 7 vote

It can be done with recursion. Just check for adjacent elements while also keeping track of out of bounds of array. Here is the code. You can test it:

``````#include <stdio.h>
#include <stdlib.h>

void convertToNextColor(char arr,int i,int j)
{
if(i<0||j<0)
return;
else if(i>5||j>5)
return;
else
{
if(arr[i][j]=='B')
{
convertToNextColor(arr,i,j-1);
arr[i][j]='W';
convertToNextColor(arr,i,j+1);
arr[i][j]='W';
convertToNextColor(arr,i-1,j);
arr[i][j]='W';
convertToNextColor(arr,i+1,j);
arr[i][j]='W';
}
else
return;
}
}
int main()
{
char a={{'W','B','W','W','B','W'},{'B','B','W','W','B','W'},{'W','B','B','B','W','B'},{'W','B','W','W','B','B'}};
int i,j;
convertToNextColor(a,1,1);
for(i=0;i<4;i++)
{
for(j=0;j<6;j++)
printf(" %c ",a[i][j]);
printf("\n");
}
}``````

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

So what's exactly is required yo be done?

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

i think,you need to convert the screen into any 1 color completely by clicking on pixels..find a way to do so..m not sure...

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

IMO, You will be given number of clicks. You need to give the answer after 'N' clicks.

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

That's the simple flood fill algo, for which the iterative implementation is given below:

``````#include <stdio.h>
#include <queue>
#include <vector>

using std::queue;
using std::vector;

typedef vector<int> ivec;
typedef vector<ivec> itab;

struct coord {
int x;
int y;
coord(int cx, int cy) : x(cx), y(cy) {};
};

void print(const itab& tab)
{
for (int j = 0; j < tab.size(); ++j){
int cc = tab[j].size();
for (int i = 0; i < cc; ++i){
printf("%-3d ", tab[j][i]);
}
printf("\n");
}
}

void init_table(int* dat, int cy, int cx, itab& tab)
{
tab.resize(cy);

for (int j = 0; j < cy; ++j){
tab[j].resize(cx);

for (int i = 0; i < cx; ++i){
;//tab
int v = dat[j * cx + i];
//printf("%d ", v);

tab[j][i] = v;
}
}
}

void flood_fill(itab& dat, int py, int px, int color)
{
int rc, cc;
if (dat.size() == 0)
return;
if (dat.size() == 0)
return;

rc = dat.size();
cc = dat.size();

if (px < 0 || px >= cc)
return;
if (py < 0 || py >= rc)
return;

int val = dat[py][px];

std::queue<coord> q;
q.push(coord(px, py));

while(!q.empty()){
coord c = q.front();
q.pop();

dat[c.y][c.x] = color;
// now add the neighbours of this cell to the queue
// if the neighbour has the same color as this cell
if (c.x - 1 > 0 && dat[c.y][c.x - 1] == val)
q.push(coord(c.x - 1, c.y));

if (c.x + 1 < cc && dat[c.y][c.x + 1] == val)
q.push(coord(c.x + 1, c.y));

if (c.y - 1 > 0 && dat[c.y - 1][c.x] == val)
q.push(coord(c.x, c.y - 1));

if (c.y + 1 < rc && dat[c.y + 1][c.x] == val)
q.push(coord(c.x, c.y + 1));

}
}

int main()
{
int dat[] = {
1,  1,  3,  4,
5,  1,  1,  8,
9,  1,  10,  12,
13, 1,  4,  16,
17, 1,  1,  1
};

itab tab;
init_table(dat, 5, 4, tab);
print(tab);

printf("\n===============\n");

flood_fill(tab, 0, 0, 0);
print(tab);

return 0;
}``````

Output:

``````1   1   3   4
5   1   1   8
9   1   10  12
13  1   4   16
17  1   1   1

===============
0   0   3   4
5   0   0   8
9   0   10  12
13  0   4   16
17  0   0   0``````

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

All the neighbours of the pixel (x,y) selected have to be changed including the current pixel.
There are 8 neighbours for a pixel.
(x-1, y-1)
(x-1, y)
(x-1, y+1)
(x, y-1)
(x, y+1)
(x+1, y-1)
(x+1, y)
(x+1, y+1)
for all these pixels the color will be the same as the new color of the clicked pixel at (x,y)

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

forget one thing, need to check for the boundary conditions.

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

Here's my implementation of the algorithm. I used the recursive approach since it's much easier to understand. It is important to change the value in cell (i,j) BEFORE diving into the recursive calls, because if not you can end up with infinite recursive calls. Here's the C++ implementation:

``````#include <iostream>

using namespace std;

void PrintMat(int ** matrix, int height, int width)
{
for(int r = 0; r < height;r++)
{
for(int c = 0; c < width;c++)
cout<<matrix[r][c]<<" ";

cout<<endl;
}
}

void ChangeColor(int & val)
{
if(val==1)
val = 0;
else
val = 1;
}

void ChangePixels(int ** matrix, int rows, int cols, int r, int c)
{
if(r<0 || r >= rows || c<0 || c>=cols)
return;

int val = matrix[r][c];

ChangeColor(matrix[r][c]);

if(r>0 && val == matrix[r-1][c])
ChangePixels(matrix, 5, 5, r-1, c);

if(r<rows-1 && val == matrix[r+1][c])
ChangePixels(matrix, 5, 5, r+1, c);

if(c>0 && val == matrix[r][c-1])
ChangePixels(matrix, 5, 5, r, c-1);

if(c<cols-1 && val == matrix[r][c+1])
ChangePixels(matrix, 5, 5, r, c+1);
}

void main(void)
{
int **matrix = new int*;
int height = 5;
int width = 5;

int a[] = { 0, 1, 0, 0, 0};
int b[] = { 0, 1, 0, 1, 1};
int c[] = { 1, 1, 0, 0, 1};
int d[] = { 0, 1, 1, 0, 1};
int e[] = { 0, 1, 0, 0, 1};

matrix = a;
matrix = b;
matrix = c;
matrix = d;
matrix = e;

ChangePixels(matrix, 5, 5, 2, 1);

PrintMat(matrix, 5, 5);
}``````

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

This was great ... Flood fill algorithm .. hmm

i came with a totally different approach but I think it will work well though.
Can anybody comment about my approach.
Make each entry as a vertex in graph and make its adjacent elements as adjacent nodes.
Algorithm:
Push the clicked vertex to the queue.

while(queue not empty)
pop the element from queue
push the adj nodes which are only B in to the queue (and toggle their color)

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

My comment is that you are building a large graph to represent a data structure that already could be considered this way and also needing to creating vertices and edges that the traditional algorithm would ignore. If you want to think of your matrix or bitmap as analogous to a graph where each pixel is a vertex and each neighboring pixel is connected to it by an edge then go crazy. Literally recreating the bitmap as a graph is not a good idea.

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

flood fill algorithm....its beautiful..

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

{{//first we need to check what the color is at a particular index..

void colorat(int *matrix[], int m, int n, int x, int y) //m, n are dimensions of the matrix, and x,y is //the current position
{
if(x<=0 || x>=m) return ;
if(y<=0 || y>=n ) return;

char color = matrix[x][y];

changecolor(matrix, x-1,y-1, color);
changecolor(matrix, x,y-1, color);
changecolor(matrix, x+1,y-1, color);
changecolor(matrix, x-1,y, color);
changecolor(matrix, x+1,y, color);
changecolor(matrix, x-1,y+1, color);
changecolor(matrix, x,y+1, color);
changecolor(matrix, x+1,y-1, color);

}

void changecolor(int *matrix[], int x, int y, char color)
{
if(matrix[i][j]!=color)
{
matrix[i][j]=color;
}
else return;
}

}}

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

``````package com.zhuyu_deng.test;

import java.util.Stack;

public class Test
{

private static void printMatrix(char[][] a)
{
for (int i = 0; i < a.length; ++i)
{
for (int j = 0; j < a[i].length; ++j)
{
System.out.print(a[i][j] + "  ");
}
System.out.println();
}
}

private static void floodFill(char[][] a, int x, int y)
{
class Node
{
public Node(int x, int y)
{
this.x = x;
this.y = y;
}

int x;
int y;
}

char orgColor = a[x][y];
char revColor = a[x][y] == 'W' ? 'B' : 'W';
int size = 0;

Node stack[] = new Node[a.length * a.length];
stack[size] = new Node(x, y);
while (size >= 0)
{
Node cur = stack[size];
size--;
a[cur.x][cur.y] = revColor;
if (cur.x - 1 >= 0 && orgColor == a[cur.x - 1][cur.y])
{
stack[++size] = (new Node(cur.x-1, cur.y));
}
if (cur.x + 1 < a.length && orgColor == a[cur.x + 1][cur.y])
{
stack[++size] = (new Node(cur.x+1, cur.y));
}
if (cur.y - 1 >= 0 && orgColor == a[cur.x][cur.y - 1])
{
stack[++size] = (new Node(cur.x, cur.y-1));
}
if (cur.y + 1 < a.length && orgColor == a[cur.x][cur.y + 1])
{
stack[++size] = (new Node(cur.x, cur.y + 1));
}
}

}

public static void main(String args[])
{
// int[] a = {-2,11,-4,13,-5,-2};
int[][] b = { { 0, -2, -7, 0 }, { 9, 2, -6, 2 }, { -4, 1, -4, 1 },
{ -1, 8, 0, -2 } };
int[][] matrix = { { 2, 3, 4, 1 }, { 1, 1, 3, 9 }, { 2, 2, 3, 1 },
{ 2, 2, 3, 1 } };
char a[][] = new char[][] { { 'W', 'B', 'W', 'W', 'B', 'W' },
{ 'B', 'B', 'W', 'W', 'B', 'W' },
{ 'W', 'B', 'B', 'B', 'W', 'B' },
{ 'W', 'B', 'W', 'W', 'B', 'B' } };

printMatrix(a);

floodFill(a, 2, 2);

System.out.println();

printMatrix(a);

}
}``````

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

``````import java.util.*;

public class Fill {

public static void print(char[][] a) {
System.out.println();
System.out.print(a.length);
for (char[] l : a) {
for (char c : l) {
System.out.print(c + " ");
}
System.out.println();
}
}

public static ArrayList<Point> checkAdj(char[][] a, int i, int j) {
ArrayList<Point> ps = new ArrayList<Point>();
char c = a[i][j];

int curI = i-1; int curJ = j;
if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a.length && (a[curI][curJ] == c))

curI = i+1; curJ = j;
if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a.length && (a[curI][curJ] == c))

curI = i; curJ = j-1;
if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a.length && (a[curI][curJ] == c))

curI = i; curJ = j+1;
if (curI >= 0 && curJ >= 0 && curI < a.length && curJ < a.length && (a[curI][curJ] == c))

return ps;
}

public static void fill(char[][] a, int i, int j, char f) {

ArrayList<Point> ps = checkAdj(a, i, j);
//
a[i][j] = f;

for (Point p: ps) {
fill(a, p.i, p.j, f);
}
}

public static void main (String[] args) throws FileNotFoundException {
char a[][] = new char[][] { { 'W', 'B', 'W', 'W', 'B', 'W' },
{ 'B', 'B', 'W', 'W', 'B', 'W' },
{ 'W', 'B', 'B', 'B', 'W', 'B' },
{ 'W', 'B', 'W', 'W', 'B', 'B' } };
print(a);
fill(a, 1, 1, 'L');
print(a);
}
}

class Point{
int i;
int j;

Point(int i, int j) {this.i = i; this.j = j;}
}``````

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

I think BFS can do the job as well. Pass the node that is recently clicked to the BFS as the starting node and then do a simple BFS walk onward. We should keep the previous color of the recently clicked node in a temporary variable, say prevColor. In the main loop of the BFS we should do something like:

``````while(!emptyStack())
{
ClickedNode=pop();
for(i=0;i<N;i++)
{
if(graph[ClickedNode][i]!=inf && color[i]==prevColor)
{
parent[i]=ClickedNode;
color[i]=NewColor; //i.e., ~prevColor
push(i);
}
}
}``````

Please correct me if there is a mistake in the above approach.

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

I forgot one condition in the above "if" and an instruction within its body. The correct one would be:

``````if(graph[ClickedNode][i]!=inf && color[i]==prevColor && visited[i]==0)
{
parent[i]=ClickedNode;
color[i]=NewColor;
visited[i]=1;
push(i);
}``````

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

A solution in Python:

``````W = 0
B = 1

def f(A, r, c, dir=None):

Nr = len(A)
Nc = len(A)

type = A[r][c]
A[r][c] = W if type == B else B

if dir!='L' and (c+1 < Nc):
if A[r][c+1] == type: f(A, r, c+1, dir='R')

if dir!='R' and (c-1 >= 0):
if A[r][c-1] == type: f(A, r, c-1, dir='L')

if dir!='U' and (r+1 < Nr):
if A[r+1][c] == type: f(A, r+1, c, dir='D')

if dir!='D' and (r-1 >= 0):
if A[r-1][c] == type: f(A, r-1, c, dir='U')

A = [[W,B,W,W,B,W],
[B,B,W,W,B,W],
[W,B,B,B,W,B],
[W,B,W,W,B,B]]

f(A, 2, 2)
for row in A:
print row``````

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

A solution in Python:

``````W = 0
B = 1

def f(A, r, c, dir=None):

Nr = len(A)
Nc = len(A)

type = A[r][c]
A[r][c] = W if type == B else B

if dir!='L' and (c+1 < Nc):
if A[r][c+1] == type: f(A, r, c+1, dir='R')

if dir!='R' and (c-1 >= 0):
if A[r][c-1] == type: f(A, r, c-1, dir='L')

if dir!='U' and (r+1 < Nr):
if A[r+1][c] == type: f(A, r+1, c, dir='D')

if dir!='D' and (r-1 >= 0):
if A[r-1][c] == type: f(A, r-1, c, dir='U')

A = [[W,B,W,W,B,W],
[B,B,W,W,B,W],
[W,B,B,B,W,B],
[W,B,W,W,B,B]]

f(A, 2, 2)
for row in A:
print row``````

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

So I am assuming this is simply how to make the pixels change color and there is no end goal (like turn the screen from black to white and count the number of clicks).

1. Initialize 2D array with 0's to represent color 1.
2. Initialize mouse event handler that returns point x,y on mouse click
3. Return x,y to the colorChange function
4. colorChange then flips pixels: (x,y) (x-1,y) (x+1,y) (x,y-1) (x,y+1) to the opposite value (0's to 1's, and 1's back to 0's) as long as their current value matches the value at x,y.
4a. You must utilize edge/corner checking to make sure you do not encounter ArrayOutOfBounds Exceptions.

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.