Microsoft Microsoft Interview Question Software Engineer in Tests
Team: Office
Country: United States
Interview Type: In-Person
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);
}
}
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.
I like your solution, can you show an implementation? count will have the number of true nodes but how to dind contiguous true nodes?
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
}
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;
}
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];
}
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();
}
}
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
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;
}
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;
}
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;
}
task: connected components
- evandrix January 25, 2013solution: flood fill