## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

Good!

Few points:

This is sufficient!

static int r[]={0,0,1,1,1};

static int c[]={-1,1,-1,0,1},k;

in total five adjacent points. This is because,

outer loop for countImage ensures for any point with x coordinate i , ( (0..i-1), j) have been already visited.j can have any value here

Secondly why are vectors r anc c static??

Third:

You are modifying the original input . You can use an auxiliary array for marking visited. And use stacks for DFS you can avoid recursion.

1. Yes, you have a good thought. Three positions are redundant to check. These are (-1,-1),(-1,0) and (0,-1).

2. static is chosen to avoid the memory allocation in each recursion. Yes, we can make them global. But, r[] & c[] are needed in this function only. So, static.

3. Yes, i am modifying the original input here. If we are not allowed to modify it, sure, take an auxiliary visited array. .

I think,this can be like number of connected components.

We can do dfs from a 1 do dfs upto we find a zero.Also maintain another matrix which records if the cell is visited or not.then we can choose next 1 which is not visited and do dfs from there.

Comments or Solution?

I am a bit confused. Can you explain with reference to the question given how the number of images comes as 5?

public class FindNumOfImagesInMatrix {

public static final int[][] matrix = {

{1,1,0,0,0},

{0,1,0,0,1},

{1,0,0,1,1},

{0,0,0,0,0},

{1,0,1,0,1},

};

public static final int size = matrix.length;

@Test

public void findNum() {

int[][] mark = new int[size][size];

int count = 0;

for (int i=0; i<size; ++i) {

for (int j=0; j<size; ++j) {

if (markImage(i, j, mark)) {

++count;

}

}

}

}

public boolean markImage(int i, int j, int[][] mark) {

if (i < 0 || i > size-1 || j < 0 || j > size-1 || mark[i][j] == 1)

return false;

if (matrix[i][j] == 1) {

mark[i][j] = 1;

markImage(i-1, j, mark);

markImage(i+1, j, mark);

markImage(i-1, j-1, mark);

markImage(i+1, j-1, mark);

markImage(i, j-1, mark);

markImage(i-1, j+1, mark);

markImage(i+1, j+1, mark);

markImage(i, j+1, mark);

return true;

}

return false;

}

}

This can be done non recursively

for(i=0 i<n; i++)

for(j=0; j<n ; j++)

if(a[i][j])

{

count ++; //one image found

point tmp = point(i,j);

while(!queue_empty(&s))

{

//enqueue all previously not visited neighbors of tmp (which are 1) in the queue

tmp = dequeu(s);

}

// This image finished now search other

}

can somebody plz xplain how dis matrix represents five images i can find only 4.....plz help

I believe there is an easier way to count the number of islands/areas of 1

Can Someone please review this!!!!!!!

```
public void countIsland(char [][] matrix)
{
int count=0;
for ( int i=0 ; i<n;i++)
{
for (int j=0;j<n;j++)
{
if(matrix[i][j]==1)
{
bool checkX = check_if_any_neihgbour_is_x(matrix,i,j);
bool check1 = check_if_any_neighbour_is_1(matrix,i,j);
if(!check1)
count++;
matrix[i][j]='X'
}
}
}
}
public Boolean checkNeighbour(int[][] matrix,)
```

Choose a slot with value 1, Perform DFS from here & set all slots to 0 while visiting to avoid them in the further visits.

Complete working code: ideone.com/RhZcU

- Aashish July 25, 2012