xyz Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
The idea here is to parse the matrix diagnolly
int b[4][4] = { { 1,1,1,0 },{ 0,0,1,0 },{ 0,0,1,0 },{ 0,0,0,0 } };
bool check1(int row,int col)
{
if (col == 0 && row != 0)
{
if (b[row - 1][col] == 1)
return true;
}
else if (row == 0 && col != 0)
{
if (b[row][col-1] == 1 || b[row + 1][col - 1] == 1)
return true;
}
else if (row == 0 && col == 0)
return false;
else if (b[row + 1][col - 1] == 1 || b[row][col - 1] == 1 || b[row - 1][col] == 1)
return true;
return false;
}
int main()
{
int a[] = { 9,3,8,11,12,4,7,0,7,8 };
int islands = 0;
for (int i = 0; i < 7; i++)
{
int j,k,count;
if (i < 4) {
j = 0;
k = i -j;
count = k;
while (j<=count)
{
if (b[j][k] == 1) {
if (!check1(j, k))
{
cout << j << " " << k << endl;
islands++;
}
}
j++;
k = i - j;
}
}
else if(i>=4)
{
k = 3;
j = i - k;
count = j;
while (k>=count)
{
if (b[j][k] == 1) {
if (!check1(j, k))
{
cout << j << " " << k << endl;
islands++;
}
}
j++;
k= i - j;
}
}
}
cout << islands;
return 0;
}
public static int getTotalIslands(int[][] plane) {
if (plane == null)
return 0;
int result = 0;
for (int i = 0; i < plane.length; i++) {
for (int j = 0; j < plane[0].length; j++) {
if (plane[i][j] == 1) {
result++;
markTheIsland(plane, i, j);
}
}
}
return result;
}
public static void markTheIsland(int[][] plane, int i, int j) {
if (plane[i][j] == 1) {
plane[i][j] = -1;
if ((j + 1) < plane[0].length)
markTheIsland(plane, i, j + 1);
if ((j - 1) >= 0)
markTheIsland(plane, i, j - 1);
if ((i + 1) < plane.length)
markTheIsland(plane, i + 1, j);
if ((i - 1) >= 0)
markTheIsland(plane, i - 1, j);
} else
return;
}
- tewelde May 24, 2016