Facebook Interview Question
Software DevelopersInterview Type: In-Person
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;
}
markedOut.add(rect);
List<Rectangle> nonOverlaps = findNonOverlaps(rect, rectList);
Set<Rectangle> subMinSet = findMinSet(nonOverlaps);
if(subMinSet.size() +1 < minSet.size()){
subMinSet.add(rect);
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;
}
nonOverlaps.add(rectangle);
}
return nonOverlaps;
}
static boolean overlap(Rectangle rect1, Rectangle rect2){
//todo: compare corners and levels
}
- JAR February 10, 2017