## Amazon Interview Question Software Engineer / Developers

• 0

Given the coordinates of N points in a plane. Assume the standard 2D quadrant system for representation of points.

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

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

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

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

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

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

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

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

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

Going for determinism, I see.

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)

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

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

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

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

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.

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

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

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.

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

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

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

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

Haha. Should have guessed that would happen.

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

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

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.

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.

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;
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
c1++;
}
index = maxi(d);
printf("Center of circle is (%d,%d)\n",*(a+(2*index)),*(a+(2*index)+1));
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));
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>

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.

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