## Microsoft Interview Question for Interns

Country: United States

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

``````/**
* Given an `N`x`N` Boolean matrix, find how many true
* regions there are in the matrix.
*/

// Define a `true region` as any contiguous set of
// true elements such that the true elements are
// touching either horizontally, vertically, or
// diagonally.

// For each `i`,`j` element in the matrix, if it is
// `true` mark it as "unvisited" and put it in the
// search set.

// Set `r` to be 0, the number of unique regions.

// While there are elements in the search set,
// take an element from the search set, if it
// is "visited", discard it, if it is "unvisited"
// mark it as "visited", and put it in the
// working set and increment `r`.

// While there are elements in the working set,
// take the next element from the working set,
// if it has any `true` neighbors among it's
// 8 possible neighbors, mark those neighbors
// as "visited" and add them to the working
// set.

// Return `r` the number of contiguous true regions of
// the `N`x`N` matrix.``````

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

//regions =0
// visited_set = new hashset()
//for each t[i,j]
//{
// if t[i,j] in visited_set or is false continue;
//
// regions ++
// Stack region_cells = new Stack();
// current = t[i,j]
// -- let's visit all true cells in this region and mark then so we will skip them later
// while (current != null)
// {
// for each neighbor of current
// {
// if (neighbor is true and not in visited_set)
// {
// stack.push(neighbor)
// }
// }
// current = stack.pop()
// }
//}

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

can be done using union-find data structure with one pass on the matrix

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

can be done using union-find data structure with one pass on the matrix.
time: O(log*(NxN))

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

``````public static int TrueRegionCount(Boolean[][] regions)
{
int newRegions = 0;
for (int i = 0; i < regions.Length; i++)
{
for (int j = 0; j < regions[i].Length; j++)
{
if (isNewRegion(regions, i, j))
{
newRegions++;
}
}
}
return newRegions;
}

private static Boolean isNewRegion(Boolean[][] regions, int i, int j)
{
return (regions[i][j] &&
!(((i > 0) &&
((j > 0) && (regions[i - 1][j - 1]) ||
regions[i - 1][j] ||
((j < regions.Length - 1) && regions[i - 1][j + 1]))
) ||
((j > 1) && regions[i][j - 1])
//Following are not visited yet
//||((j < regions.Length - 1) && regions[i][j+1]) ||
//((i < regions.Length -1) &&
//((j > 1) && regions[i+1][j-1] ||
//regions[i+1][j] ||
//regions[i+1][j+1] )
));
}``````

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

``````static void MarkedasTrue(int[,] myMatrix)
{
int[,] ValueChanged = new int[3,3];

for (int i = 0; i < myMatrix.GetLength(0); i++)
{
for (int j = 0; j < myMatrix.GetLength(1); j++)
{
if (myMatrix[i,j]==1)
{
for (int k = 0; k < myMatrix.GetLength(1); k++)
{
ValueChanged[i, k] = 1;
}
for (int l = 0; l < myMatrix.GetLength(0); l++)
{
ValueChanged[l, j] = 1;
}
}
}
}

myMatrix = ValueChanged;

PrintMatrix(myMatrix);
}``````

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

int GetTrueRegions(bool[,] m)
{
boo[,] visited = new bool[m.GetLength(0),m.GetLength(1)];
int counts = 0;
for(int i=0;i<m.GetLength(0);i++)
{
for(int j=0;j<m.GetLength(1);j++)
{
if(m[i,j] && !v[i,j])
{
counts = 0;
VisitConnected(m, visited, i, j);
}
}

}

}

void VisitConnected(bool[,] m, bool[,] visited, int i, int j)
{
if(i < m.GetLength(0) && j < m.GetLength(1) && m[i,j])
{
visited[i,j]=true;
VisitConnected(m, visited, i+1, j);
VisitConnected(m, visited, i, j+1);
VisitConnected(m, visited, i+1, j+1);
}
}

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

``````public static int GetTrueRegions(bool[,] m)
{
bool[,] visited = new bool[m.GetLength(0), m.GetLength(1)];
int counts = 0;
for (int i = 0; i < m.GetLength(0); i++)
{
for (int j = 0; j < m.GetLength(1); j++)
{
if (m[i, j] && !visited[i, j])
{
counts++;
VisitConnected(m, visited, i, j);
}
}

}
return counts;
}

static void VisitConnected(bool[,] m, bool[,] visited, int i, int j)
{
if (i < m.GetLength(0) && j < m.GetLength(1) && m[i, j])
{
visited[i, j] = true;
VisitConnected(m, visited, i + 1, j);
VisitConnected(m, visited, i, j + 1);
VisitConnected(m, visited, i + 1, j + 1);
}
}``````

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

let result = 0;
For each element:
if element==false: continue;
else element == true:
if any true elements are 'touching' this current element, set current elem to false
else result++

analysis: O(n) as there are in the worst case 8 neighbors to check per item if it is true

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.

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