Facebook Interview Question for Software Engineer / Developers

• -1
of 1 vote

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

Seems like the solution is either a k-d tree or a range tree.

Comment hidden because of low score. Click to expand.
0

Please mention algorithm or code for kd tree solution

Comment hidden because of low score. Click to expand.
0

Mention either algorithm or code for kdtree solution

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please clarify question. How to find rectangle that contains a point?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do we have to find the one among the given rectangle which contains all the given list of points or lie on the rectangle itself? or do we have to form a new rectangle with the coordinates of the list of rectangles? please clarify?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
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

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) {
}

Point[] pPoints = {new Point(1,1), new Point(-1000, 5), new Point(6, 7)};
for (Point p : pPoints) {
}

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+")";
}

}``````

Comment hidden because of low score. Click to expand.
0

the 2 points in your rectangle should be bottomLeft and topRight instead. Since your second points has both Y and X bigger than the first one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// brute force 19 minutes

import java.util.Arrays;
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() {
}

}

private List<Rectangle> find(Point point) {

for(Rectangle r : rectangles){
if(r.contains(point)){
}
}

return res;
}

public static void main(String[] args){
FindEnclosingRectangles wrapper = new FindEnclosingRectangles();

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());
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}``````

Comment hidden because of low score. Click to expand.
0

Forgot to add def of Rect in main post

``````struct Rect
{
Rect(const Pos& leftUpper,
const Pos& rightLower) :_leftUpper(leftUpper),
_rightLower(rightLower){}
Pos _leftUpper;
Pos _rightLower;

};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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<>();

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 {
mergedZone = rr;
}

}

List<Point> rectPoints = new ArrayList<>();
for (Point point : candidatePoints) {
if (point.inRect(rect)) {
}
}
resultMap.put(rect, rectPoints);

zoneMap.keySet().removeAll(zonesToMerge);
zoneMap.put(mergedZone, mergedZonePoints);

}

return resultMap;

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.