Facebook Interview Question: giving lots of intervals [ai,... | Glassdoor

## Interview Question

Software Engineering Interview

# giving lots of intervals [ai, bi], find a point intersect

with the most number of intervals.

0

only come up with n^2 method in the interview process. interval tree crossed my mind, but too complex to implement in a short time. They are looking for nlgn solution, which I came up after interview. wtf.

intervals = [[a1, b1], [a2, b2], ..., [an, bn]]

sort(intervals);
priority_queue q;
int res = 0, point = -1;
for (int i = 0; i res) {
res = q.size();
point = q.front();
}
if (a[i] > q.front())
while (a[i] > q.front()) q.dequeue();
}

// res is the numbers of intersections, point is the number.

Interview Candidate on Mar 1, 2012
0

How do you sort the intervals?

Interested on Mar 8, 2012
0

First solution is correct.
The assumption is, the point is definitely one of ai.
Then
quicksort intervals by ai
for each intervals,
queue.insert (bi)
queue.pop()
updatemax(ai, queue.size)

buptrain on Mar 20, 2012
1

Jeez, how many times have they asked this same question?

Anonymous on Apr 9, 2012
0

I suspect the answer given by both the candidate and buptrain. If you look at this sorted interval group: (1,10), (2,5), (7,9). The algorithm returns 3 as # of intersections and return 10 as the point, which is obviously wrong.
(1): **********
(2): ****
(3): ***
The key problem here (or some additional assumption not specified by candidate) is the length of each interval varies, thus the next interval may have a shorter end value than the previous one even the start value is larger.

Anonymous on Apr 12, 2012