## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
9
of 9 vote

store each boundary value as a separate element in an array with the information whether it's the start boundary or end boundary.
Sort 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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Using a Sweep Line algorithm approach I think is the way... can be done in N logN

Comment hidden because of low score. Click to expand.
1
of 1 vote

sweep line should work.
sort the endpoints.
low1-low2-low3-high1-high2-high3-low4-high4.
keep a counter.. increase it if you encounter low-type, reduce it if you encounter
high-type. keep the maxcount.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

\$bounds=array();
foreach(\$intervals as \$intv) { //assume \$intv=low \$intv=high
\$bounds[\$intv]=1;
\$bounds[\$intv]=-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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````\$bounds=array();
foreach(\$intervals as \$intv) { //assume \$intv=low \$intv=high
\$bounds[\$intv]=1;
\$bounds[\$intv]=-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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

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);
return pointList;
}

public List<Point> intervalsToPoints(List<Interval> intervalList){
List<Point> pointList = new ArrayList<Point>();
for(Interval interval : intervalList){
List<Point> subPointList = intervalToPoint(interval);
}
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();
}

}

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

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

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.

### 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.