Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: In-Person


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

For each possible center, compute the possible distances and sort them. Keep track of the count the value that is repeated most for that given center.

Pick the center with the maximum count.

O(n^2 log n).

- Anonymous on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why the logN factor? You can determine the mode of a set in linear time using a hashmap.

- eugene.yarovoi on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it requires n^2 right? how it is possible O(n)?

- Anonymous on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Eugene: Yes, you can use hashing and bring it down to expected O(n) for each center. Of course, worst case could go Omega(n^2). Sorting is worst case O(n logn) (say heap sort).


@Anonymous: Eugene is talking about the case of a specific center. For each center, it is expected O(n), so you both are right. It is expected O(n^2) to solve the full problem.

- Anonymous on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Going for determinism, I see.

- eugene.yarovoi on April 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

let us say a point x,y lies on circle with centre x0,y0, we can say that a=x-x0,b=y-y0 lies on circle with centre 0,0.
now a^2+b^2=r^2. hence for each point x,y calculate x^2+y^2, and hash it to a table with this index and maintain count.
Now the entry with maximum count is answer. Complexity O(n)

- andy on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) complexity for finding the optimal circle radius when given a center. Since there are O(n) possibilities for the center, the entire algorithm is O(n^2).

- eugene.yarovoi on April 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi buddy, can you please share your interview experience along with the questions. Thanks

- Vivek on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi
1. first of all I was ask to take one online programming test which had 3 questions. out of those I solved 2 and 3rd one partially.
2. Then I had a telephonic interview in which I was asked to write a program to calculate the max depth of a binary tree followed by a long discussion on the time and space complexity of the same.
3. Then I was called to Hyderabad for in-person interview. There in first I was asked to write a program, which I dont remember.
4. Followed by next round by two interviewer and I was asked this question. He asked about algorithm followed by code for the same.

Then I was told that they will update on Monday. On Monday I got the bad news about end of my interview process with Amazon.

They put a lot of emphasis on writing a clean piece of code. So practice a lot before appearing for interview.
However It was a great experience. Hope to make it to final round next time.

- vivekanand3435 on April 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi vivek
can you tell about the standard of code asked in the online programming test.Is it very complex or simple one.

- Vishal Deshraj on April 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Here is my answer to this question. We can solve the problem with O(N^2) time complexity.

basicalgos.blogspot.com/2012/04/42-find-minimum-radius-that-covers-all.html

- Andy on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No. This does not solve the problem. Don't want to log in to give a -1, so

_________
             / ______      |
            /_/          |      |
                          |      |
   ________       |      |
  |________|      |      |
                          |      |
       ---------------+      + ---------------
       |_______________________|

- Anonymous on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Haha. Should have guessed that would happen.

- Anonymous on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Misunderstood the problem. Have updated my post with the right solution. Comments are welcome.

- Andy on April 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can create a point class with x,y coordinate and hashmap<integer,arraylist<point>> this will give us the most common distance for each point then we can iterate to get the point with max number of points which satisfies the above criteria. We can maybe add a little optimization in running time if we can have a one more hashmap<point,hashmap<point,distance>>. So one we compute a distance between two pints we can add it to above map once for each of the points between which we just computed the distance. This way we can avoid calculating the distance again and again and we just look it up in the above map.

- Free Bird on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If for every point we create a map of the following structure :
<distance, count>

where distance is the distance of this point from another point in the plane. If two points A and B are equidistant from the same point P, then they must both lie on a circle with centre P and passing thru both these points A and B. The count gives us how many points are at a particular distance from point P.

Once we have computed this for every point, we then need to find the distance with maximum count. That point will be the centre and distance will be the radius.

In order to avoid repetitive updation for same set of points, we can update the hashtables of both points at the same time. For example, if we are calculating distance between A and B, we can update hashtables of A and B simultaneously.

I have not tested this yet but I think it should work. I hope I am not missing out anything.

- mandeep on April 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<code>//Find the centre and radius of a circle which passes through the maximum number of points. The centre must be one out of the given N points.
#include<stdio.h>
#include<math.h>
#define n 14

float dist(int *a,int *b)
{
float d;
d = sqrt(((*(b+1) - *(a+1)) * (*(b+1) - *(a+1))) + ((*(b) - *(a)) * (*(b) - *(a))));
return d;
}

float max_occurence(float a[],float *val)
{
int i,j;
float occ[n] = {0},max,v[n]={0};

for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
if(a[i]==a[j])
{
occ[i]++;
v[i] = a[i];
}
}
}
max = occ[0];
for(i=0;i<n;i++)
{
if(occ[i]>=max)
{
max = occ[i];
*val = a[i];
}
}
return max;
}

float maxi(float d[])
{
int i,max = d[0],index;
for(i=0;i<n;i++)
{
if(d[i]>max)
{
max=d[i];
index=i;
}
}
return index;
}

void findcircle(int *a)
{
int i,j,c1=0,c2=0,index;
float r = 0, d[n]={0},temp[n]={0},val,radius[n]={0},tmp;
for(i=0;i<(2*n);i=i+2)
{
c2=0;
for(j=0;j<(2*n);j=j+2)
{
r = dist(a+i,a+j);
printf("Dist between (%d,%d) and (%d,%d) is %f \n",*(a+i),*(a+i+1),*(a+j),*(a+j+1),r);
temp[c2] = r;
c2++;
}
d[c1] = max_occurence(temp,&val);//finds the distance of all points from all the other points and find maximum occurence of distances
radius[c1]=val;
c1++;
}
index = maxi(d);
printf("Center of circle is (%d,%d)\n",*(a+(2*index)),*(a+(2*index)+1));
printf("Radius of circle is %f\n",radius[index]);
printf("Points on circle are:\n");
for(i=0;i<(2*n);i=i+2)
{
if(i!=(2*index))
{
tmp = (*(a+(2*index)) - *(a+i))*(*(a+(2*index)) - *(a+i)) + (*(a+(2*index)+1) - *(a+i+1))*(*(a+(2*index)+1) - *(a+i+1));
if(fabs(tmp - (radius[index]*radius[index])) <= 0.001 )//for floating point comparison
printf("(%d,%d)\n",*(a+i),*(a+i+1));

}
}
}

int main()
{
/*int a[n][2] = {{2,3},
{3,2},
{2,2},
{5,5},
{1,2},
};*/
int a[n][2] = {{2,4},
{3,3},
{3,5},
{4,2},
{4,4},
{4,6},
{5,3},
{5,5},
{6,4},
{2,2},
{2,3},
{3,2},
{3,4},
{4,3}
};
findcircle(&a[0][0]);

return 0;
}
</code>

- pd on April 13, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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