CareerCup

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.

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.

Feels like a gradient-descent problem:

minimize (max((x1-x)^2 + (y1 -y)^2, (x2-x)^2 + (y2 -y)^2, ..., (xN-x)^2 + (yN -y)^2)

Not sure this is a good interview question.

sqrt ( (max X - min X)^2 + (max Y - min Y)^2 ) / 2

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;
	}
}

Get left uppermost point and right lowest point. This will be diameter of your circle