Facebook

www.facebook.com
Engaged Employer

Interview

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

with the most number of intervals.
Answer

## Interview Answer

5 Answers

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 < n; i++) { q.enqueue(b[i]); if (q.size() > 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) while( queue_head < ai) 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

## Add Answers or Comments

To comment on this, Sign In or Sign Up.