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

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:

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