CareerCup

Build a balanced tree of the x-coordinates of the points(appearing only at leaf nodes) which will allow you to perform queries like getting the points in a given range [l, r].

Annotate each node of the tree with a balanced tree of the y-coordinates (called Y-trees) of the points in the leaf nodes of the subtree. Thus each range query [l,r] can be represented as a set of O(log n) Y-trees.

Building this structure takes O(n (log n)^2) time and O(n log n) space.

Now given a rectangle, you can query the S points that lie in the rectangle, in O( (log n)^2 + S) time. First run the range query of [l,r], the width of the rectangle to get O(log n) Y-Trees. Then run the range query of [bottom,top] (the height of the rectange) on each Y-Tree we got. This is O( (log n)^2 + S) total.

Since we do this for each rectangle, the total query time is O(n (log n)^2) (could potentially be faster is lot of points lie within a single rectangle...).

That said, this is too much for an interview, to come up with and write pseudo-code. Perhaps there is an easier method.

(btw, if I recollect correctly, this is the idea behind a orthogonal-range search tree).

Does the following solve the problem in O(n log n)?

Sort the rectangles by the x-coordinate of the lower-left corner and remove those with this corner to the right of the point.

Sort the (remaining) rectangles by the x-coordinate of the upper-right corner and remove those with this corner to the left of the point.

Sort the (remaining) rectangles by the y-coordinate of the lower-left corner and remove those with this corner above the point.

Finally, sort the remaining rectangles by the y-coordinate of the upper-right corner and remove those with this corner below the point.

If there is nothing left, then no rectangle contains the point. Otherwise, the one left is as desired.

I think, this problem can be solved by KD Tree because all the rectangles are non-overlapping. We can split the set of rectangles in half by x and y axis alternatively and construct the tree.

The lookup algorithm would also be same as KDTree. This way you can construct the tree in O(nlogn) and lookup in O(logn).

PLEASE? A KD-tree? They will be more than happy to see you implement one in pseudocode... BTW a KD-Tree has O(n) worst-case complexity.

What they were probably looking for is this.
Sort all rectangles and points by their x and y coordinates into sorted sets Rx, Ry, Px and Py.

Then in each recursion level swap a bit which says whether to subdivide in X or Y direction. (This is just to make complexity analysis a whole heck of a lot easier)

You always use the middle element in the current subdivision of Rx, Ry, Px, Py as splitter to obtain the sets for the next subdivision.

The recursion terminates after log(n) steps when there is either none or one rectangle left. Then you check whether all points in the subdivided Px or Py are in there and add them to a result set.

The algorithm is at most O(n*log(n)^2) worst case... I have the proof on paper but it would be too tedious to carry it out here. Shouldn't be too hard ;).

found a mistake in the algo

how about a simpler approach of using divide of merge sort. keep sub dividing the set of rectangles till 1 rectangle remains. checking if a point is inside the rectangle is constant time operation.
there is no need to combine as the result is unique rectangle.
as a optimization , we can have global variable which says the search is complete. before we check for any inside condition for a rectangle we simply check if this variable is set. this will minimize the containment operation.

To get O(n log n * log n) complexity it means that we have to solve the problem by doing a sorting and organizing an array as a tree , to be able to search next in log n time.

My idea is to sort and organize the array of rectangles creating a structure for each node to be formed of : min x , max x, min y, max y. Next search in Log n time for each point if it fits in a rectangle.

O(nlogn log n) time and O (length of the rectangle array)

For the set of rectangles, create 4 sorted arrays, each storing the BottomLeft (BL) coordinate, the TopRight (TR) coordinate & an ID for the rectangle. The 4 arrays are sorted one each for the below (and named accordingly)
1. BL x value - BLX
2. TR x value - TRX
3. BL y value - BLY
4. TR y value - TRY
(thus far takes O(nlogn))

Function - FindBLXSet(Px)
{
//this is O(logn) assume using binary search
Search for Px in the array BLX looking at BL x-cord value 
//this returns all rectangles with BL x-cord >= Px
return ID list of all IDs that occur after this array index, including this one.
}

Function - FindBLXSet(Px)
{
//this is O(logn) assume using binary search
Search for Py in the array BLY looking at BL y-cord value 
//this returns all rectangles with BL y-cord >= Py
return ID list of all IDs that occur after this array index, including this one.
}

Function - FindTRXSet(Px)
{
//this is O(logn) assume using binary search
Search for Px in the array TRX looking at TR x-cord value 
//this returns all rectangles with TR x-cord <= Px
return ID list of all IDs that occur before this array index, including this one.
}

Function - FindTRYSet(Py)
{
//this is O(logn) assume using binary search
Search for Py in the array TRY looking at TR y-cord value 
//this returns all rectangles with TR y-cord <= Py
return ID list of all IDs that occur before this array index, including this one.
}

main()
{
Create arrays BLX, BLY, TRX, TRY as described above
for each point in set P {
IDList_BLX = FindBLXSet(Px)
IDList_BLY = FindBLYSet(Py)
IDList_TRX = FindTRXSet(Px)
IDList_TRY = FindTRYSet(Py)

if ( IDList_BLX intersection IDList_BLY intersection IDList_TRX intersection IDList_TRY) is empty 
	mark as no intersection for this point
else 
	//this should be exactly given the input constraint of non overlapping rectangles
	save ID as intersection rectangle for this point.
}
}

Now I have not written the intersection function, an approach like sort & compare first pair of lists, and the intersection with the next and so on, should lead to O(nlogn) to sort and O(n) to compare should work.

public static void main(String[] args) {
        /*
         * For each point 'p' in set P, find the rectangle 'r_p' in set R that contains 'p', 'r_p'
         * is unique because of the non-overlapping set.
         */

        // set R of n1 non-overlapping rectangles, whose sides are parallel to the x- and y-axes
        Set<Rectangle> rectangles = new HashSet<Rectangle>();
        // fill rectangles here...

        // set P of n2 points
        Set<Point> points = new HashSet<Point>();
        // fill points here...

        Rectangle[] rectanglesSortedByX = rectangles.toArray(new Rectangle[0]);
        // O(NlgN), N = rectangles.size
        Arrays.sort(rectanglesSortedByX, new Comparator<Rectangle>() {
            @Override
            public int compare(Rectangle r1, Rectangle r2) {
                return Integer.valueOf(r1.bottomLeft.x).compareTo(r2.bottomLeft.x);
            }
        });

        Rectangle[] rectanglesSortedByY = rectangles.toArray(new Rectangle[0]);
        // O(NlgN), N = rectangles.size
        Arrays.sort(rectanglesSortedByY, new Comparator<Rectangle>() {
            @Override
            public int compare(Rectangle r1, Rectangle r2) {
                return Integer.valueOf(r1.bottomLeft.y).compareTo(r2.bottomLeft.y);
            }
        });

        // O(N)
        for (Point point : points) {
            // O(lgN)
            Rectangle rectangle = findRectagnleByX(rectanglesSortedByX, point, 0, rectanglesSortedByX.length);
            if (rectangle == null) {
                System.out.println("there is not a rectangle for point=" + point);
            } else {
                // O(lgN)
                rectangle = findRectagnleByY(rectanglesSortedByY, point, 0, rectanglesSortedByY.length);
                if (rectangle == null) {
                    System.out.println("there is not a rectangle for point=" + point);
                } else {
                    System.out.println("point=" + point + " is covered by rectangle=" + rectangle);
                }
            }
        }
    }

    private static Rectangle findRectagnleByX(Rectangle[] sortedByX, Point point, int start, int end) {
        if (start >= end) {
            return null;
        }

        int middle = start + (end - start) / 2;

        if (sortedByX[middle].bottomLeft.x <= point.x && point.x <= sortedByX[middle].topRight.x) {
            return sortedByX[middle];
        } else if (sortedByX[middle].topRight.x < point.x) {
            return findRectagnleByX(sortedByX, point, middle + 1, end);
        } else {
            return findRectagnleByX(sortedByX, point, start, middle - 1);
        }
    }

    private static Rectangle findRectagnleByY(Rectangle[] sortedByY, Point point, int start, int end) {
        if (start >= end) {
            return null;
        }

        int middle = start + (end - start) / 2;

        if (sortedByY[middle].bottomLeft.y <= point.y && point.y <= sortedByY[middle].topRight.y) {
            return sortedByY[middle];
        } else if (sortedByY[middle].topRight.y < point.y) {
            return findRectagnleByY(sortedByY, point, middle + 1, end);
        } else {
            return findRectagnleByY(sortedByY, point, start, middle - 1);
        }
    }

You can do it in O(n*lg(n)) with a sweep line algorithm.

> Sort all rectangles left x and all points by x.
> Move sweep line with 3 kinds of event points: start/end of rectangle and point.
> If left/right rectangle boundary is encountered then add/remove its y-interval to a line. Can be done in log(n) because rectangles don't intersect.
> If a point is encountered then check to which y-interval it belongs. Can be done in log(n) because intervals on the line stored sorted.