Google Interview Question for SDE-2s
- 0of 0 votes
I was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:- Jaysun October 26, 2019 in United States
There's a list of (x,y) points and a method getCircle with the following signature:
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.
The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?
| Report Duplicate | Flag | PURGE
Google SDE-2 Algorithm
Open Chat in New Window