Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Thank you Nani. It is simple one. I think instread of creating a new boolean 2D Array, we might play around the existing array with different values like -1 for visited 0s and -2 for 1s and count the 1 group. What you think?.
The Algo provided by Nani will return 1 in your case, Appu
And I think this is also expected from the question's algo
<pre lang="" line="1" title="CodeMonkey35139" class="run-this">class Cluster {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = { { 1, 0, 1 }, { 1, 0, 1 }, { 0, 1, 1 } };
int cluster = dfs(matrix);
System.out.print("Cluster:" + cluster);
}
private static int dfs(int[][] matrix) {
// TODO Auto-generated method stub
int cluster = 0;
printMatrix(matrix);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1) {
dfsVisit(matrix, i, j);
cluster++;
}
}
}
printMatrix(matrix);
return cluster;
}
private static void dfsVisit(int[][] matrix, int i, int j) {
// TODO Auto-generated method stub
if (i < 0 || i >= matrix.length)
return;
if (j < 0 || j >= matrix[0].length)
return;
if (matrix[i][j] != 1)
return;
matrix[i][j] = -1;
dfsVisit(matrix, i + 1, j);
dfsVisit(matrix, i, j + 1);
dfsVisit(matrix, i - 1, j);
dfsVisit(matrix, i, j - 1);
}
private static void printMatrix(int[][] matrix) {
// TODO Auto-generated method stub
System.out.println();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.printf("%4d", matrix[i][j]);
}
System.out.println();
}
}
}
</pre><pre title="CodeMonkey35139" input="yes">
</pre>
<pre lang="" line="1" title="CodeMonkey83180" class="run-this">class Cluster {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] matrix = { { 1, 0, 1 }, { 1, 0, 1 }, { 0, 1, 1 } };
int cluster = dfs(matrix);
System.out.print("Cluster:" + cluster);
}
private static int dfs(int[][] matrix) {
// TODO Auto-generated method stub
int cluster = 0;
printMatrix(matrix);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 1) {
dfsVisit(matrix, i, j);
cluster++;
}
}
}
printMatrix(matrix);
return cluster;
}
private static void dfsVisit(int[][] matrix, int i, int j) {
// TODO Auto-generated method stub
if (i < 0 || i >= matrix.length)
return;
if (j < 0 || j >= matrix[0].length)
return;
if (matrix[i][j] != 1)
return;
matrix[i][j] = -1;
dfsVisit(matrix, i + 1, j);
dfsVisit(matrix, i, j + 1);
dfsVisit(matrix, i - 1, j);
dfsVisit(matrix, i, j - 1);
}
private static void printMatrix(int[][] matrix) {
// TODO Auto-generated method stub
System.out.println();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.printf("%4d", matrix[i][j]);
}
System.out.println();
}
}
}
</pre><pre title="CodeMonkey83180" input="yes">
</pre>
int FindAdjacentOns(int** matrix, int rows, int cols)
{
int groupCount = 0;
for (int i=0; i< rows ; i++)
{
for(int j=0; j< cols ; j++)
{
if(matrix[i][j] == 1)
{
groupCount ++;
CheckAdjacent( matrix, i, j)
}
}
}
return groupCount;
}
void CheckAdjacent(int** matrix, int i, int j, int rows, int cols)
{
if (matrix != null && matrix[i][j] == 0)
{
return;
}
matrix[i][j] = 0;
if (i > 0)
{
CheckAdjacent(matrix, i - 1, j, rows, cols);
}
if (j > 0)
{
CheckAdjacent(matrix, i - 1, j, rows, cols);
}
if (i < rows - 1)
{
CheckAdjacent(matrix, i + 1, j, rows, cols);
}
if (j < cols - 1)
{
CheckAdjacent(matrix, i, j + 1, rows, cols);
}
}
Running C++ code:
#include<iostream>
using namespace std;
void numGroups(int a[][5],int i,int j,int n,int curr )
{
if(i < 0 || j < 0 )
return;
if((i == n) || (j == n))
return;
if(a[i][j]==1)
{
a[i][j] = curr;
numGroups(a,i-1,j,n,curr);
numGroups(a,i+1,j,n,curr);
numGroups(a,i,j-1,n,curr);
numGroups(a,i,j+1,n,curr);
numGroups(a,i+1,j+1,n,curr);
numGroups(a,i-1,j+1,n,curr);
numGroups(a,i+1,j-1,n,curr);
numGroups(a,i-1,j-1,n,curr);
}
}
bool discoverAll(int arr[][5],int n,int &next_i,int &next_j)
{
for(int i =0;i<n;i++)
for(int j=0;j<n;j++)
if(arr[i][j]==1)
{
next_i = i;
next_j = j;
return false;
}
return true;
}
int numGroupsTrigger(int arr[][5],int n)
{
int groupCount = 2;
int start_i=0,start_j=0;
while(!discoverAll(arr,n,start_i,start_j))
{
numGroups(arr,start_i,start_j,n,groupCount);
groupCount++;
}
return groupCount-2;
}
void showArr(int arr[][5],int n)
{
for(int i =0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}
}
int main()
{
int array2D[5][5] = { {1,0,1,0,1},
{0,1,1,0,0},
{1,1,1,1,1},
{0,0,1,1,0},
{1,0,1,0,1}
};
int n = 5;
cout<<"# 1s: "<<numGroupsTrigger(array2D,5);
cout<<endl;
showArr(array2D,n);
cout<<endl;
char c;
cin>>c;
return 0;
}
Assuming that I am writing code for a 4 by 4 matrix.
static void GroupCount(ref int[,] Arr)
{
int groupCount = 1;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (Arr[i, j] == 1)
{
groupCount += 1;
Arr[i, j] = groupCount;
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
}
}
Console.WriteLine("GroupCount is {0}", groupCount-1);
Console.ReadLine();
}
private static void CombineGroup(ref int[,] Arr, int i, int j)
{
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
Assuming that I am working on a 4by4 matrix
static void GroupCount(ref int[,] Arr)
{
int groupCount = 1;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (Arr[i, j] == 1)
{
groupCount += 1;
Arr[i, j] = groupCount;
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
}
}
Console.WriteLine("GroupCount is {0}", groupCount-1);
Console.ReadLine();
}
private static void CombineGroup(ref int[,] Arr, int i, int j)
{
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
this solution assumes the input matrix order is 4by4.
static void GroupCount(ref int[,] Arr)
{
int groupCount = 1;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
if (Arr[i, j] == 1)
{
groupCount += 1;
Arr[i, j] = groupCount;
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
}
}
Console.WriteLine("GroupCount is {0}", groupCount-1);
Console.ReadLine();
}
private static void CombineGroup(ref int[,] Arr, int i, int j)
{
if (i + 1 < 4)
{
if (Arr[i + 1, j] == 1)
{
Arr[i + 1, j] = Arr[i, j];
CombineGroup(ref Arr, i + 1, j);
}
}
if (j + 1 < 4)
{
if (Arr[i, j + 1] == 1)
{
Arr[i, j + 1] = Arr[i, j];
CombineGroup(ref Arr, i, j + 1);
}
}
}
input array (a) and flag array are the members of class. Below is the code for counting both zero groups and one groups.
- Nani November 03, 2011