## Google Interview Question for SDE-2s

Country: United States

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

observation:
after 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.

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

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.

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

I am tempted to say it is not possible to avoid O(n^3) in general. Consider a case where you have N points but only 3 of them lie on a circle (i.e. getCircle returns non-null). Now you cannot find the circle unless you test all triplets.

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

Look into Welzl's algorithm it's a O(log n) implementation for finding the center of a circle using Randomization.

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

What would be the recursive algorithm for this?

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

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.

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

Won't this be O(N4). O(N3) for each combination and iterating over all the point once again to calculate the distance.

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

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.

Name:

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

### Books

is a comprehensive book on 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.