Google Interview Question for Software Engineer / Developers


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());
		
	}

}

- Anonymous January 25, 2015 | Flag Reply
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.

- ABCD March 02, 2015 | Flag
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.

- Paul January 24, 2015 | Flag Reply
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

- Source January 24, 2015 | Flag Reply
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);
        }
    }
}

- Akhilesh Pandey January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what are xi and xj?

- JY January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Akhilesh Pandey January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi dude, what is the counties?

- Anonymous January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Booshi January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can some one explain the question?

- hk86 January 24, 2015 | Flag Reply
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;
}

- Booshi January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nikhi January 25, 2015 | Flag Reply
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);
					}
				}
			}
		}
	}
}

- Sumeet Singhal January 25, 2015 | Flag Reply
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))
							{
								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);
	}

- akiremi January 26, 2015 | Flag Reply
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);

                }
            }

}

- Enkokow January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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];

}

- Enkokow January 26, 2015 | Flag
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[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));
    }
}

- wwu January 26, 2015 | Flag Reply
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[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));
    }
}

- wwu January 26, 2015 | Flag Reply
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[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;
}

- David Cottrell January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- npc January 29, 2015 | Flag
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[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).

- npc January 29, 2015 | Flag Reply
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);
    }
}

- Victor January 29, 2015 | Flag Reply
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[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));
    }
}

- zhangboryan March 08, 2015 | Flag Reply
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;
	}

- Anonymous March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

- Mudit Goel December 26, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

- Mudit Goel December 26, 2020 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More