## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

``````int isSafe(int (*M)[COL],int r,int c)
{
return r>=0 && r<ROW && c>=0 && c<COL && M[r][c];
}

void DFS(int (*M)[COL],int i,int j)
{
static int r[]={-1,-1,-1,0,0,1,1,1};
static int c[]={-1,0,1,-1,1,-1,0,1},k;

M[i][j]=0;
for(k=0;k<8;++k)
if(isSafe(M,i+r[k],j+c[k]))
DFS(M,i+r[k],j+c[k]);
}

int countImage(int (*M)[COL])
{
int count=0,i,j;

for(i=0;i<ROW;i++)
for(j=0;j<COL;j++)
if(M[i][j])
{
DFS(M,i,j);
count++;
}
return count;
}``````

Complete working code: ideone.com/RhZcU

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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. .

Comment hidden because of low score. Click to expand.
0

Very Nice! :)

Comment hidden because of low score. Click to expand.
0

very good.

Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

Comment hidden because of low score. Click to expand.
0

correctomundo

Comment hidden because of low score. Click to expand.
1
of 3 vote

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

Comment hidden because of low score. Click to expand.
0

image 1 - a[0,0],a[0,1],a[1,1],a[2,1]
image 2 - a[1,4],a[2,4],a[2,3]
image3- a[4,0]
4- a[4,2]
5- a[4,4]

Comment hidden because of low score. Click to expand.
0
of 0 vote

Working Code @

codes-to-problem.blogspot.in/2012/07/given-2d-matrix-which-has-only-1s-and.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

``````11000
01001
10011
00000
10101
here the five images are
1.(0,0),(0,1),(1,1),(2,0)
2.(1,4),(2,3),(2,4)
3.(4,0)
4.(4,2)
5.(4,4)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

``````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,)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.