Facebook Interview Question
Java DevelopersCountry: United States
I assume they are looking for an approximation, since the iterative method for determining a minimal enclosing circle is really specialized knowledge to pull out during an interview.
Instead, assume all points are equidistance from each other and form a regular polygon. The radius of that polygon would be the radius of the circle enclosing them, which is easily found using the law of cosines. Still, this is just an upper bound approximation, as the points are probably not going to be equidistance from each other.
class Point {
double x;
double y;
Point (double x, double y) {
this.x = x;
this.y = y;
}
}
double getRadius(List<Point> points) {
Point max = new Point(0.0, 0.0);
Point min = new Point(0.0, 0.0);
for (Point p : points) {
if (max.x < p.x) {
max.x = p.x;
}
if (max.y < p.y) {
max.y = p.y;
}
if (min.x = 0 || min.x > p.x) {
min.x = p.x;
if (min.y = 0 || min.y > p.y) {
min.y = p.y;
}
}
Point center = new Point((max.x - min.x)/2, (max.y - min.y)/2);
if (max.x > max.y) {
return max.x - center.x;
} else {
return max.y - center.y;
}
}
The smallest circle would have two points from the set of points as diameter. Thus, the problem is choosing two such points for which all points fall inside the circle. This is O(n3) by definition.
- Champaklal October 24, 2018