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.