Facebook

  www.facebook.com
  www.facebook.com

Interview Question

Software Engineering 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.