Facebook Interview Question for Software Developers

Interview Type: In-Person

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

``````Sort all of your rectangles' min and max x coordinates into an array, as "start-rectangle" and "end-rectangle" events

Step through the array, adding each new rectangle encountered (start-event) into a current set

Simultaneously, maintain a set of "non-overlapping rectangles" that will be your output set

Any time you encounter a new rectangle you can check whether it's completely contained already in the current / output set (simple comparisons of y-coordinates will suffice)

If it isn't, add a new rectangle to your output set, with y-coordinates set to the part of the new rectangle that isn't already covered.

Any time you hit a rectangle end-event, stop any rectangles in your output set that aren't covering anything anymore.``````

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

Can you explain this a little more with an example?

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

1. find all the rectangles overlapping the given area. by matching if any of the four corner points are in the area.

2. After step 1, try to find the minual set none overlapping - call findMinSet(rectList)

``````static List<Rectangle> findMinSet(List<Rectangle> rectList){
Set<Rectangle> markedOut = new HashSet<Rectangle>();
findMinSet(rectList, markedOut);
}
static List<Rectangle> findMinSet(List<Rectangle> rectList, Set<Rectangle> markedOut){
Set<Rectangle> minSet = new HashSet<Rectangle>();
for (Rectangle rect: rectList){
if (markedOut.get(rect) != null) {
continue;
}
List<Rectangle> nonOverlaps = findNonOverlaps(rect, rectList);
Set<Rectangle> subMinSet = findMinSet(nonOverlaps);
if(subMinSet.size() +1 < minSet.size()){
minSet = subMinSet;
}
}
return minSet;
}
static List<Rectangle> findNonOverlaps(Rectangle rect, List<Rectangle> rectList){
Set<Rectangle> markedOut = new HashSet<Rectangle>();
List<Rectangle> nonOverlaps = new ArrayList<Rectangle>();
for (Rectangle rectangle: rectList){
if (markedOut.get(rect) != null || overlap(rect, rectangle) {
continue;
}
}
return nonOverlaps;
}
static boolean overlap(Rectangle rect1, Rectangle rect2){
//todo: compare corners and levels
}``````

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

Can you please explain more with an example

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.