CareerCup

This question is too confusing to understand w/o a diagram :-)

This looks like finding connected components in a graph.
Make each cell a node, its neighbours (with common side) are connected with edges, only if they have same color.
Use DFS/BFS -- O(V+E) -- to find the number of connected components and their color.
Count numbers of each type and report.

just wondering, is this an interview question for UI engineer position? or the front end (grwoth) engineer position?

Try region merging algorithm.

1. Initially, make each cell in the matrix as a separate region.
2. While (there is at least one region merged) 
3.      for each region
4.           find neighbors.
5.           if region can be merged with neighbor (i.e. color is same)
6.                merge the regions.

// Algorithm: For each color find the number of connected components where a connected component includes all cells that can be reached through same color.
// Use a variation of flood fill algorithm to find connected components
// Map black color to 1 (true) and white to 0 (false)

struct cell
{
      int color;
      bool visit;

      cell()
      {
        color = -1; visit = false;
      }
};

int getOriginal(bool** C, int n)
{
      //Copy Color matrix into B
      
      cell** B = new cell*[n];
      for(int i=0;i<n;i++)
      { 
           B[i] = new cell[n];
           
           for(j=0;j<n;j++)
           {
               B[i][j].color = C[i][j] == true? 1 : 0;
           }
      }

      reset(B,n);
      int numblack_regions = Count(1,B,n);
      
      reset(B,n);
      int numwhite_regions = Count(0,B,n);

      if(numblack_regions > numwhite_regions) return 1;
      if(numblack_regions < numwhite_regions) return 0;
      
     return 2;        
}

void reset(cell**B, int n)
{
      for(int i=0;i<n;i++)
      {
         for(int j=0;j<n;j++)
         {
            B[i][j].visit = false;
         }
      }

}

int Count(int color, cell** B, int n)
{
    int numregions = 0;

    while(true)
    {
          int x = -1, y = -1;
          
          pick_unvisited(B,n,x,y);

          if(x == -1 || y == -1) return num_regions;

          Fill(B,n,color,x,y);
          num_regions++; 
    }

}

Fill(cell**B, int n, int color, int x, int y)
{
      if(B[x][y].color != color || B[x][y].visit == true) return;

      B[x][y].visit = true;

      Fill(B,n,color,x+1,y+1);
      Fill(B,n,color,x-1,y+1);
      Fill(B,n,color,x-1,y-1);
      Fill(B,n,color,x+1,y-1);
      Fill(B,n,color,x,y+1);
      Fill(B,n,color,x+1,y);
      Fill(B,n,color,x,y-1);
      Fill(B,n,color,x-1,y);             
}

void pick_unvisited(cell**B, int n, int color, int& x, int& y)
{
      int x = -1. y = -1;

      for(int i=0;i<n;i++)
      {
         for(int j=0;j<n;j++)
         {
             if(B[i][j].color == color && B[i][j].visit == false)
             {
                x = i; y = j;
                return;
             }
         }
      }
}

I would use the simple colouring algorithm to find all the components (merging components if they have different marks but same color), and then just sum all components of the given colours considering merged ones.

A bit messy and JS, so sorry

{{
function getOriginalColor(carpet) {
var cell = 0;
var markCell = new checker();
for(var i = 0; i < carpet.length; i++) {
for(var j = 0; j < carpet[i].length; j++) {
markCell.check(i, j, carpet);
}
}
var white = markCell.sum(true);
var black = markCell.sum(false);
if(black == white) {
return 'white';
}
if(black > white) {
return 'black';
} else {
return 'white';
}
}

function checker() {
this.cell = 0;
this.coloredComps = [];
}

checker.prototype = {

sum: function(color) {
var sum = 0;
for(var i = 1; i < this.coloredComps.length; i++) {
if(this.coloredComps[i].color === color) {
if(!this.coloredComps[i].merged) {
sum++;
} else if(this.coloredComps[i].merged > i) {
sum++;
}
}
}
return sum;
},

mergeable: function(a, b) {
if(a == b) {
return false;
}
return this.coloredComps[a].color === this.coloredComps[b].color ? true : false;
},

merge: function(a, b) {
this.coloredComps[a].merged = b;
this.coloredComps[b].merged = a;
},

check:function(i, j, carpet) {
[[i - 1, j], [i - 1, j - 1], [i - 1, j + 1], [i, j - 1]].forEach(function(cs) {
var ii = cs[0];
var jj = cs[1];
if(ii >= 0 && ii < carpet.length && jj >= 0 && jj < carpet[ii].length) {
if(typeof carpet[i][j] === 'number' && this.mergeable(carpet[ii][jj], carpet[i][j])) {
this.merge(carpet[ii][jj], carpet[i][j]);
return;
}
if(this.coloredComps[carpet[ii][jj]].color === carpet[i][j]) {
carpet[i][j] = carpet[ii][jj];
}
}
}.bind(this))
if(typeof carpet[i][j] !== 'number') {
this.cell++;
this.coloredComps[this.cell] = { color: carpet[i][j] };
carpet[i][j] = this.cell;
}
}
}
}}

JavaScript

(function(){

  // Let's start with three test inputs for the three expected outputs (0,1,2)
  // We'll use 0 to identify a white cell and 1 for a black cell

  var a = [          // more white spots than black spots - answer is 0
    [0,0,0,0,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,1,1,0],
    [0,0,1,0,0,1,0],
    [0,0,1,0,1,1,0],
    [0,0,1,1,1,0,0]
  ];

  var b = [          // more black spots than white spots - answer is 1
    [0,0,0,0,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0],
    [0,0,1,0,1,1,0],
    [0,0,1,1,1,0,0]
  ];

  var c = [          // equal white spots and black spots - answer is 2
    [0,0,0,0,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,0,0,0],
    [0,0,1,1,1,0,0],
    [0,0,0,0,0,1,0],
    [0,0,1,0,1,1,0],
    [0,0,1,1,1,0,0]
  ];

  alert([getOriginalColor(a),getOriginalColor(b),getOriginalColor(c)]);

  // our expected output matches the actual output: [0,1,2] :)

})();

function getOriginalColor(a) {

  // We'll start by creating a tracking array that is identical in size to the
  // input array.
  // Each cell of the tracking array uses an object to identify the color of
  // the cell and also a flag to indicate whether or not that spot has been
  // visited.

  var b=[],i,j;
  for(i=0;i<a.length;i++) {
    b[i]=[];
    for(j=0;j<a[i].length;j++) b[i].push( { color: a[i][j], visit: false } );
  }

  var whiteCount = countSpots(b,0);

  // all cells of our tracking array will have been marked as visited
  // let's reset the tracking array
  //
  for(i=0;i<a.length;i++) for(j=0;j<a[i].length;j++) b[i][j].visit = false;

  var blackCount = countSpots(b,1);

  return blackCount == whiteCount ? 2 : (blackCount > whiteCount) & 1;

}

function countSpots(b,color) {

  var count = 0;

  while(true) {

    // find first available "unvisited" cell in [x,y] coords
    // if there are no unvisited cells, a is undefined
    //
    var a = pickUnvisited(b,color);

    // if there are no unvisited cells, we have our count - return it
    //
    if(!a) return count;

    // if we get here, there's more work to do
    // let's expand the unvisited cell into a "spot"
    //
    expandSpot(b,color,a[0],a[1]);

    // the tracking array has fully tracked the new spot
    // let's record our new spot
    //
    count++;

  }

}

function pickUnvisited(b,color) {

  var i,j;

  // we'll go through every cell and return the first one we find that hasn't
  // yet been visited
  //
  for(i=0;i<b.length;i++)
    for(j=0;j<b[i].length;j++)
      if(b[i][j].color == color && !b[i][j].visit) return [i,j];

  // if we get here, there are no unvisited cells
  // we'll return undefined to indicate this state
  //
  return undefined;

}

function expandSpot(b,color,x,y) {

  // first we'll check that x and y exists within the grid
  // then we'll ensure that the cell hasn't been visited before now and also
  // that it is also the color we're looking for. if any of these conditions
  // are not true then we leave immediately
  //
  if( x < 0 || x >= b.length || y < 0 || y >= b[x].length ||
    b[x][y].visit || b[x][y].color != color) return;

  // we found a new cell for our spot! let's mark it as visited
  //
  b[x][y].visit = true;

  // now, let's look all around us for other cells to add to our spot. there
  // are up to 8 cells we can look at; fewer if we're at an edge of the carpet
  // but we won't worry about that here (it's take care of by the initial
  // conditional statement of this recursive function). using "o" to represent
  // our current location, we want to look at each of the "x" cells:
  //
  //                                 x x x
  //                                 x o x
  //                                 x x x
  //
  // let's mark each cell of the map with [i,j] delta to our current position
  //
  //                        [-1,-1] [-1, 0] [-1,+1]
  //                        [ 0,-1] [ 0, 0] [ 0,+1]
  //                        [+1,-1] [+1, 0] [+1,+1]
  //
  // we can use two loops (3 x 3) to generate these deltas, and a conditional
  // to ensure we don't re-visit our current position (not absolutely necessary
  // since we've already marked the spot as visited)
  //
  var i,j;
  for(i=-1;i<2;i++)
    for(j=-1;j<2;j++)
      if(i != 0 || j != 0) expandSpot(b,color,x + i,y + j);

}

Here is a clean solution that I think summarize all the above comments. Please let me know what you think
Time complexity O(n2) – which is obviously the best possible
Space complexity O(1) – if can't change the original matrix, then O(n2) for a copy of the original matrix.
There is a matrix: 0 white , 1 black
Assume it is possible to change the original matrix, visited cells will be marked as: -1 white , 2 black
Just to go over all the N *N matrix . When there is a new spot ( white 0 / black 1 ) :
1. mark it as visited (-1/2)
2. count Black / white += 1
3. mark all the surrounded as visited ( +-1 row / column ). Recursively mark all surrounded of the surrounded if it just been changed from not visited to visited

Stage 3 is the key of the solution. Before continue with the main loop for new spots, we just have to mark as visited all the cells of the found spot. So it won't be counted twice.

def WhiteBlackCarpet ( matrix ):
    if not matrix : return "Tie"
    NumOfWhite = 0
    NumOfBlack = 0 
    N = len(matrix[0])
    for i in range(0,N):
        for j in range(0,N):
            
            if matrix[i][j] == 0: # new white spot
                NumOfWhite += 1
                matrix[i][j] == -1
                markSurrond(matrix,i,j,0)

                
            elif matrix[i][j] == 1: # new black spot 
                NumOfBlack += 1 
                matrix[i][j] == 2
                markSurrond(matrix,i,j,1)
                
    if NumOfWhite > NumOfBlack : return "White "     if NumOfWhite < NumOfBlack : return "black "     return "Tie"     
                 
            
def markSurrond (matrix,i,j,colorInd):
    
    if colorInd == 0: replaceVal = -1
    else: replaceVal = 2
    N = len(matrix[0])
    
    for k in range ( max(i-1,0)  ,min(i+2,N) ):
        for z in range ( max(j-1,0)  ,min(j+2,N) ):
            if matrix[k][z] == colorInd:
                matrix[k][z] = replaceVal
                markSurrond (matrix,k,z,colorInd)

White,
		Black;
	}
	
	public void isCarpetBlackOrWhite(Color[][] n) {
		// for each of the colors, 
			// for each of the unvisited cells,
				// do a dfs, get the count
		
		// return max of counts to be the color of the carpet
		Color[] colors = Color.values();
		boolean[][] visited = new boolean[n.length][n.length];
		int count[] = new int[colors.length];
		
		for(int i=0; i<n.length; i++) {
			for(int j=0; j<n.length; j++) {
				if(!visited[i][j]) {
					count[n[i][j].ordinal()]++;
					isCarpetBlackOrWhite(n, visited, i, j, colors[n[i][j].ordinal()]);
				}
			}
		}
		System.out.println(Arrays.toString(count));
		
	}
	
	public void isCarpetBlackOrWhite(Color[][] n, boolean[][] visited, int currRow, int currCol, Color color) {
		if(currRow < 0 || currRow >= n.length || currCol < 0 || currCol >= n.length)
			return;
		
		if(n[currRow][currCol].equals(color) && !visited[currRow][currCol]) {
			visited[currRow][currCol] = true;
			isCarpetBlackOrWhite(n, visited, currRow+1, currCol, color);
			isCarpetBlackOrWhite(n, visited, currRow-1, currCol, color);
			isCarpetBlackOrWhite(n, visited, currRow, currCol+1, color);
			isCarpetBlackOrWhite(n, visited, currRow, currCol-1, color);
			isCarpetBlackOrWhite(n, visited, currRow+1, currCol+1, color);
			isCarpetBlackOrWhite(n, visited, currRow-1, currCol-1, color);
			
		}
	}