Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Also make sure when you are sorting, if boundary value are same then a start should come before end.
my boundary class looks like this
enum BoundaryType
{
Start = 0,
End = 1
}
class Boundary : IComparable<Boundary>
{
public int Value { get; set; }
public BoundaryType BoundaryType { get; set; }
public int CompareTo(Boundary other)
{
if (Value == other.Value)
{
return BoundaryType.CompareTo(other.BoundaryType);
}
else
return Value.CompareTo(other.Value);
}
}
I guess the intersections should meet ai-1 < bi-1 < ai < bi < ai+1 < bi+1.(i-1, i and i+1 are indices)
So here is an array a0, b0, a1, b1, ......, an-1, bn-1;
For each number x, find the least number that is greater/equal to x. And found and the index (M) is an ODD number (in C/C++ index) then x is located in [a(M-1)/2, b(M-1)/2]. Record the occurrence and find the largest
For those intersections having overlap they can be split into sub-sections.
For instance, two sections like [1, 5], [2, 4].
Then [1, 5] can be split into [1, 2 - delta), [2, 4], (4 + delta, 5] and apply the same method in my last comment. And the occurrence of [1, 5] is sum of 3 sub-sections.
$bounds=array();
foreach($intervals as $intv) { //assume $intv[0]=low $intv[1]=high
$bounds[$intv[0]]=1;
$bounds[$intv[1]]=-1;
}
ksort ($bounds); //sort by key, which are bound values
$max_intersect=0; $intersects=0;
foreach($bounds as $bound =>$type){
if($type==1) $intersect++;
elseif($type==-1) $intersects--;
if($max_intersect <$intersects)
$max_intersect = $intersects;
}
return $max_intersect;
$bounds=array();
foreach($intervals as $intv) { //assume $intv[0]=low $intv[1]=high
$bounds[$intv[0]]=1;
$bounds[$intv[1]]=-1;
}
ksort ($bounds); //sort by key, which are bound values
$max_intersect=0; $intersects=0;
foreach($bounds as $bound =>$type){
if($type==1) $intersect++;
elseif($type==-1) $intersects--;
if($max_intersect <$intersects)
$max_intersect = $intersects;
}
return $max_intersect;
for each boundary b {
sweep[b.start]++
sweep[b.end]--
}
int current = 0, max = 0
bool recording = false
int start, end
for i = 0 to sweep.length {
current += sweep[i]
if (current > max) {
max = current
start = i
recording = true
}
if (sweep[i] < 0 && recording) {
end = i
recording = false
}
}
def find_point_intersect(ranges):
sorted_ranges = []
index = 0
for (low,high) in ranges:
sorted_ranges.append((low, index))
sorted_ranges.append((high, index))
index +=1
sorted_ranges.sort()
max_range = 0
max_range_so_far = 0
encountered_indices = {}
low = -sys.maxint
high = -sys.maxint
for i in range(len(sorted_ranges)):
(num, index) = sorted_ranges[i]
if max_range_so_far == 0 :
high = -sys.maxint
if not encountered_indices.has_key(index):
encountered_indices[index] = 0
max_range_so_far += 1
else:
if high == - sys.maxint:
high = num
max_range_so_far -= 1
if max_range_so_far > max_range:
low = num
max_range = max_range_so_far
print max_range
print low, high
import java.io.*;
import java.util.*;
class MaxOverlapCount {
private class Interval {
int begin;
int end;
public Interval(int begin, int end){
this.begin = begin;
this.end = end;
}
}
private class Point {
int value;
boolean isBegin;
public Point(int value, boolean isBegin) {
this.value = value;
this.isBegin = isBegin;
}
public int getValue() { return value; }
}
public static void main (String[] args) {
MaxOverlapCount maxOverlapCount = new MaxOverlapCount();
maxOverlapCount.findMaxOverlapCount();
}
public void findMaxOverlapCount(){
List<Interval> intervalList = new ArrayList<Interval>();
Interval interval1 = new Interval(1, 3);
Interval interval2 = new Interval(2, 3);
Interval interval3 = new Interval(2, 4);
intervalList.add(interval1);
intervalList.add(interval2);
intervalList.add(interval3);
List<Point> pointList = intervalsToPoints(intervalList);
Collections.sort(pointList, new PointComparator());
int overlapCount = 0;
int beginInterval = 0;
for(Point point : pointList){
if(point.isBegin){
beginInterval++;
} else {
beginInterval--;
}
if(beginInterval > overlapCount){
overlapCount = beginInterval;
}
}
System.out.println("Max overlap Count:" + overlapCount);
}
public List<Point> intervalToPoint(Interval interval){
List<Point> pointList = new ArrayList<Point>();
Point beginPoint = new Point(interval.begin, true);
Point endPoint = new Point(interval.end, false);
pointList.add(beginPoint);
pointList.add(endPoint);
return pointList;
}
public List<Point> intervalsToPoints(List<Interval> intervalList){
List<Point> pointList = new ArrayList<Point>();
for(Interval interval : intervalList){
List<Point> subPointList = intervalToPoint(interval);
pointList.addAll(subPointList);
}
return pointList;
}
public class PointComparator implements Comparator {
@Override
public int compare(Object o1, Object o2){
Point p1 = (Point) o1;
Point p2 = (Point) o2;
return p1.getValue() - p2.getValue();
}
}
}
I don't think the sweep-line algorithm will work. The question asks us to find a point which intersects with most number of intervals. Here is an example where the sweep-line algo is wrong..
If intervals are [1,5] [2,9] [12,16] [11,20] [14,21] the sweep line gives result as 0 when in fact you have [14,16] which intersects with 3 intervals.
Please correct me if I'm wrong.
You are wrong.
If you sort them you will have [1,5] the first then you will keep counting all the intervals to the next interval that doesn't intersect [1,5] which count to 1([2,9]) you go next to the next one which is[12,16] or [14,16],let's say [14,16] and you keep counting the next interval that intersect this new interval([14,16]) which count to 2([12,16],[14,21]) and plus [14,16] you get 3
store each boundary value as a separate element in an array with the information whether it's the start boundary or end boundary.
- DarkKnight October 14, 2012Sort this array by boundary value.
initialize an integer overLapCount = 0;
Traverse this array from start to finish
whenever you cross a "Start" boundary, increment overlapCount
whenever you cross an "End" boundary, decrement overlapCount
store the maxOverLapCountSoFar
at the end of the traversal you will have the information about what is the maximum possible overlap for a range.
You can easily modify this to store the range information as well.