## Google Interview Question

SDE-2s**Country:**United States

Also, we can find out what point groups can not mutually create a circle. How? Simple, any 3 points on a plane can be made into a circle, unless all 3 of them form a line.

It is O(n^2) to check all points to find out all lines, at most.

So, we would have point groups which can not be used as circle.

That automatically should reduce a lot of points comparison.

They, might be possibly more optimisations, but am thinking still. Hence a comment, not an answer.

With a few draws, I come to an observation - but unable to prove it yet, that is, among the list, find 4 points with the highest x,y and lowest x,y, it seems the circle must include at least 2 points among those 4. (Again, just observation, not a proved fact). If so, we can always pick the 2 among the list and find another point using the trivial method you mentioned in O(n) time.

I think getCircle already returns center point and radius right. Say it returns center point as (p,q), and radius = r

After finding the triplet, for each other point in the list

square-root of ((x-p)^2 + (y-q)^2) == radius will give the points in that circle perimeter.

Buffer all these points in a list.

Repeat above for other triplet combinations, but skip the combination where all three points are already part of a circle identified.

I can think an optimization where we create a fully connected graph, where the edge weight represent distance between 2 points sqrt((a2-a1)2 + (b2-b1)2). Store these edges in a sorted order list. This would take O(n2). Now when we choose triplets and get a circle, we start iterating over nearest neighbor from each of 3 points, till a stage where the distance is less than diameter. This way when we ignore all the points which will definitely be out of circle.

Observation:

After a few sketches, I have an yet-to-prove observation that the circle if exits must include 2 points among the following 4 points: lowest_x, higest_x, lowest_y and highest_y. If that's the case, clearly we can have a O(n) solution to this problem. Or at least, I have a feeling that solving this problem may rely on some geometry observation from which the problem can be greatly simplified...

I think that will give you the largest circle. The circle with the most points on its perimeter chosen from among the points in the set might have a smaller radius. I could define a circle with radius 2 centered at (0,0), and pick 100 points on its perimeter, then add three more points on a circle of radius 10 that is also centered at (0,0).

Idea is if all three points have to lie on circle's circumference than distance of all 3 points from centre should be same. Now we have to find such centre.

find min x and max x

find min y and max y

for (i = min_x; i <= max_x; i++)

{

for (j = min_y; j <= max_y; j++)

{

a = (x1-i)^2 + (y1-j)^2;

b = (x2-i)^2 + (y2-j)^2;

c = (x3-i)^2 + (y3-j)^2;

if (a == b && a == c)

// this is the centre

return;

}

}

observation:

- plarion October 27, 2019after you calculate a circle - find all points on the circle (o(n))

since a triplet form only one circle - so all combination of point on that circle form the same circle.

so there is no need to re-calculate a circle with them.

storing them in a hash and skipping them in the future will reduce run-time.

you will still go over all triplets (o(n^3)) but you will call the method getCircle(...) much fewer times.