Plane Sweep To Solve a hard Google Onsite Problem @08/10


  • 1
    F

    Yesterday, I meet a hard problem on Google onsite, of course, I do not finished to solve it in the limited time, I am really depressed as most of my classmates are asked to solve some much more easy problem set.

    So let us check the problem directly ....

    Given N rectangle in the plane, how to check whether all the rectangle can form a big rectangle exactly !

    To make it clear, the interviewer mean that all the matrix should have no gap in between and no overlap to form a big rectangle !

    At the first glance, I just think a brute force solution to sweep from the left most edge to the most right edge and check whether along all the edges we can fill the big rectangle exactly !. ... So finally, my method is a little messy, I just can not implement elegently....So you know what happened next ...... Goodbye, Google.....

    Let us first check out a easy solution :

    We can just calculate all the rectangle area, and check whether the overall area equal the most outer rectangle area. Then we just need to check whether there exists 2 rectangle interact in the plane !

    Here is basic implementation by myself ....

    struct Rect {
    	int x0, x1, y0, y1;
    };
    
    class Solution {
    	bool rect_overlap(Rect& a, Rect& b) {
    		if (a.x0 > b.y0 || b.x0 > a.y0) { return false; }
    		if (a.y0 > b.y1 || b.y0 < a.y1) { return false; }
    		return true;
    	}
    
    	int rect_area(Rect &a) {
    		return (y1 - y0) * (x1 - x0);
    	}
    
    	bool rect_check(vector<Rect> &rects) {
    		int n = rects.size();
    		long long sum_area = 0;
    		int xx0 = rects[0].x0, yy0 = rects[0].y0;
    		int xx1 = rects[1].x1, yy1 = rects[0].y1;
    		for (int i = 0; i < n; i++) {
    			xx0 = min(rects[i].x0, xx0);
    			yy0 = min(rects[i].y0, yy0);
    			xx1 = max(rects[i].x1, xx1);
    			yy1 = max(rects[i].y1, yy1);
    			sum_area += rect_area(rects[i]);
    			for (int j = i + 1; j < n; j++) {
    				if (rect_overlap(rects[i], rects[j])) {
    					return false;
    				}
    			}
    		}
    		return sum_area == (xx1 - xx0) * (yy1 - yy0);
    	}
    };
    

    Hehe, of course this time complexicity is O(N^2) ! But we want O(NlogN) ....*

    Let us change the orginal problem into a new problem :

    Problem Def :

    Given N rectangle in the plane, how to check whether there are 2 rectangle overlap in NlogN time cost

    To solve this problem, I strong recommend you to refer the post by a Chinese guy

    The main ideas is to use the plane swap ideas to solve the problem !

    We will split the plane along all the edges of the rectangle and swap all the lines from left to right !

    alt text

    I will not delve into the details, just give you the template to know the key ideas behind the problem ...

    class SegmentTree {
    	void  Init() ; 
    	void  Insert(int  left , int  right);  
    	void  Delete(int  left , int  right);
    	void  hasIntersect(int  left , int  right); 
    };
    
    
    class Solution {
    	boolean has_rectangle_intersect(rectangle r[] , int n) {
    		map all the {r[0].left_x , r[0].right_x , ... , 
    		      r[n-1].left_x , r[n-1].right_x} to the mapx[] ; 
    		for( i = 0 ; i < n ; ++ i){
    		event[i<<1]     = {r[i].left_x , r[i].down_y , r[i].up_y , +1 } ;
    		event[(i<<1)|1] = {r[i].right_x, r[i].down_y , r[i].up_y , -1 } ; 
    		}
    		sort event[0..2*n-1] based on x in increasing order
    		tree.init() ;
    		for( i = 0 ; i < n<<1 ; ++ i){
    		 if( event[i] is insert event){
    		     if( tree.hasIntersection(event[i].down_y , event[i].up_y) )
    		             return true ;
    		    tree.Insert(event[i].down_y , event[i].up_y) ;
    		 }else{
    		     tree.Delete(event[i].down_y , event[i].up_y);
    		}  
    		}
    		return false ;
    	}
    };
    
    

  • 0

    @fight-for-dream
    This is really a hard problem. Thanks so much for sharing!
    I'm thinking: what if the rectangles are not fixed on the plane, but rather they can move?
    Then the question becomes: given N rectangles, is it possible to position them to form a larger rectangle? - I have no clue how to solve this one...


  • 0
    A

    can we just make a hashset which contains all the previous points? ie we traverse each rectangle and add all its point to the hashset. we then move on to the next one and if ever reach a point thats already in the hashset then we can stop.


  • 0

    @alan28
    Sorry I didn't get it - if the rectangles can move, each rectangle should be represented by (w, h) instead of points with x/y values. Please correct me if I was wrong.


  • 0
    A

    @alan28 how would that work if your rectangles are large? your running time and space could be arbitrarily bad, regardless of the number of rectangles in the input.


  • 5
    A

    This is different from OP's solution. OP checks whether N rectangles have any intersection, while I avoid all geometric tests. I sweep from left to right and check that left-hand boundaries of rectangles match up with right-hand boundaries of rectangles. It's also O(n log n).

    Given N rectangles with integer coordinates, check whether they are an exact
    cover of a rectangle

    If you don't know already, Google's on-site interview process involves 5
    independent interviews in one day. In each one a Google Software Engineer poses
    a problem that should be solved in 45 min to 1 hr. The interviewee can code on a
    white board or in Google Docs (check with your recruiter for details) in a
    language of their choice, but not pseudo-code.

    By itself, the question is not all that intimidating, but the time-limit can
    make it quite challenging. That's why I'm practising!

    As usual, there is a fairly straightforward "brute force" solution, and some
    better solutions. I'll give hints and solutions immediately after the jump so
    avoid spoilers by not looking past the example inputs yet.

    2_1471192144391_isbigrect.png

    Hint 1

    Try to find a brute-force solution by looking at the total area of the rectangles.

    Hint 2

    After computing the area, can you avoid comparing every pair of rectangles?

    Hint 3

    The problem can be solved in O(N log N), both with and without computing areas.

    Hint 4

    What needs to occur at every left-hand segment of an input rectangle that is
    interior to the smallest rectangle that bounds the input rectangles? At every
    right-hand segment? At the vertical segments not interior?

    Solutions from area

    One solution is to compute the area of the smallest bounding rectangle, and the
    combined areas of the N input rectangles. The input data is unsorted, so you
    need to do an O(N) scan of the input to find the minimum and maximum points,
    both vertically and horizontally (up to 4 points). If the areas differ, output
    False, and if they are the same, you need to check that no pair of input
    rectangles intersect. To see why, look at the input below.

    1_1471192144390_areaprobleminput.png

    Testing whether a pair of rectangles intersect is
    a simple, O(1) calculation
    (though I would understand if you failed to get it onto the whiteboard in 5
    minutes under pressure), so we know we can finish in O(N^2) time by comparing (N
    choose 2) pairs of input rectangles.

    Some light reading suggests that the intersections can be tested in O(N log N)
    time in some cases, but the solutions seem far from simple. I didn't look at
    this very deeply, but for further reading:

    R-trees on StackOverflow
    R-trees on Wikipedia
    Another answer on StackOverflow
    The Princeton lecture cited in the above StackOverflow answer

    I'll now present a solution that does not require any 2D geometric tests.

    My Solution

    Imagine, first, that the (smallest) rectangle bounding the inputs is a cylinder,
    so that its leftmost edge coincides with its rightmost edge. Now we can state
    the 'algorithm' in one sentence:

    If **(P) every point interior to a right-hand edge of an input rectangle is unique,
    and it coincides with a point of a left-hand edge of an input rectangle, and
    vise versa **, then we (Q) output True, and otherwise we output False.

    Take a moment to let that sink in. We are claiming that P if and only if Q. Let
    us make clear here that when we say rectangles intersect, we mean that their
    interiors intersect. The explanation is a bit dense, but hopefully you'll come
    to the same conclusions by making some drawings.

    0_1471192144389_algorithmbigrect.png

    If P is false, then one of two things can happen. If points interior to the
    right-hand edges of two distinct rectangles coincide, then the rectangles
    intersect. Otherwise, without loss of generality, we may assume there is there
    is some point p on a left-hand edge of an input rectangle, call it A, that
    does not coincide with a point on a right-hand edge of an input rectangle. Thus,
    p is interior to a small open disc that both contains points interior to A
    and points exterior to A. The same disc is either entirely inside a rectangle
    distinct from A, which will necessarily intersect with A, or it contains
    points exterior to all rectangles distinct from A, and thus contains a hole in
    the bounding cylinder. Thus we output False, so Q is false.

    If Q is false, on the other hand, then either two distinct rectangles intersect,
    or a point in the bounding cylinder falls outside of all input rectangles. If
    rectangles intersect and they have intersecting vertical segments, then P is
    false, so we may assume that is not the case. But then, the vertical segment of
    one rectangle must be interior to another rectangle, which again falsifies P.
    Finally, if a point falls outside of all rectangles, then there are vertical
    segments to its left and right that falsify P.

    Thus, we have shown that P is a necessary and sufficient condition for the N
    rectangles to be an exact cover of a rectangle, q.e.d.

    Now we need to code the solution. The short of it is, we sort a copy of the
    input rectangles by left-edge x-coordinates, and we sort another copy by
    right-edge x-coordinates. The first left edge and last right edge are special
    cases, but are easily dealt with. We then process the vertical segments in the
    sorted lists, at each x-coordinate, and simply compare the lists.

    The bottleneck in time-complexity is in sorting the inputs, plus we need O(N)
    space to make left-edge-sorted and right-edge-sorted copies of the inputs.

    I am assuming that an input rectangle is given as a bottom-left point and a
    top-right point; for example, a unit square is [[1,1],[2,2]].

    A final word of warning before you delve into my Python code. I am primarily a
    C-programmer leveraging some features of Python, so my code is not very
    "Pythonic". Suggestions, improvements, and more test cases welcome.

    def isBigRect(rectangles):
        if rectangles==[]:
            return True
        L=processBoundaries(rectangles,leftOrRight='left')
        R=processBoundaries(rectangles,leftOrRight='right')
        if L==False or R==False or not len(L)==len(R):
            return False
        L[-1][0]=R[-1][0]
        R[0][0]=L[0][0]
        if not L==R:
            return False
        else:
            return True
    
    def processBoundaries(B,leftOrRight='left'):
        x0orx1=0
        if leftOrRight=='right':
            x0orx1=1
            res=[[]]
        elif leftOrRight=='left':
            x0orx1=0
            res=[]
        else:
            print 'process boundaries input error'
            return False
        B=[ [x[x0orx1][0],[x[0][1],x[1][1]]] for x in B]
        B.sort(cmp=lambda x,y: x[0]-y[0])
        i=0
        while i<len(B):
            x=B[i][0]
            res.append( [x,[]] )
            while i<len(B) and B[i][0]==x:
                res[-1][1].append(B[i][1])
                i=i+1
            res[-1][1]=mergeSpecialIntervals(res[-1][1])
            if res[-1][1]==False:
                return False
        if leftOrRight=='right':
            res[0]=['first',res[-1][1]]
        else:
            res.append(['last',res[0][1]])
        return res
    
    def mergeSpecialIntervals(L):
        if L==[]:
            return False
        if len(L)==1:
            return L
        L.sort(cmp=lambda x,y: x[0]-y[0])
        res=[L[0]]
        for i in range(len(L)-1):
            if L[i][1]>L[i+1][0]:
                return False
            elif L[i][1]==L[i+1][0]:
                res[-1][1]=L[i+1][1]
                i=i+2
            else:
                res.append(L[i])
                i=i+1
        if i == len(L)-1:
            res.append(L[i])
        return res
    
    
    A=[[[[0,0],[4,1]],
        [[7,0],[8,2]],
        [[6,2],[8,3]],
        [[5,1],[6,3]],
        [[4,0],[5,1]],
        [[6,0],[7,2]],
        [[4,2],[5,3]],
        [[2,1],[4,3]],
        [[0,1],[2,2]],
        [[0,2],[2,3]],
        [[4,1],[5,2]],
        [[5,0],[6,1]]],
    
       #shuffled the above a little
       [[[0,0],[4,1]],
        [[7,0],[8,2]],
        [[5,1],[6,3]],
        [[6,0],[7,2]],
        [[4,0],[5,1]],
        [[4,2],[5,3]],
        [[2,1],[4,3]],
        [[0,2],[2,3]],
        [[0,1],[2,2]],
        [[6,2],[8,3]],
        [[5,0],[6,1]],
        [[4,1],[5,2]]],
    
       [[[0,0],[4,1]]],
    
       [],
    
       #vertical stack
       [[[0,0],[1,1]],
    	[[0,1],[1,2]],
    	[[0,2],[1,3]],
    	[[0,3],[1,4]],],
       
       #horizontal stack
       [[[0,0],[1,1]],
    	[[1,0],[2,1]],
        [[2,0],[3,1]],
        [[3,0],[4,1]],],
    
       ]
    
    print 'should be True'
    for a in A:
        print isBigRect(a)
    
    
    B=[
        #missing a square
        [[[0,0],[4,1]],
         [[7,0],[8,2]],
         [[6,2],[8,3]],
         [[5,1],[6,3]],
         [[6,0],[7,2]],
         [[4,2],[5,3]],
         [[2,1],[4,3]],
         [[0,1],[2,2]],
         [[0,2],[2,3]],
         [[4,1],[5,2]],
         [[5,0],[6,1]]],
        
        #exceeds top boundary
        [[[0,0],[4,1]],
         [[7,0],[8,2]],
         [[5,1],[6,4]],
         [[6,0],[7,2]],
         [[4,0],[5,1]],
         [[4,2],[5,3]],
         [[2,1],[4,3]],
         [[0,2],[2,3]],
         [[0,1],[2,2]],
         [[6,2],[8,3]],
         [[5,0],[6,1]],
         [[4,1],[5,2]]],
        
        #two overlapping rectangles
        [[[0,0],[4,1]],
         [[0,0],[4,1]]],
        
        #exceeds right boundary
        [[[0,0],[4,1]],
         [[7,0],[8,3]],
         [[5,1],[6,3]],
         [[6,0],[7,2]],
         [[4,0],[5,1]],
         [[4,2],[5,3]],
         [[2,1],[4,3]],
         [[0,2],[2,3]],
         [[0,1],[2,2]],
         [[6,2],[8,3]],
         [[5,0],[6,1]],
         [[4,1],[5,2]]],
    
        # has an intersecting pair
        [[[0,0],[5,1]],
         [[7,0],[8,2]],
         [[5,1],[6,3]],
         [[6,0],[7,2]],
         [[4,0],[5,1]],
         [[4,2],[5,3]],
         [[2,1],[4,3]],
         [[0,2],[2,3]],
         [[0,1],[2,2]],
         [[6,2],[8,3]],
         [[5,0],[6,1]],
         [[4,1],[5,2]]],
        
        #skips column 4
        [[[0,0],[4,1]],
         [[7,0],[8,2]],
         [[5,1],[6,3]],
         [[6,0],[7,2]],
         [[2,1],[4,3]],
         [[0,2],[2,3]],
         [[0,1],[2,2]],
         [[6,2],[8,3]],
         [[5,0],[6,1]],],
    
    
        #exceed left boundary
        [[[0,0],[4,1]],
         [[7,0],[8,2]],
         [[5,1],[6,3]],
         [[6,0],[7,2]],
         [[4,0],[5,1]],
         [[4,2],[5,3]],
         [[2,1],[4,3]],
         [[-1,2],[2,3]],
         [[0,1],[2,2]],
         [[6,2],[8,3]],
         [[5,0],[6,1]],
         [[4,1],[5,2]]],
    
    
       #horizontal stack with overlapping left boundaries at x=1
        [[[0,0],[1,1]],
         [[1,0],[2,1]],
         [[1,0],[3,1]],
         [[3,0],[4,1]],],
    ]
    
    print 'should be False'
    for b in B:
        print isBigRect(b)
    

  • 0
    A

    @fight.for.dream Can you explain the n-rectangles intersection solution in O(n log n)? I have looked around and it doesn't look that simple. I doubt they expected you to code this.


  • 0

    @StefanPochmann
    Do you have any good idea for this question?


  • 1

    @alejandroerickson Nice idea by you. As for @fight.for.dream's, I think a segment tree is overkill. Because we don't need to support overlapping segments here, as we can simply return false when we detect an overlap. So we can just use a C++ set of intervals or a map mapping interval starts to interval ends or lengths.


  • 0
    R

    would it be possible to share in which office you did the interview? thanks!


  • 0
    M

    Every rectangle would have two intervals (y1,y2) on y axis and (x1, x2) on x axis. We need to sort all the y coordinates first based on this intervals and then x coordinates based on this interval.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.