Microsoft Interview Question for Software Engineer in Tests


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

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

- Rayden January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think it should be 4 neighbors as only 4 can be made to connect...

- na January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous January 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous January 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this, traversal & check 8 neig. & strike out black, logic is good. One optimization one can do here is, Dont scan first and last rows and first and last column. Meaning, start index as below.
for ( i=1; i<arr.length -1, i++)
{
for(j = 1; j<arr[i].length-1;j++)
{}
}

- Jayesh V May 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Can you please elaborate the question with some examples?

- loveCoding January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Anonymous January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the example above, we have one component. It's clear from the question >>"adjacent cells in the matrix are black they make up a connected component"

- D October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- siva.sai.2020 January 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@siva sai .. can u temme whrr u making visited equals true ??

- router February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- RKD February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain with an example..

- Anonymous June 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure how this will work? Can you summarize your algo first

- pc June 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- lixing January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Learner January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- qsgh February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- qsgh February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

actually, the map can be divided into small parts, say (1*1) size parts

- Anonymous February 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Which team was this question for?

- K April 04, 2014 | 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