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.

- JAR February 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you explain this a little more with an example?

- hulk February 10, 2017 | Flag Reply
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;
		}
		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
}

- Mei Li February 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please explain more with an example

- A February 13, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More