Amazon Interview Question
Software Engineer / DevelopersCountry: 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