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

- Aashish July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- words&lyrics July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aashish July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very Nice! :)

- nerd August 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

very good.

- Psycho September 07, 2012 | Flag
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.
Comments or Solution?

- grave July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correctomundo

- TheWolfe August 13, 2012 | Flag
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?

- Anonymous July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- grave July 31, 2012 | Flag
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

- niraj.nijju July 25, 2012 | Flag Reply
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;
}

}

- gfan July 26, 2012 | Flag Reply
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
}

- words&lyrics July 26, 2012 | Flag Reply
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

- sameer July 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- viji July 28, 2012 | Flag
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
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,)

- Anonymous February 21, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More