Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
import math
all_intersecting_circles = list()
for a_idx in range(len(circles)):
a = circles[a_idx]
intersecting_circles = set()
intersecting_circles.append(a)
for b_idx in range(a_idx + 1, len(circles)):
b = circles[b_idx]
height = abs(a.y - b.y)
width = abs(a.x - b.x)
distance = math.sqrt(math.pow(width, 2) + math.pow(height, 2))
if distance <= a.radius + b.radius:
# circles do intersect
intersecting_circles.add(b)
if len(intersecting_circles) > 0:
all_intersecting_circles.append(intersecting_circles)
print(all_intersecting_circles)
Runtime: O((N^2)/2)
However, N^2 is the dominant complexity class and therefore we would end with O(N^2) again.
We need to calculate the distance between each tuple of circles. I don't think we can do better in this case.
The O(n^2) solution checks for intersection among each pair.
To improve it, we have various options:
- If the radius is all the same for each circle, we can put the circles in a hash map that keys to y/r and x/r (this is essentially putting r-side length squares over the 2d space. Then for the remaining n-1 circles for each of the 8 adjacent sqaures of this circle check if one circle found in this squares intersect. There are at most 8*4 circles to compare per circle which makes it O(8*4*n) = O(n)
- If the radius is not the same for each square, a two dimensional segment tree could be used on the bounding box of the circle. If a potential intersection is detected, one has to check intersection of the k points which is if the distance of the centers is less than then the sum of the two radius. This has O(n*log(n)^2) for read and insert, therefore leading to O(n*log(n)^2) performance, where as it is assumed that the number of collisions in a bounding box is not significant. One has to carefully think if worst case isn’t O(n^2) due to collisions within the bounding box of circles that still don’t overlap (e.g. if k can be a factor * n, like n/2 n/4 n/f).
//Time: O(NlogN) Space: O(N).
class Circle{
double x;
double y;
double rad;
}
class Interval implements Comparable<Interval>{
double start;
double end;
int id;
public Interval(double s, double e, int idx){
start = s;
end = e;
id = idx;
}
public int compareTo(Interval i){
if(start == i.start){
return end - i.end;
}
return start - i.start;
}
}
public boolean hasIntersect(Circle[] c){
if(c == null || c.length == 0){
throw new IllegalArgumentException();
}
Interval[] xRange = new Interval[c.length];
Interval[] yRange = new Interval[c.length];
for(int i = 0; i < c.length; i++){
xRange[i] = new Interval(c[i].x - c[i].r,c[i].x + c[i].r,i);
yRange[i] = new Interval(c[i].y - c[i].r, c[i].y + c[i].r, i);
}
Arrays.sort(xRange);
Arrays.sort(yRange);
Set<String> overlaps = new HashSet<String>();
for(int i = 1; i < xRange.length; i++){
if(xRange[i].start <= xRange[i -1].end){
int minId = Math.min(xRange[i-1].id, xRange[i].id);
int maxId = Math.max(xRange[i - 1].id, xRange[i].id);
overlaps.add(minId +", " + maxId);
}
}
for(int i = 1; i < yRange.length; i++){
if(yRange[i].start <= yRange[i - 1].end){
int minId = Math.min(yRange[i -1]. id, yRange[i].id);
int maxId = Math.max(yRange[i - 1].id, yRange[i].id);
if(overlaps.contains(minId + ", " + maxId)){
return true;
}
}
}
return false;
}
* build a 2D range tree from the circle centers, requires O(n log n) time (see en.wikipedia.org/wiki/Range_tree )
* for each center (x_i, y_i), find the points within the 2D range (x_i - r_i, x_i + r_i) x (y_i - r_i, y_i + r_i), requires O(log^2 n + k) time (where k is the number of points returned which can actually be n^2 in the worst case) per point. Calculate the actual Euclidean distance between the points found in the range search and the center of circle i and check whether it is less than r_i + r_other .
if the average number of points k returned in a query does not grow with n, the total time complexity is O(n log^2 n)
(the Wikipedia article also mentions that queries can even be done in O(log n + k) time for 2D trees.
To do better than O(n^2), we either need to scan the data set multiple times in O(n) or use divide and conquer which will be O(nlog(n))
In this case, I would sort circle center by x coordinate and partition by median and use quick sort technique to find intersections in left and right. Also we need to find intersections around median as well, which in worst case may make algorithm O(n^2)
I believe that can be solved by a sweep line algorithm. However, I always find myself some homework like questions in the forum. This is one of them. I am really surprised if they ask you to write and test the code in such limited time. Maybe they only want to know if you know the method and explain it to them on a white board.
import math
class Circle(object):
def __init__(self, x, y, r):
super(Circle, self).__init__()
self.x = x
self.y = y
self.r = r
def get_distance(self, circle):
return math.sqrt(math.pow(self.x - circle.x, 2) + math.pow(self.y - circle.y, 2))
def is_intersect(self, circle):
return self.get_distance(circle) < self.r + circle.r
@staticmethod
def has_intersections(list_circles):
list_circles.sort(key=lambda a: a.x - a.r)
sweep_intersected = []
for circle in list_circles:
for in_sweep in sweep_intersected:
if circle.is_intersect(in_sweep):
return True
if in_sweep.x + in_sweep.r < circle.x - circle.r:
sweep_intersected.remove(in_sweep)
sweep_intersected.append(circle)
return False
c1 = Circle(5, 5, 5)
c2 = Circle(11, 11, 5)
c3 = Circle(5.5, 10.5, 0.1)
print Circle.has_intersections([c1, c2, c3])
Project circles to x axis and find overlap there first, then check if they really overlap in 2D
Use slide window to find overlap on x. each circle can be represent as [x - radius, x+radius]
Sort them by x-radius, scan by slide window. two anchors i, j to satisify
1. circles[j][0] < circles[i][1]
2. maximize j-i
It seems that (most of) the solutions above don't take into account the fact that for two circles to *intersect* the distance between centers needs to be larger than the absolute value of the difference between the radii, and addition to being smaller than their sum.
The idea to do a quick screen:
- ctk November 19, 20161) For two circles to intersect, x-range and y-range must have overlap.
2) but the reverse is not always true. So need to iterate over the screened result in (1) to check
So,
1) sorted over x-coordination, check each element's sliding window to focus on overlapping ones, and check if y overlaps as well, and then check the r1+r2>distance