Google Interview Question
SDE1sCountry: United States
You need to project them on axis X and form massiv on begins end ends of their sides. Then you do the same on Y axis. After that we consiver all rectangles that fits int some interval of another interval. And check wther those rects are intersect.
Did I understand you right?
By projecting all edges of rectangle to X & Y-axis, you are getting (X1, X2) and (Y1, Y2) of rect_1.
Similarly for all rectangles.
<X1, X2>, <X3, X4> ... <X2n, X2n+1>
<Y1, Y2>, <Y3, Y4> ... <Y2n, Y2n+1>
Now, sort all (X1, X2) and (Y1, Y2) based on 2nd element of pair.
if there is overlap of any two interval in <X1, X2> <Xk, Xk+1>, then check corresponding <Y1, Y2> <Yk, Yk+1>. if that too overlap then this rectangle do overlap.
M i rite?
If not, then please explain your algo a little bit more.
Also, does it also consider the case mentioned by "srikantaggarwal".
What if rectangles are not parallel to axis?
Instead of finding which intersect, find the conditions where they dont intersect. There are total 4 conditions which tell if two rectangles intersect or not. For all the rectangles that pass those 4 conditions, means they intersect.
Yep,but your solution needs O(n^2) where n is a number of rectangler. My solution, which uses sorting do detect intervals intersection needs O(NlogN).
I have a solution O(n^2) though for a larger number of rectangles it may not work.
simply add a boundary check whether a particular point falls in that boundary.
boolean boundary(Rec r,point p)
{
if(p.x>=r.p1.x &&p.x<=r.p2.x&&p.y<=r.p1.y&&p.y>=r.p3.y)return true;
return false;
}
now for each rectangle save them in a list while saving just check whether any of them falls within the boundary of any other in the already existing list.
the boundary check is an O(1) operation and for each element t we are checking (t-1) elements. O(n^2) operations.
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
A working O(2Nlog2N + Nm) solution, where N is the number of rectangles and m is the average number of rectangles whose x projection intersect. The solution uses two sorted sets: one of all x endpoints and another of all y endpoints. An endpoint is rectangle start and a rectangle end on a particular axis.
public class IntersectingRectangles {
static class Endpoint implements Comparable<Endpoint> {
Rect rect;
boolean isStart;
double val;
Endpoint(Rect r, boolean start, double v){
rect = r;
isStart = start;
val = v;
}
public int compareTo(Endpoint other){
int ret;
double diff= this.val - other.val;
if(diff == 0) ret = 0;
else ret = (diff>0)?1:-1;
if(ret == 0){
ret = this.isStart?1:-1;
if(this.rect != other.rect){
ret = -ret;
}
}
return ret;
}
}
static class Rect {
Rect (double minX, double minY, double maxX, double maxY){
xStart = new Endpoint(this, true, minX);
xEnd = new Endpoint(this, false, maxX);
yStart = new Endpoint(this, true, minY);
yEnd = new Endpoint(this, false, maxY);
}
Endpoint xStart;
Endpoint xEnd;
Endpoint yStart;
Endpoint yEnd;
}
public static int getNumIntersecting(Rect [] rects){
TreeSet<Endpoint> sortedByX = new TreeSet<>();
for(Rect r: rects){
sortedByX.add(r.xStart);
sortedByX.add(r.xEnd);
}
TreeSet<Endpoint> sortedByY = new TreeSet<>();
int ret =0;
for(Endpoint ep: sortedByX){
Rect r = ep.rect;
if(ep.isStart){
ret+= countIntersections(sortedByY.subSet(r.yStart, false,r.yEnd, false),
r.yStart.val, r.yEnd.val);
sortedByY.add(r.yStart); sortedByY.add(r.yEnd);
} else {
sortedByY.remove(r.yStart); sortedByY.remove(r.yEnd);
}
}
return ret>0?ret+1:0; // count the first square with whom an intersection is found
}
private static int countIntersections(Set<Endpoint> eps, double minY, double maxY){
HashSet<Rect> rects = new HashSet<>();
for(Endpoint ep : eps){
rects.add(ep.rect);
}
return rects.size();
}
public static void main(String[] args) {
Rect [] rects = {
new Rect(1, 1, 3, 3),
new Rect(2, 5, 4, 6),
new Rect(2.5,2,3.5,5.5)
};
System.out.println(getNumIntersecting(rects));
}
}
This is very similar to Alex's solution. And the complexity could be further improved if we use Alex's mysterious DS...
It's a good solution, however one scenario is missing here:
you won't count rectangles "nested by Y". Here is an example.
if we have rectangles {0, 0, 3, 5}, {1, 1, 4, 4} and {2, 2, 5, 3} this algo reports 0. But there are 3 pairs of intersected rectangles.
Alex's solution here in the thread covers this case: we subtract all the rectangle which are completely below the current one and completely above the current one from total number of rectangles that have intersection with the current one by X.
This is a famous swipe line algorithm used to solve this problem.
First let's have a data structure that stores segments [le, ri] and can answer these questions:
1) query1(X) : how many segments are there with le > X.
2) query2(X) : how many segments are there with ri < X.
3) total number of segments in data structure.
4) Add segment
5) Delete segment
Then let's create a vector of events:
After we sort this array we can add events one by one and using the data structure described before we can update global answer if that is the beginning of the rectangle:
If it is the end of the rectangle we remove the segment:
Total complexity is O(nlogn) if we use set for DS.
- Alex February 01, 2014