Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
8
of 10 vote

BFS

- Anonymous May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow, very detail answer.

- Anonymous May 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Avaln May 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anont July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- aviundefined September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Indra Bayu May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous May 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This seems to fail for the second example, your counting all cells of the same color in the entire matrix regardless if they are connected to the starting point.

- Anonymous May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Connected components solution should work here.

- Victor May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The updated clarifications should answer your questions.

- DotQ May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Anonymous May 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes that's one way to do it but programmatically you should be able to calculate the area in other ways, that's part of the problem to solve.

- DotQ May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can a cell be half colored I mean how can you form a circle out of equal sized squares

- DashDash May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can a cell be half colored I mean how can you form a circle out of equal sized squares

- DashDash May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ok guys, as requested I put further clarifications to your questions in the original post.

- DotQ May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorted for you, originally it was intentionally made small to make it compact but I fixed now if it causes confusion.

- DotQ May 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- rojordan May 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can anyone talk about the algorithm? Reading code is a pain.

- Fighter May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- byteattack May 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- JayHolla May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Raghvendra Singh May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Raghvendra Singh May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Raghvendra Singh May 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- hritupon May 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- Looper May 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fast Union Find Algorithm if we need to get area for different shapes:

* index all separate sets by Union-By-Size, with merging by elements count / rank O(α(N ^ 2))
* by providing any coordinates we area in O(1)

For only one shape with on point: DFS or BFS

- Paul May 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the shape can be a circle, do we need to detect that it is a circle and use formula for area of circle. Most of the code submitted here just calculate number of adjacent 1s which would not be correct for a circle?

- Anon1 May 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Strongly connected components at work.

- msmajeed9 May 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Avaln May 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what will be the the output of this? if starting point is at (0,0)
RRR0000000
R0RRRRRRR
R0R0000000
RRR0000000
??

- Sujon November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- J Reid February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- J Reid February 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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

- paxglobal May 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is horroable...

- oceanmaster.wang May 27, 2014 | Flag


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