Google Interview Question
Software Engineer / DevelopersCountry: -
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.
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);
}
}
}
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.
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;
}
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);
}
}
}
}
}
}
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))
{
edges.Add(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))
{
neighbours.Add(top);
}
Coor left;
left.col = coor.col - 1;
left.row = coor.row;
if (isValidCoor(matrix, left))
{
neighbours.Add(left);
}
Coor right;
right.col = coor.col + 1;
right.row = coor.row;
if (isValidCoor(matrix, right))
{
neighbours.Add(right);
}
Coor bottom;
bottom.col = coor.col;
bottom.row = coor.row + 1;
if (isValidCoor(matrix, bottom))
{
neighbours.Add(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);
}
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);
}
}
}
/**
*
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[0].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[0].length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix[0].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));
}
}
/**
*
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[0].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[0].length];
for(int i = 0; i < matrix.length; i ++){
for(int j = 0; j < matrix[0].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));
}
}
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[0].length; x++) {
if(m[0][x] !== m[0][x - 1]) totalCountries++;
}
var curCountryConnected = false;
for (var y = 1; y < m.length; y++) {
if(m[y - 1][0] === m[y][0]) curCountryConnected = true;
for (var x = 1; x < m[0].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;
}
return totalCountries;
}
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[0])
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).
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);
}
}
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[0].length == 0) {
return res;
}
boolean[][] visited = new boolean[graph.length][graph[0].length];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[0].length; j++) {
if (!visited[i][j]) {
res++;
Queue<MyClass> queue = new LinkedList<MyClass>();
queue.add(new MyClass(i, j));
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) {
queue.add(new MyClass(cur.row - 1, cur.col));
visited[cur.row - 1][cur.col] = true;
}
if (cur.col + 1 < visited[0].length && !visited[cur.row][cur.col + 1] && graph[cur.row][cur.col + 1] == target) {
queue.add(new MyClass(cur.row, cur.col + 1));
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) {
queue.add(new MyClass(cur.row, cur.col - 1));
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) {
queue.add(new MyClass(cur.row + 1, cur.col));
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));
}
}
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;
}
<html>
<script>
var distinctCountry=0;
var Input = [[5,4,4],[4,3,4],[3,2,4],[2,2,2],[3,3,4],[1,4,4],[4,1,1]];
var DistinctCountryMap = [];
for (var i = 0; i < Input.length; i++) {
DistinctCountryMap[i] = [];
for (var j = 0; j < Input[i].length; j++) {
DistinctCountryMap[i][j] = 0;
}
}
function markAreaCountry(i, j, distinctCountry) {
DistinctCountryMap[i][j] = distinctCountry;
if ( Input[i-1] !== undefined && Input[i-1][j] === Input[i][j] && DistinctCountryMap[i-1] !== undefined && DistinctCountryMap[i-1][j] === 0) {
markAreaCountry(i-1, j, distinctCountry);
}
if ( Input[i+1] !== undefined && Input[i+1][j] === Input[i][j] && DistinctCountryMap[i+1] !== undefined && DistinctCountryMap[i+1][j] === 0) {
markAreaCountry(i+1, j, distinctCountry);
}
if ( Input[i] !== undefined && Input[i][j-1] === Input[i][j] && DistinctCountryMap[i] !== undefined && DistinctCountryMap[i][j-1] === 0) {
markAreaCountry(i, j-1, distinctCountry);
}
if ( Input[i] !== undefined && Input[i][j+1] === Input[i][j] && DistinctCountryMap[i] !== undefined && DistinctCountryMap[i][j+1] === 0) {
markAreaCountry(i, j+1, distinctCountry);
}
}
for (var i = 0; i < Input.length; i++) {
for (var j = 0; j < Input[i].length; j++) {
if (DistinctCountryMap[i][j] !== 0) {
continue;
}
distinctCountry++;
markAreaCountry(i, j, distinctCountry);
}
}
console.log('distinct countries', distinctCountry);
console.log('DistinctCountryMap', DistinctCountryMap);
</script>
</html>
<html>
<script>
var distinctCountry=0;
var Input = [[5,4,4],[4,3,4],[3,2,4],[2,2,2],[3,3,4],[1,4,4],[4,1,1]];
var DistinctCountryMap = [];
for (var i = 0; i < Input.length; i++) {
DistinctCountryMap[i] = [];
for (var j = 0; j < Input[i].length; j++) {
DistinctCountryMap[i][j] = 0;
}
}
function markAreaCountry(i, j, distinctCountry) {
DistinctCountryMap[i][j] = distinctCountry;
if ( Input[i-1] !== undefined && Input[i-1][j] === Input[i][j] && DistinctCountryMap[i-1] !== undefined && DistinctCountryMap[i-1][j] === 0) {
markAreaCountry(i-1, j, distinctCountry);
}
if ( Input[i+1] !== undefined && Input[i+1][j] === Input[i][j] && DistinctCountryMap[i+1] !== undefined && DistinctCountryMap[i+1][j] === 0) {
markAreaCountry(i+1, j, distinctCountry);
}
if ( Input[i] !== undefined && Input[i][j-1] === Input[i][j] && DistinctCountryMap[i] !== undefined && DistinctCountryMap[i][j-1] === 0) {
markAreaCountry(i, j-1, distinctCountry);
}
if ( Input[i] !== undefined && Input[i][j+1] === Input[i][j] && DistinctCountryMap[i] !== undefined && DistinctCountryMap[i][j+1] === 0) {
markAreaCountry(i, j+1, distinctCountry);
}
}
for (var i = 0; i < Input.length; i++) {
for (var j = 0; j < Input[i].length; j++) {
if (DistinctCountryMap[i][j] !== 0) {
continue;
}
distinctCountry++;
markAreaCountry(i, j, distinctCountry);
}
}
console.log('distinct countries', distinctCountry);
console.log('DistinctCountryMap', DistinctCountryMap);
</script>
</html>
- Anonymous January 25, 2015