Microsoft Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
Algo,
You need to check only 4 positions for this. Find nearest left, right, top and bottom edge of the rectangles who overlaps the point P. then calculate then minArea(left , right, top bottom) rectangle gives you the answer.
Algorithm will take constant time if you can find those edges in constant time else it slips to O(n) for finding part overtime.
I think we can do it in O(log n) using interval trees. Lets say the given point is (x,y). Lets say, the positions of lower-left (xL, yL) & upper-right (xH, yH) corners of each rectangle are given. We will create two interval trees. Each node of first interval tree (say treeX) will have pair (xL, xH) corresponding to each rectangle. Similarly, each node of second interval tree (say treeY) will have pair (yL, hH) corresponding to each rectangle. In first pass (which is O(log n)), we will use treeX to get all the rectangles for which (xL < x < xH). In second pass (which is also order O(log n)), we will use treeY to get the minimum rectangle that contains (x,y).
This will be O(n), but could be done in parallel by distributing the list of rectangles to multiple nodes.
- gen-y-s April 10, 2016