Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I don't know how the rectangles are represented. I assume it is represented by its four vertices: upper-left -> A(X1, Y1), lower-left -> B(X1, Y2), lower-right -> C(X2, Y2), upper-right -> D(X2, Y1). Then if a point (x, y) in a rectangle, its coordinates should satisfy a relationship:
X1 <= x <= X2 and Y1 <= x <= Y2.
Then we can sort the point list based on x-axis coordinate and y-axis coordinate, and store the two result separately for better search performance. Or if the number of points is large, we can consider using bit map to project each point onto the map.
At last, simply iterate over rectangles list and find if a point in the rectangle with the pre-processed point list or bit map.
/*
There is a list of rectangles and a list of points in a 2d space. Note that the edge of each rectangle are aligned to XY axis.
question is how to find rectangles with point or points inside
Note: 0,0 is top, left
*/
import java.util.*;
class Solution {
public static void main(String[] args) {
//create a list of rectangles and points
List<Rectangle> rectangles = new LinkedList<>();
List<Point> points = new LinkedList<>();
Point[][] rPoints = {{new Point(0, 0), new Point(10, 10)},
{new Point(5, 5), new Point(100, 100)},
{new Point(-10, 7), new Point(32, 1001)}};
for (Point[] p : rPoints) {
rectangles.add(new Rectangle(p[0], p[1]));
}
Point[] pPoints = {new Point(1,1), new Point(-1000, 5), new Point(6, 7)};
for (Point p : pPoints) {
points.add(p);
}
for (Rectangle r : rectangles) {
for (Point p : points) {
System.out.println(r + " contains point: " + p + " :" + r.containsPoint(p));
}
}
}
}
class Rectangle {
//Note: 0,0 is top, left
Point topLeft;
Point bottomRight;
public Rectangle(Point tl, Point br) {
topLeft = tl;
bottomRight = br;
}
public boolean containsPoint(Point p) {
return p.x <= bottomRight.x &&
p.x >= topLeft.x &&
p.y <= bottomRight.y &&
p.y >= topLeft.y;
}
public String toString() {
return "(topLeft: "+topLeft+", bottomRight:"+bottomRight+")";
}
}
class Point {
//Note: 0,0 is top, left
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(x: "+x+", y: "+y+")";
}
}
// brute force 19 minutes
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class FindEnclosingRectangles {
static class Point implements Comparable<Point>{
int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
//System.out.println(x + "," + y + "\t" + o.x + "," + o.y);
if(o.x != x){
return x - o.x;
} else {
return y - o.y;
}
}
}
static class Rectangle{
Point pLL, pUR;
Rectangle(Point pLL, Point pUR){
this.pLL = pLL;
this.pUR = pUR;
}
boolean contains(Point p){
boolean result = p.compareTo(pLL) >= 0 && pUR.compareTo(p) >= 0;
return result;
}
}
List<Rectangle> rectangles;
public FindEnclosingRectangles() {
rectangles = new LinkedList<Rectangle>();
}
private void addRectangle(Rectangle rectangle) {
rectangles.add(rectangle);
}
private List<Rectangle> find(Point point) {
List<Rectangle> res = new LinkedList<Rectangle>();
for(Rectangle r : rectangles){
if(r.contains(point)){
res.add(r);
}
}
return res;
}
public static void main(String[] args){
FindEnclosingRectangles wrapper = new FindEnclosingRectangles();
wrapper.addRectangle(new Rectangle(new Point(0,0), new Point(4,5)));
wrapper.addRectangle(new Rectangle(new Point(1,2), new Point(5,5)));
List<Rectangle> res = wrapper.find(new Point(3,4));
System.out.println(res.size());
res = wrapper.find(new Point(13,4));
System.out.println(res.size());
}
}
Fully working solution
struct Point
{
Point() :x(-1), y(-1){}
Point(int x, int y) :x(x), y(y){}
int x;
int y;
};
bool isPointInRec(const Rect& rect, const Point& pos)
{
return(
rect._leftUpper.y > pos.y &&
rect._leftUpper.x < pos.x &&
rect._rightLower.y < pos.y &&
rect._rightLower.x > pos.x
);
}
vector<Rect> findRectWithPoint(vector<Rect>& rects, vector<Point>& points)
{
vector<Rect> result;
for (const Rect& currRect : rects)
{
for (const Point& currPoint : points)
{
if (isPointInRec(currRect, currPoint))
{
result.push_back(currRect);
}
}
}
return result;
}
int main(int argc, const char* argv[])
{
vector<Rect> rectList = { { { 3, 5 }, { 5, 1 } },
{ { 1, 6 }, { 2, 4 } },
{ { 1, 2 }, { 2, 1 } },
{ { -3, -3 }, { -1, -5 } }
};
vector<Point> points = { { -2, -4 }, { 0, 0 }, { 10, 15 }, { 5, 6 }, { 7, 8 }, { -10, -30 }, { 6, 5 }, { 4, 4 } };
vector<Rect> res = findRectWithPoint(rectList, points);
}
Here is the C++ version of solution.
Running time is between O(M log N) and O(MN), where M is # of rectangles and N is number of points.
O(MN) is the worst case. I should say just O (MN).
I uses the binary search to find the point with x position within the given rectangle.
If it find it but its y position is not in rectangle it need to search both side, which leads to O(N).
bool bsearch(point *list, int s, int e, rect& target)
{
if (s > e)
return false;
int half = s+ (e-s)/2;
if (list[half].x >= target.low.x && list[half].x <= target.high.x )
{
if (list[half].y >= target.low.y && list[half].y <= target.high.y)
{
return true;
}
if (bsearch(list, s, half -1, target))
return true;
if (bsearch(list, half+1, e, target))
return true;
}
if (list[half].x < target.low.x)
return bsearch(list, half+1, e, target);
else
return bsearch(list, s, half-1, target);
}
list<rect> find_intersect_rect(rect* input, int len, point * points, int plen)
{
list<rect> result;
//sort by x value
quick_sort(points, 0, plen-1);
for (int i = 0; i < len; i++)
{
if (bsearch(points, 0, plen -1, input[i]))
result.push_back(input[i]);
}
return result;
}
If we keep track of rectangles overlap, we can exclude significant portions of candidate points each time we consider a new rectangle: if we find that a rectangle does not overlap with a given zone, we can ignore all points there contained.
My Java implementation:
static class Point {
double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
boolean inRect(Rect rect) {
return (x >= rect.left && y >= rect.top
&& x <= rect.right && y <= rect.bottom);
}
}
static class Rect {
double left, top, right, bottom;
public Rect(double left, double top, double right, double bottom) {
this.left = left;
this.top = top;
this.right = right;
this.bottom = bottom;
}
Rect mergeWith(Rect rect) {
if ((left > rect.right) || (rect.left > right)
|| (top > rect.bottom) || (rect.top > bottom)) {
return null;
}
return new Rect(Math.min(left, rect.left), Math.min(top, rect.top),
Math.max(right, rect.right), Math.max(bottom, rect.bottom));
}
}
Map<Rect, List<Point>> findPointsInRects(List<Point> points, List<Rect> rects) {
Map<Rect, List<Point>> zoneMap = new HashMap<>();
Map<Rect, List<Point>> resultMap = new HashMap<>();
for (Rect rect : rects) {
List<Point> candidatePoints = new ArrayList<>();
candidatePoints.addAll(points);
Rect mergedZone = rect; // let us initialize our current rect's zone
List<Point> mergedZonePoints = new ArrayList<>();
List<Rect> zonesToMerge = new ArrayList<>();
for (Rect zone : zoneMap.keySet()) {
List<Point> zonePoints = zoneMap.get(zone);
Rect rr = mergedZone.mergeWith(zone);
if (rr == null) { // disjoint zones -> remove candidates
candidatePoints.removeAll(zonePoints);
} else {
zonesToMerge.add(zone);
mergedZone = rr;
mergedZonePoints.addAll(zonePoints);
}
}
List<Point> rectPoints = new ArrayList<>();
for (Point point : candidatePoints) {
if (point.inRect(rect)) {
rectPoints.add(point);
}
}
resultMap.put(rect, rectPoints);
mergedZonePoints.addAll(rectPoints);
zoneMap.keySet().removeAll(zonesToMerge);
zoneMap.put(mergedZone, mergedZonePoints);
}
return resultMap;
}
Seems like the solution is either a k-d tree or a range tree.
- Omri Bashari January 22, 2015