## Microsoft Microsoft Interview Question for Software Engineer in Tests

Team: Office
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

solution: flood fill

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

agree with you. Graphics question.

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

i agree with the flood fill algorithm. here is my implementation for the algorithm please do comment if you find anything problematic

public static void countRegion(boolean[][] mat){
int count = 0;
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[i].length; j++) {
if (mat[i][j]) {
count++;
floodFill(mat, i, j);
}
}
}
System.out.println("Number of region: " + count);
}

private static void floodFill(boolean[][] mat, int i, int j) {
if (i >= 0 && i < mat.length && j >= 0 && j < mat[0].length && mat[i][j]) {
mat[i][j] = false;
floodFill(mat, i+1, j);
floodFill(mat, i, j+1);
floodFill(mat, i-1, j);
floodFill(mat, i, j-1);
}
}

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

Hint : Use BFS here. Here is algo

``````Lets say A is boolean matrix. consider each A[i][j] as node and the bool value as there value and it is connected with all its 2 to 4 nearer node.
Now run BSE on it. Here BFS is just used for visiting nodes with value true. in BFS we provide a source node whose value is true,
Here is sample code

for i=1 to n
for j=1 to m
if A[i][j] is not visited and is true
count++;
run BFS with source node A[i][j]

Now BFS only visit to new nodes having true value.``````

complexity O(m*n), same algo can also be used to calculate largest size pound of true values, or other related questions.

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

I like your solution, can you show an implementation? count will have the number of true nodes but how to dind contiguous true nodes?

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

Hey @ruth542, look at my code.
Kevin

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

``````bool  isTraversed[][] = {False};

int extendRegion(bool matrix[][], int x, int y)
{
if(X >N or Y> N ) return ;
if (Matrix[x][y] == True & isTraversed[x][y] = False)
{
isTraversed[x][y] = True;
extendRegion(x+1, y) ; (x-1, y) ; (x, y-1) (x ,  y+1)
}
}

int findRegion(bool matrix[][], int N)
{
count = 0
while( canfind  True and  not traversed)
{
find a True,  not traversed;
count ++;
extendRegion(x, y );
}
return count
}``````

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

what's the time complexity?

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

``````void extendRegion(bool *T, bool * is_traversed,int i,int j,int m, int n){
if ((i>=m) || (i<0)) return;
if ((j>=n) || (j<0)) return;
if (T[i*n+j] && !is_traversed[i*n+j]){
is_traversed[i*n+j]=true;
extendRegion(T, is_traversed,i+1,j,m,n);
extendRegion(T, is_traversed,i-1,j,m,n);
extendRegion(T, is_traversed,i,j+1,m,n);
extendRegion(T, is_traversed,i,j-1,m,n);
}
}

int findRegion(bool *T, int m, int n){
int count=0;
bool is_over=false;
bool is_traversed[m][n];
for (int i=0; i<m; i++){
for (int j=0; j<n; j++){
is_traversed[i][j]=false;
}
}

while (!is_over){
is_over=true;
for (int i=0; i<m; i++){
for (int j=0; j<n; j++){
if (T[i*n+j] && !is_traversed[i][j]){
is_over=false;
extendRegion(T, (bool *) is_traversed, i,j,m,n);
count++;
}
}
}
}
return count;
}``````

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

A dynamic programming approach..

public static int count(boolean[][] T) {
if (T == null || T[0] == null)
return 0;
int m = T.length;
int n = T[0].length;
int[][] C = new int[m][n];

// set up initial conditions
C[0][0] = T[0][0] ? 1 : 0;
for (int i = 1; i < m; i++) {
C[i][0] = C[i-1][0];
if (T[i][0] && !T[i-1][0])
C[i][0] += 1;
}
for (int j = 1; j < n; j++) {
C[0][j] = C[0][j-1];
if (T[0][j] && !T[0][j-1])
C[0][j] += 1;
}

// iterations
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int up = C[i-1][j];
int left = C[i][j-1];
C[i][j] = up > left ? up : left;
if (!T[i-1][j] && !T[i][j-1])
C[i][j] += 1;
}
}
return C[m-1][n-1];
}

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

This approach isn't work necesssarily true for every case. for the following case it returns 2.(1->true and 0->false)
1 0 0
1 0 1
1 1 1

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

``````import java.util.Stack;

public class BoolMatrix {
int M;
int N;
Square matrix[][];

class Square{
boolean bool;
int x;
int y;
boolean isVisited;
public Square(boolean bool, int x, int y) {
super();
this.bool = bool;
this.x = x;
this.y = y;
this.isVisited = false;
}
@Override
public String toString(){
if(bool){
return "T";
}else{
return "F";
}
}
}

public BoolMatrix(int m, int n) {
super();
M = m;
N = n;
matrix = new Square[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (Math.random() < 0.5) {
matrix[i][j] = new Square(true,i,j);
} else {
matrix[i][j] = new Square(false,i,j);
}
}
}
}

public void print() {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}

public int countRegion() {
int count = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if(!matrix[i][j].isVisited){
if(matrix[i][j].bool){
count++;
Stack<Square> stack = new Stack<Square>();
stack.push(matrix[i][j]);
while(!stack.isEmpty()){
Square s = stack.pop();
Square[] neighbors = getNeighbors(s);
for(Square squ:neighbors){
if(squ != null && !squ.isVisited){
stack.push(squ);
squ.isVisited = true;
}
}
}
}else{
matrix[i][j].isVisited = true;
}
}
}
}
System.out.println(count);
return count;
}

private Square[] getNeighbors(Square s) {
Square[] neighbors = new Square[4];
for (int k = 0; k < 4; k++) {
neighbors[k] = null;
}
if (s.x - 1 >= 0 && matrix[s.x - 1][s.y].bool) {
//top
neighbors[0] = matrix[s.x - 1][s.y];
}
if (s.x + 1 < M && matrix[s.x + 1][s.y].bool) {
//bottom
neighbors[1] = matrix[s.x +1][s.y];
}
if (s.y - 1 >= 0 && matrix[s.x][s.y - 1].bool) {
//left
neighbors[2] = matrix[s.x][s.y - 1];
}
if (s.y + 1 < N && matrix[s.x][s.y + 1].bool) {
//left
neighbors[3] = matrix[s.x][s.y + 1];
}
return neighbors;
}

public static void main(String[] args) {
BoolMatrix bm = new BoolMatrix(4, 5);
bm.print();
bm.countRegion();
}

}``````

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

Could you plz explain more ?

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

You have to count the number of contiguous true values in the array. A region is formed by true values that are next to each other either horizontally or vertically but not on the diagonal.

Some other examples. Tell me if is still not clear. On the whiteboard I could drew the regions to be sure.

``````T T T T T        <= 3 regions, the first one has horizontal and
F F F T F             vertical values
T T F F F
F F F F T

T F T F      <= 2 regions
T F T F

T F T F        <= 2 regions - look at the diagonal
T F T T
F T T T``````

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

can you explain the Question

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

public static int nRegion(char[][] A){
int x1=A.length, x2=A[0].length;
int nr=0,x,y,flag;
for(int i=0;i<x1;i++){
for(int j=0;j<x2;j++){
flag=0;
if(A[i][j]=='T'||A[i][j]=='B'){
nr++;
if(A[i][j]=='B'){ flag=1; }
x=i; y=j+1;
while(y<x2 && (A[x][y]=='T'||A[x][y]=='B')){
if(A[x][y]=='B'){ flag=1; }
A[x][y]='B';
y++;
}
x=i+1; y=j;
while(x<x1 && (A[x][y]=='T'||A[x][y]=='B')){
if(A[x][y]=='B'){ flag=1; }
A[x][y]='B';
x++;
}
}
if(flag==1){ nr--; }
}
}
return nr;
}

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

``````public static int nRegion(char[][] A){
int x1=A.length, x2=A[0].length;
int nr=0,x,y,flag;
for(int i=0;i<x1;i++){
for(int j=0;j<x2;j++){
flag=0;
if(A[i][j]=='T'||A[i][j]=='B'){
nr++;
if(A[i][j]=='B'){ flag=1; }
x=i; y=j+1;
while(y<x2 && (A[x][y]=='T'||A[x][y]=='B')){
if(A[x][y]=='B'){ flag=1; }
A[x][y]='B';
y++;
}
x=i+1; y=j;
while(x<x1 && (A[x][y]=='T'||A[x][y]=='B')){
if(A[x][y]=='B'){ flag=1; }
A[x][y]='B';
x++;
}
}
if(flag==1){ nr--; }
}
}
return nr;
}``````

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

excellent resource for this

``stackoverflow.com/questions/8124626/finding-connected-components-of-adjacency-matrix-graph``

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

``````int A[MAX_N][MAX_N];
int W, H;
int di[] = {1, 0};
int dj[] = {0, 1};

int countRegions() {
int cnt = 0;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
if (A[i][j] == 1) ++cnt;
for (int k = 0; k < 2; ++k) {
int ii = i + di[k], jj = j + dj[k];
if (ii < H && jj < W && A[ii][jj] == 1)
A[ii][jj] = 2;
}
}}
return cnt;
}``````

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

careercup question?id=12451676

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.