Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
10
of 10 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.

- DarkKnight October 14, 2012 | Flag Reply
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);
    }
}

- DarkKnight October 14, 2012 | Flag
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

- marcelovox2 October 14, 2012 | Flag Reply
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.

- dud3cod3r October 14, 2012 | Flag Reply
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

- peter tang October 14, 2012 | Flag Reply
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.

- peter tang October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$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;

- Anonymous October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$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;

- Anonymous October 14, 2012 | Flag Reply
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
  }
}

- Test October 15, 2012 | Flag Reply
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

- Anonymous February 19, 2013 | Flag Reply
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);
        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();
      }
      
   } 
	
}

- swapsmagic December 15, 2015 | Flag Reply
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.

- Anonymous October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- florin314 October 26, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More