Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
+1 Cool. I actually didn't realize this problem could be solved without labeling the components. Probably because most real-world algorithms that do something like this (image segmentation) would be interested in extracting the components.
Once you have whitened out a black component, where would you start your next search from ? I suppose we have to start over from the begining again.
You could traverse the entire matrix and store the black points in a map by their xy-coord. Then pick an element from the map and work out from there, removing any black points you encounter from the map. Then, after you've exhausted a black component, pick another point from the map and repeat the process.
Good point Manan. We need a lot more information to begin to solve this question. For example (say 1 is white and 0 is black)
1 1 1 1 0 0
1 1 0 0 0 0
0 0 0 0 0 0
How many connected components are there? Since that is a bunch of 1s together, do they count as 1 connected component or do we count multiple components (provided that we pair them in groups of 2).
If its the former (the entire bunch of 1 represents 1 component), then splitting the workload to multiple processors can become tricky!
int main()
{
/* 1100
0010
0100
0011
*/
int A[4][4] = {1,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1}, B[4][4];
int numComponent=0, i,j;
int n = 4; // array size
for(i=n-1; i>=0; i--)
for( j=n-1;j>=0;j--)
{
if(A[i][j] == 1)
{
/* right */
if( ( j+1 < n) && (A[i][j+1] == 1))
B[i][j] = B[i][j+1];
/* down */
else if( (i+1 <n ) && (A[i+1][j] == 1))
B[i][j] = B[i+1][j];
/* left down diagonal */
else if( (j-1 >= 0 ) && (i+1 <n ) && (A[i+1][j-1] == 1))
B[i][j] = B[i+1][j-1];
/* right down diagonal */
else if( (j+1 < n ) && (i+1 <n ) && (A[i+1][j+1] == 1))
B[i][j] = B[i+1][j+1];
/* there is no adjacent 1's, so increase number of component count */
else
B[i][j] = ++numComponent;
}
}
printf("\n numberof components = %d\n", numComponent);
return 0;
}
1=white / 0=black
I create 5 masks of size 2x2 - 1 row, 2 cols, 2 diagonals
(I skipped one row bcz it will be considered in next iteration)
I loop through the entire matrix and at each cell visited, I check if there is a corresponding mask match.. if it is then it is a component.
Time complexity: O(nxnx2x2) = O(nxn)
public static int countComponents(int[][] matrix)
{
int count = 0;
int[][] mask1 = {{0,0},{1,1}};
int[][] mask2 = {{0,1},{0,1}};
int[][] mask3 = {{1,0},{1,0}};
int[][] mask4 = {{0,1},{1,0}};
int[][] mask5 = {{1,0},{0,1}};
for(int i=0; i<matrix.length-1; i++)
for(int j=0; j<matrix[0].length-1; j++)
{
if(isComponent(matrix, i,j,mask1)) count++;
if(isComponent(matrix, i,j,mask2)) count++;
if(isComponent(matrix, i,j,mask3)) count++;
if(isComponent(matrix, i,j,mask4)) count++;
if(isComponent(matrix, i,j,mask5)) count++;
}
return count;
}
public static boolean isComponent(int [][]matrix, int i, int j, int[][] mask)
{
for(int m=i, p=0; p<mask.length; m++, p++)
for(int n=j, q=0; q<mask[0].length; n++, q++)
if(mask[p][q]==0 && matrix[m][n]!=0) return false;
return true;
}
Use 4 pixel rectangle to label the components at the first pass, at the same time, generating a table for equivalent labels. At the second pass, merge the equivalent labels.
Matrix can be divided into small pieces and then every thread can label its own part. Keep the boarder of small matrix appears at adjacent submatrixes. And make the boarder label equivalent so we can merge them later
Let us think about multiple core approach for a while.
We have a matrix of whites and blacks.
If possible, divide the matrix into as many parts as number of cores.
Then, each core will find the number of connected components it has.
So, each core will return 1) number of connected components it identified 2) array of arrays where each internal array contains indices of a particular connected component.
During merge process of the solutions from two different cores, we need to find if there is any common indice in one of the subarrays. If yes, club the two arrays with a common indice (since they belong to same connected component)
the multi-core solution:
1. divide the map into 4 parts, for example.
2. use single cores to calculate the components in each sub-map, as well as each component's position at the edges.
3. the total number of components is the sum of components in each sub-map subtract the total number of joint components.
the multi-core solution:
1. divide the map into 4 parts, for example.
2. use single cores to calculate the components in each sub-map, as well as each component's position at the edges.
3. the total number of components is the sum of components in each sub-map subtract the total number of joint components.
Whenever you encounter a black you will check its 8 neighbors to see if they are also black. You will do the same thing for the black neighbors again and again until there is no neighbor remains.
- Rayden January 18, 2012Assuming you can destroy the original matrix just change the black neighbors to white as you encounter them.
You can assign the control for 8 neighbors to seperate cores to speed things up.