## Google Interview Question for Software Engineer / Developers

• 2

Country: -

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

``````public class CountryNumberCal {
private int m;
private int n;
private int matrix[][];
private boolean visited[][];

CountryNumberCal(int matrix[][], int m, int n) {
this.matrix = matrix; this.m = m; this.n = n;

visited = new boolean[m][n];
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
visited[i][j] = false;
}

private boolean canMove(int i, int j, int v){
if (i<0 || j<0 || i>=m || j>=n) return false;
if ((!isVisited(i,j)) &&  v==matrix[i][j])
return true;
return false;
}

private void DFS(int i, int j, int v){
if (canMove(i,j, v)){
visited[i][j] = true;

DFS(i-1,j, v); // up
DFS(i+1,j, v); // down
DFS(i,j-1, v); // left
DFS(i,j+1, v); // right
}
};

private boolean isVisited(int i, int j) {
return visited[i][j];
}
public int getCountryNumber(){
int count = 0;
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
if (!isVisited(i,j)){
count ++;
DFS(i,j, matrix[i][j]);
}

return count;
}

public static void main(String[] args) {
int m1[][]= {{1,1,1,0},{1,1,0,0},{0,0,0,1}};

CountryNumberCal m = new CountryNumberCal(m1, 3, 4);
System.out.println(m.getCountryNumber());

int m2[][]= {{1,1,1,1},{0,0,0,0},{1,0,0,1}};

m = new CountryNumberCal(m2, 3, 4);
System.out.println(m.getCountryNumber());

int m3[][]= {{1,0,1,1},{0,1,0,0},{0,0,1,1},{1,1,0,1}};

m = new CountryNumberCal(m3, 4, 4);
System.out.println(m.getCountryNumber());

}

}``````

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

this is 1 minor bug in your code. to check adjacent node, you only checked up, down, left, and right. The diagonal node should be checked and marked too. for example:
[[1,0,0,0]
[0,1,0,0]
[0,0,0,1]]

will be mark as 4 country with your code. but it is 3 country. Since two 1s are diagonally connected. And they are 1 country.

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

Country means a group of numbers that are connected (adjacent to each other). For his first example
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]

First country is
[[1,1,1,]
[1,1,]
[,,,]

likewise, second country then becomes all the zeros, and the third country is the one in the right bottom corner.

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

This is my algo

``````countries = 0
for( elements in matrix )
if element is not visited
countries++
dfs from element and mark similar elements in path as visited

print countries``````

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

We can use DFS to find the connected components. We will not want to step on an alien element while doing a DFS. The number of distinct DFS forests will be the number of countries.

``````bool visited[m][n];
int xi[]={0, 1, 1, 1, 0, -1, -1, -1};
int xj[]={1, 1, 0, -1, -1, -1, 0, 1};

int number_of_countries(int **country_map, int m, int n)
{
int i, j;
int count=0;

init();

for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(visited[i][j]==false)
{
count++;
dfs(i, j, m, n, country_map[i][j]);
}
}
}

return count;
}

void init(int m, int n)
{
int i, j;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
visited[i][j]=false;
}
}
}

void dfs(int i, int j, int m, int n, int country)
{
if(i<0 || j<0 || i>=m || j>=n)
return;

for(int k=0; k<8; k++)
{
if(i+xi[k]>=0 && i+xi[k]<m && j+xj[k]>=0 && j+xj[k]<n && visited[i+xi[k]][j+xj[k]]==false && country_map[i+xi[k]][j+xj[k]]==country)
{
visited[i+xi[k]][j+xj[k]]=true;
dfs(i+xi[k], j+xj[k], m, n, country);
}
}
}``````

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

what are xi and xj?

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

xi and xj contain the values needed to be added to i and j to get to adjacent cells.

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

hi dude, what is the counties?

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

Question:
[1,1,1,0]
[1,1,0,0]
[0,0,0,1]

Look at this like a 2D MAP where the neighbouring country will have different codes.

The 3 countries are

1. Country with area defined by 1, * contains all other countries.
[1,1,1,*]
[1,1,*,*]
[*,*,*,*]

2. Country with area defined by 0, * contains all other countries.
[*,*,*,0]
[*,*,0,0]
[0,0,0,*]

3. Country with area defined by 1, * contains all other countries.
[*,*,*,*]
[*,*,*,*]
[*,*,*,1]

So in total 3 countries.

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

can some one explain the question?

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

This is a BFS solution.
This starts at starting oint of the country and visits all the node which is in the same country.
Starts a new country the next time it loops and finds a node which is not visited.

It searches from (0,0), visits only those nodes which are already not visited.
Searches top, bottom, left and right of the current node in the search.

# => current node
* => neighbour nodes

[1 * 1 1 1 1 1 1]
[* # * 1 1 0 0 0]
[0 * 0 0 0 0 0 0]
[0 0 0 1 1 1 1 1]
[0 1 1 1 1 1 1 1]

``````bool bound(int i, int j, int visited[][])
{
return (i >= 0 && j >= 0 && i <= horizontal && j <= vertical && visited[i][j]);
}

int countCountries(int input[][] int horizontal, int vertical)
{
int count = 0;
Queue BFSQueue; // Stores i, j in each node
bool visited[horizontal][vertical] = FALSE;

for(int i = 0; i < horizontal; i++)
{
for(int j = 0; j < vertical; j++)
{
if(!visited[i][j])
{
// Starting location - start at (0, 0)
BFSQueue.push(i, j);
int countryCode = input[i][j];

// Increment country count
count++;

// Search boundary for this country
Node thisNode;
while((thisNode = BFSQueue.pop()) != NULL)
{
if(input[thisNode.i][thisNode.j] != countryCode)
continue;

visited[thisNode.i][thisNode.j] = TRUE;

if(bound(thisNode.i - 1, thisNode.j, visited))
BFSQueue.push(thisNode.i - 1, thisNode.j);

if(bound(thisNode.i, thisNode.j - 1, visited))
BFSQueue.push(thisNode.i, thisNode.j - 1);

if(bound(thisNode.i + 1, thisNode.j, visited))
BFSQueue.push(thisNode.i + 1, thisNode.j);

if(bound(thisNode.i, thisNode.j + 1, visited))
BFSQueue.push(thisNode.i, thisNode.j + 1);

}
}
}
}

return count;
}``````

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

This question is extremely vague. Can someone please explain the question?

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

This algorithm modifies the input matrix. If we don't want to modify the input, we can use another matrix to keep track of already visited neighbors.

``````class Countries {
public static void main (String [] args) {
int [][] matrix = {{1, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}};
System.out.println("Number of countries = " + getNumOfCountries(matrix));
}

public static int getNumOfCountries(int [][] matrix) {
int currentColor = -1;
int numOfCountries = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] != -1) {
colorNeighbors(i, j, matrix);
numOfCountries++;
}
}
}
return numOfCountries;
}

public static void colorNeighbors(int i, int j, int [][] matrix) {
int color = matrix[i][j];
matrix[i][j] = -1;
for (int m = -1; m <= 1; m++) {
for (int n = -1; n <= 1; n++) {
if (m + i >= 0 && n+ j >= 0 && m + i < matrix.length && n + j < matrix[m + i].length) {
if (matrix[m + i][n + j] == color) {
colorNeighbors(m + i, n + j, matrix);
}
}
}
}
}
}``````

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

I see most people have 2 for loops for traversing each cell in matrix, it isn't necessary with the following logic.

My approach is BFS, achieved by usage of queue. Starting from 0,0 coordinate, I find all the connected cells that is belong to the same country. When you are looking at neighbouring cells, you will also discover the edges that belongs to other countries, these are useful information, you will see how it is used later, I am storing these as HashSet. After the queue is emptied out, I have finished finding all the cells belong to current country, as well as the edges that belong to a different country (or countries). In order to look at the next country, I take out a edge coordinate and push into the queue, and start the whole process again.

``````struct Coor
{
public int col;
public int row;
}

public static int countOfCountries(int[,] matrix)
{
if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0)
{
return -1;
}

int count = 0;

bool[,] visitedCells = new bool[matrix.GetLength(0), matrix.GetLength(1)];
HashSet<Coor> edges = new HashSet<Coor>();

Queue<Coor> queue = new Queue<Coor>();
Coor start;
start.col = 0;
start.row = 0;
queue.Enqueue(start);
visitedCells[start.col, start.row] = true;

while(true)
{
while(queue.Count != 0)
{
// this is BFS traversal
Coor currentCoor = queue.Dequeue();
List<Coor> neighbours = getNeighbourCells(matrix, currentCoor);

// this is important
// edges can be long to one or multiple countries, so as we
// are looking at each coordinate, we need to remove it from
// edges hashset, so we don't have to look at it later.
edges.Remove(currentCoor);

foreach(Coor neighbour in neighbours)
{
bool isNeighbourVisited = visitedCells[neighbour.col, neighbour.row];
// we only care if neighbour is unvisited
if (!isNeighbourVisited)
{
// this is a connected cell belong to the same country
if (matrix[neighbour.col, neighbour.row] == matrix[currentCoor.col, currentCoor.row])
{
queue.Enqueue(neighbour);
visitedCells[neighbour.col, neighbour.row] = true;
}
// this is an edge
else
{
if (!edges.Contains(neighbour))
{
}
}
}
}
}
count++;

if (edges.Count == 0)
{
// no more edges to look at, which means we are done counting
break;
}

// push next edge into queue and find the next country
Coor nextEdge = edges.First();
queue.Enqueue(nextEdge);
}

return count;
}

private static List<Coor> getNeighbourCells(int[,] matrix, Coor coor)
{
List<Coor> neighbours = new List<Coor>();

Coor top;
top.col = coor.col;
top.row = coor.row - 1;
if (isValidCoor(matrix, top))
{
}

Coor left;
left.col = coor.col - 1;
left.row = coor.row;
if (isValidCoor(matrix, left))
{
}

Coor right;
right.col = coor.col + 1;
right.row = coor.row;
if (isValidCoor(matrix, right))
{
}

Coor bottom;
bottom.col = coor.col;
bottom.row = coor.row + 1;
if (isValidCoor(matrix, bottom))
{
}

return neighbours;
}

private static bool isValidCoor(int[,] matrix, Coor coor)
{
return coor.col >= 0 && coor.col < matrix.GetLength(0) && coor.row >= 0 && coor.row < matrix.GetLength(1);
}``````

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

C# implementation , basically modified DFS

``````static int FindNumberOfCountries(int[,] matrix)
{
var visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];
int count = 0;
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (int j = 0; j < matrix.GetLength(1); j++)
{
if (!visited[i, j] && matrix[i, j] == 0)
{
Visit(matrix, i, j, visited, 0);
count++;
}

if (!visited[i, j] && matrix[i, j] == 1)
{
Visit(matrix, i, j, visited, 1);
count++;
}
}
}
return count;
}

static void Visit(int[,] matrix, int i, int j, bool[,] visited, int p)
{
var xMod = new[] { 0, -1, -1, -1, 0, 1, 1, 1 };
var yMod = new[] { -1, -1, 0, 1, 1, 1, 0, -1 };
if (visited[i, j])
{
return;
}
visited[i, j] = true;
for (int k = 0; k < 8; k++)
{
var row = xMod[k] + i;
var col = yMod[k] + j;
if (IsValid(row, col, matrix, visited, p))
{
Visit(matrix, row, col, visited, p);

}
}``````

}

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

adding missed method from my previous c# solution

``````static bool IsValid(int row, int col, int[,] matrix, bool[,] visited, int p)
{
return row >= 0 && col >= 0 && row < matrix.GetLength(0) && col < matrix.GetLength(1) &&
matrix[row, col] == p && !visited[row, col];``````

}

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

``````/**
*
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?

For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.

another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4
*
*  Created by wwu on 1/26/15.
*/
public class num_of_countries {
public void bfs(int[][] matrix, boolean[][] visited, int i, int j, int
label){
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix.length ||
visited[i][j] || matrix[i][j] != label)
return;
visited[i][j] = true;
bfs(matrix, visited, i-1,j,label);
bfs(matrix, visited, i+1,j,label);
bfs(matrix, visited, i,j-1,label);
bfs(matrix, visited, i,j+1,label);
}
public int driver(int[][] matrix){
int count = 0;
boolean[][] visited = new boolean[matrix.length][matrix.length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix.length; j ++){
if(!visited[i][j]){
count++;
bfs(matrix, visited, i, j, matrix[i][j]);
}
}
}
return count;
}

public static void main(String[] args){
num_of_countries obj = new num_of_countries();
int[][] matrix = {{1,1,1,1},
{0,0,0,0},
{1,0,0,1}};
System.out.println(obj.driver(matrix));
}
}``````

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

``````/**
*
2D matrix with 0s and 1s. Try to find out how many countries in this matrix?

For example:
[[1,1,1,0]
[1,1,0,0]
[0,0,0,1]]
return 3, because one for 1s, one for 0s, and one for the last one.

another example:
[[1,1,1,1]
[0,0,0,0]
[1,0,0,1]]
return 4
*
*  Created by wwu on 1/26/15.
*/
public class num_of_countries {
public void bfs(int[][] matrix, boolean[][] visited, int i, int j, int
label){
if(i < 0 || i >= matrix.length || j < 0 || j >= matrix.length ||
visited[i][j] || matrix[i][j] != label)
return;
visited[i][j] = true;
bfs(matrix, visited, i-1,j,label);
bfs(matrix, visited, i+1,j,label);
bfs(matrix, visited, i,j-1,label);
bfs(matrix, visited, i,j+1,label);
}
public int driver(int[][] matrix){
int count = 0;
boolean[][] visited = new boolean[matrix.length][matrix.length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix.length; j ++){
if(!visited[i][j]){
count++;
bfs(matrix, visited, i, j, matrix[i][j]);
}
}
}
return count;
}

public static void main(String[] args){
num_of_countries obj = new num_of_countries();
int[][] matrix = {{1,1,1,1},
{0,0,0,0},
{1,0,0,1}};
System.out.println(obj.driver(matrix));
}
}``````

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

Way better than all these search-based approaches.
I do allocate a boolean though...

``````function findCountries(m) {
var totalCountries = 1;
for (var x = 1; x < m.length; x++) {
if(m[x] !== m[x - 1]) totalCountries++;
}

var curCountryConnected = false;
for (var y = 1; y < m.length; y++) {
if(m[y - 1] === m[y]) curCountryConnected = true;

for (var x = 1; x < m.length; x++) {
if(m[y][x] !== m[y][x - 1]) {
if(!curCountryConnected) totalCountries++;
}
curCountryConnected = false;
if(m[y - 1][x] === m[y][x]) curCountryConnected = true;
}
if(!curCountryConnected) {
totalCountries++;
}
curCountryConnected = false;
}

}``````

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

If you give the array

``````1, 0, 1
1, 1, 1``````

as input, the correct answer is 2 but I think your code will return 3.

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

This is a great place to use the union-find algorithm. It requires O(n) storage and O(n log n) time to solve this problem. In Python:

``````def countries(m):
rows, cols = len(m), len(m)
parent = [ i for i in xrange(rows * cols) ]
def root(idx):
while idx != parent[idx]:
idx = parent[idx]
return idx

for r in xrange(rows - 1):
for c in xrange(cols - 1):
i = root(r * cols + c)
j = root(r * cols + c + 1)
if i != j and m[r][c] == m[r][c + 1]:
parent[max(i, j)] = min(i, j)
i = min(i, j)
k = root( (r + 1) * cols + c )
if i != k and m[r][c] == m[r + 1][c]:
parent[max(i, k)] = min(i, k)

num_countries = 0
for i in xrange(rows * cols):
if parent[i] == i:
num_countries += 1
return num_countries``````

The code above actually has an O(n^2) worst case in theory. You can improve on this by augmenting the parent array with a child count and always making the index with a larger count the parent when connecting two indices (not shown above for the sake of brevity).

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

My solution in C#:

``````public class Matrix
{
public static int NumberOfCountries(int [,] a)
{
if (a == null || a.Length == 0)
{
return 0;
}

return CountCountries(a);
}

private static int CountCountries(int [,] a)
{
bool [,] b = new bool[a.GetLength(0), a.GetLength(1)];
int counter = 0;
for (int i = 0; i < a.GetLength(0); i++)
{
for (int j = 0; j < a.GetLength(1); j++)
{
if (a[i,j] != int.MinValue && !b[i,j])
{
Counter(a,b,i,j, a[i,j]);
counter++;
}
}
}

return counter;
}

private static void Counter(int[,]a, bool[,]b, int i, int j, int current)
{
if (i == a.GetLength(0) || i < 0 || j == a.GetLength(1) || j < 0 || a[i,j] != current)
return;

a[i,j] = int.MinValue;
b[i,j] = true;
Counter(a, b, i - 1, j, current);
Counter(a, b, i, j - 1, current);
Counter(a, b, i + 1, j, current);
Counter(a, b, i, j + 1, current);
}
}``````

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

Java Implementation by BFS

``````import java.util.*;
public class HowManyCountries{
public int countriesNum(int[][] graph) {
int res = 0;
if (graph == null || graph.length == 0 || graph.length == 0) {
return res;
}
boolean[][] visited = new boolean[graph.length][graph.length];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
if (!visited[i][j]) {
res++;
visited[i][j] = true;
bfs(graph, visited, queue, i, j, graph[i][j]);
}
}
}
return res;
}
private void bfs(int[][] graph, boolean[][] visited, Queue<MyClass> queue, int row, int col, int target) {
while (!queue.isEmpty()) {
MyClass cur = queue.poll();
if (cur.row - 1 >= 0 && !visited[cur.row - 1][cur.col] && graph[cur.row - 1][cur.col] == target) {
visited[cur.row - 1][cur.col] = true;
}
if (cur.col + 1 < visited.length && !visited[cur.row][cur.col + 1] && graph[cur.row][cur.col + 1] == target) {
visited[cur.row][cur.col + 1] = true;
}
if (cur.col - 1 >= 0 && !visited[cur.row][cur.col - 1] && graph[cur.row][cur.col - 1] == target) {
visited[cur.row][cur.col - 1] = true;
}
if (cur.row + 1 < visited.length && !visited[cur.row + 1][cur.col] && graph[cur.row + 1][cur.col] == target) {
visited[cur.row + 1][cur.col] = true;
}
}

}
class MyClass{
int row;
int col;
public MyClass(int row, int col) {
this.row = row;
this.col = col;
}
}
public static void main(String[] args) {
HowManyCountries code = new HowManyCountries();
int[][] graph = {
{1,1,1,0},
{1,1,0,0},
{0,0,0,1},
};
System.out.println(code.countriesNum(graph));
}
}``````

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

DFS- BRUTE Force

``````public static int countrysize(int[][]mat,int previous,int row,int col){
if(row==mat.length||col==mat.length||row<0||col<0){
return 0;
}
if(mat[row][col]!=previous||mat[row][col]==Integer.MIN_VALUE){ return 0;}
int current=mat[row][col];
mat[row][col]=Integer.MIN_VALUE;
int values=countrysize(mat,current,row+1,col)+ countrysize(mat,current,row,col+1)+countrysize(mat,current,row+1,col+1)+
countrysize(mat,current,row-1,col)+countrysize(mat,current,row,col-1)+countrysize(mat,current,row-1,col-1)+1;
return values;
}

public static int NumberofCountry(int[][]mat){
int count=0;
for(int i=0;i<mat.length;i++){
for(int j=0;j<mat.length;j++){
int val=countrysize(mat,mat[i][j],i,j);
if(val!=0){
count++;
}
}
}
return count;
}``````

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.