Facebook Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
6
of 8 vote

public static int mergeSegments(int[][] segments) {
        Arrays.sort(segments, (x, y) -> x[0] - y[0]);

        int result = 0;
        int last = 0;
        for(int[] seg : segments) {
            result += Math.max(seg[1] - Math.max(last, seg[0]), 0);
            last = Math.max(last, seg[1]);
        }
        return result;
    }

Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

- aonecoding4 January 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its very simple, the code works.
Just put those interval on a line and see. U'll understand

- nitinguptaiit March 31, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesnt work for
[[1,4],[6,8],[4,6],[10,15]]

- voldetort August 02, 2020 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It is the overlapping intervals questions with a small modification.
If you have seen at least one such interval question - all of them are easy, if you have never seen them - they will be impossible to solve.

function intervalTotalRange(intervals) {
  var starts = intervals.map(i => i.start).sort((a, b) => a - b);
  var ends = intervals.map(i => i.end).sort((a, b) => a - b);
  var totalRange = 0;
  var currentStart = 0;
  var currentCount = 0;
  for (var i = 0, j = 0; i < starts.length && j < ends.length;) {
    if (starts[i] <= ends[j]) {
      // start point
      if (currentCount == 0) {
        currentStart = starts[i];
      }
      currentCount++;
      i++;
    } else {
      // finish point
      currentCount--;
      if (currentCount == 0) {
        totalRange += (ends[j] - currentStart);
      }
      j++;
    }
  }
  totalRange += (ends[ends.length - 1] - currentStart);
  return totalRange;
}

- Wolf January 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work for - intervalTotalRange([[1,10],[5,8],[7,9]])

The total overlap duration is from 5-9. Which is 4 hours. But the function above gives 9 hours.

- Noit January 27, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

([[1,10],[5,8],[7,9]])

As per my understanding, this set should result in 9 hours because of (1,10) and other two intervals are within it.

Am I wrong?

- shaum January 27, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n * logn) complexity as this is a classic overlapping intervals problem that requires sorting start and end points.

function intervalTotalRange(intervals) {
  var starts = intervals.map(i => i.start).sort((a, b) => a - b);
  var ends = intervals.map(i => i.end).sort((a, b) => a - b);
  var totalRange = 0;
  var currentStart = 0;
  var currentCount = 0;
  for (var i = 0, j = 0; i < starts.length && j < ends.length;) {
    if (starts[i] <= ends[j]) {
      // start point
      if (currentCount == 0) {
        currentStart = starts[i];
      }
      currentCount++;
      i++;
    } else {
      // finish point
      currentCount--;
      if (currentCount == 0) {
        totalRange += (ends[j] - currentStart);
      }
      j++;
    }
  }
  totalRange += (ends[ends.length - 1] - currentStart);
  return totalRange;

}

- Wolf January 19, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simpler solution is possible if intervals are always given by ordered pair integers and their total range is not too large.

def coverage(intervals):
    mina = 2**64
    maxb = -2**64
    for interval in intervals:
        mina = min(mina, interval[0])
        maxb = max(maxb, interval[1])
    mask = [0]*(maxb - mina)
    for interval in intervals:
        for i in range(interval[0], interval[1]):
            mask[i-mina] = 1
    return sum(mask)

Too naive?

- baites January 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a nice solution if the total range of the intervals is small enough. Note that in the worst case, all entries in the mask must be marked True (or 1 in your case), which takes O(total range) time, which is exponential in the input size (as the interval points are encoded in binary).

- Anonymous March 01, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
 { 

    ArrayList<List<Integer>> rangeList = new ArrayList<>();
		rangeList.add(Arrays.asList(1,4));
		rangeList.add(Arrays.asList(6,8));
		rangeList.add(Arrays.asList(2,4));
		rangeList.add(Arrays.asList(7,9));
		rangeList.add(Arrays.asList(10,15));
		
		ArrayList<List<Integer>> result = mergeRange(rangeList);
		
		System.out.println(sumRange(result));
		
	}
	
	public static int sumRange(ArrayList<List<Integer>> list) {
		
		int sum = 0;
		for(int i=0; i<list.size(); i++) {
			sum = sum + (list.get(i).get(1) - list.get(i).get(0));
		}
		
		return sum;
	}
	
	public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
	{
	  if(rangeList.isEmpty()) return rangeList;

	  ArrayList<List<Integer>> result = new ArrayList<>();

	  Collections.sort(rangeList, new Comparator<List<Integer>>() {
	      @Override
	      public int compare(List<Integer> range1, List<Integer> range2)
	      {
	        return range1.get(0) - range2.get(0);
	      }
	  });

	    List<Integer> first = rangeList.get(0);
			int start = first.get(0);
			int end = first.get(1);

	    for(int i=0; i<rangeList.size(); i++)
	    {
	      List<Integer> current = rangeList.get(i);

	      if(current.get(0) <= end)
	      {
	        end = Math.max(current.get(1), end);
	      }
	      else
	      {
	        ArrayList<Integer> temp = new ArrayList<>();
	        temp.add(start);
	        temp.add(end);
	        result.add(temp);
	        start = current.get(0);
	        end = current.get(1);
	      }
	    }
	    
	    ArrayList<Integer> temp = new ArrayList<>();
	    temp.add(start);
	    temp.add(end);
	    result.add(temp);

	    return result;
	    
	}

- ihsanA January 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
 { 

    ArrayList<List<Integer>> rangeList = new ArrayList<>();
		rangeList.add(Arrays.asList(1,4));
		rangeList.add(Arrays.asList(6,8));
		rangeList.add(Arrays.asList(2,4));
		rangeList.add(Arrays.asList(7,9));
		rangeList.add(Arrays.asList(10,15));
		
		ArrayList<List<Integer>> result = mergeRange(rangeList);
		
		System.out.println(sumRange(result));
		
	}
	
	public static int sumRange(ArrayList<List<Integer>> list) {
		
		int sum = 0;
		for(int i=0; i<list.size(); i++) {
			sum = sum + (list.get(i).get(1) - list.get(i).get(0));
		}
		
		return sum;
	}
	
	public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
	{
	  if(rangeList.isEmpty()) return rangeList;

	  ArrayList<List<Integer>> result = new ArrayList<>();

	  Collections.sort(rangeList, new Comparator<List<Integer>>() {
	      @Override
	      public int compare(List<Integer> range1, List<Integer> range2)
	      {
	        return range1.get(0) - range2.get(0);
	      }
	  });

	    List<Integer> first = rangeList.get(0);
			int start = first.get(0);
			int end = first.get(1);

	    for(int i=0; i<rangeList.size(); i++)
	    {
	      List<Integer> current = rangeList.get(i);

	      if(current.get(0) <= end)
	      {
	        end = Math.max(current.get(1), end);
	      }
	      else
	      {
	        ArrayList<Integer> temp = new ArrayList<>();
	        temp.add(start);
	        temp.add(end);
	        result.add(temp);
	        start = current.get(0);
	        end = current.get(1);
	      }
	    }
	    
	    ArrayList<Integer> temp = new ArrayList<>();
	    temp.add(start);
	    temp.add(end);
	    result.add(temp);

	    return result;
	    
	}

- IhsanA January 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args)
 { 

    ArrayList<List<Integer>> rangeList = new ArrayList<>();
		rangeList.add(Arrays.asList(1,4));
		rangeList.add(Arrays.asList(6,8));
		rangeList.add(Arrays.asList(2,4));
		rangeList.add(Arrays.asList(7,9));
		rangeList.add(Arrays.asList(10,15));
		
		ArrayList<List<Integer>> result = mergeRange(rangeList);
		
		System.out.println(sumRange(result));
		
	}
	
	public static int sumRange(ArrayList<List<Integer>> list) {
		
		int sum = 0;
		for(int i=0; i<list.size(); i++) {
			sum = sum + (list.get(i).get(1) - list.get(i).get(0));
		}
		
		return sum;
	}
	
	public static ArrayList<List<Integer>> mergeRange(ArrayList<List<Integer>> rangeList)
	{
	  if(rangeList.isEmpty()) return rangeList;

	  ArrayList<List<Integer>> result = new ArrayList<>();

	  Collections.sort(rangeList, new Comparator<List<Integer>>() {
	      @Override
	      public int compare(List<Integer> range1, List<Integer> range2)
	      {
	        return range1.get(0) - range2.get(0);
	      }
	  });

	    List<Integer> first = rangeList.get(0);
			int start = first.get(0);
			int end = first.get(1);

	    for(int i=0; i<rangeList.size(); i++)
	    {
	      List<Integer> current = rangeList.get(i);

	      if(current.get(0) <= end)
	      {
	        end = Math.max(current.get(1), end);
	      }
	      else
	      {
	        ArrayList<Integer> temp = new ArrayList<>();
	        temp.add(start);
	        temp.add(end);
	        result.add(temp);
	        start = current.get(0);
	        end = current.get(1);
	      }
	    }
	    
	    ArrayList<Integer> temp = new ArrayList<>();
	    temp.add(start);
	    temp.add(end);
	    result.add(temp);

	    return result;
	    
	}

- ihsan.a January 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Functional approach using Scala:

object MergeCountIntervals {
  def main(args: Array[String]): Unit = {
    println(mergeSegments(Array(Array(1,4), Array(2,3))))
    println(mergeSegments(Array(Array(4,6), Array(1,2))))
    println(mergeSegments(Array(Array(1,4), Array(6,8), Array(2,4), Array(7,9), Array(10,15))))
  }

  def mergeSegments(segments: Array[Array[Int]]): Int = {
    if (segments == null || segments.length == 0) return 0

    val list = List.empty[Array[Int]]
    val merged = segments.sortWith(_(0) < _(0)).foldLeft(list)((seq, s) =>
      if (seq.isEmpty || seq.last(1) < s(0)) {
        seq :+ s
      } else {
        val last = seq.last
        seq.dropRight(1) :+ Array(last(0), Math.max(last(1), s(1)))
      }
    )

    merged.foldLeft(0)((acc, x) => acc + x(1) - x(0))
  }
}
// output:
/*
3
3
11
*/

- guilhebl January 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in Java:

public static void main(String[] args) {
        List<Pair<Integer, Integer>> intervals = new ArrayList<>();
        intervals.add(new Pair<>(1, 4));
        intervals.add(new Pair<>(6, 8));
        intervals.add(new Pair<>(2, 4));
        intervals.add(new Pair<>(7, 9));
        intervals.add(new Pair<>(10, 15));
        System.out.println(totalTime(intervals));
    }

    private static int totalTime(List<Pair<Integer, Integer>> intervals) {
        intervals.sort((left, right) -> left.first.compareTo(right.first));
        if (intervals.isEmpty()) {
            return 0;
        }
        if (intervals.size() == 1) {
            return intervals.get(0).second - intervals.get(0).first;
        }
        int sum = 0;
        Pair<Integer, Integer> temp = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            if (temp.second >= intervals.get(i).first) {
                temp = new Pair<>(temp.first, Math.max(temp.second, intervals.get(i).second));
                continue;
            }
            sum += temp.second - temp.first;
            temp = intervals.get(i);
        }
        sum += temp.second - temp.first;
        return sum;
    }

- duenytz January 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Improved solution in python that I stress test it against my first naive one.

def do_overlap(interval, last):
    imin = interval[0]
    imax = interval[1]
    lmin = last[0]
    lmax = last[1]
    return imax >= lmin and lmax >= imin

def merge(interval, last):
    # This is why a merger needs to be mutable
    last[0] = min(last[0], interval[0])
    last[1] = max(last[1], interval[1])

def sum_intervals(intervals):
    result = 0
    for interval in intervals:
        result += interval[1] - interval[0]
    return result

def coverage(intervals):
    # Sort using interval mins as key
    intervals.sort()
    # Collection of non-overlaping intervals
    # Each merger needs to be mutable
    mergers = None
    for interval in intervals:
        if mergers is None:
            mergers = [list(interval)]
            continue
        # Correctness proof:
        # Show that checking last merger is enough
        last = mergers[-1]
        if do_overlap(interval, last):
            merge(interval, last)
        else:
            mergers.append(list(interval))
    return sum_intervals(mergers)

- baites January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Sample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ArrayList<Interval> input = new ArrayList();
		input.add(new Interval(0,1));
		input.add(new Interval(2,6));
		input.add(new Interval(3,8));
		input.add(new Interval(1,4));
		input.add(new Interval(10,14));
		
		Collections.sort(input,new SortByStart());

		ArrayList<Interval> result = new ArrayList<>();
		
		for(int i = 0 ; i < input.size() ; i++){
			if(result.isEmpty()){
				result.add(new Interval(input.get(i).start,input.get(i).end));
			}else{
				if(input.get(i).start > result.get(result.size()-1).end){
					result.add(new Interval(input.get(i).start,input.get(i).end));
				} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
					result.get(result.size()-1).end = input.get(i).end;
				}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
					// Discard interval
				}
			}
			
		}
		int totalTime = 0;
		for(int i = 0 ; i < result.size() ; i++){
			//System.out.println(result.get(i).start+" "+result.get(i).end);
			totalTime += result.get(i).end - result.get(i).start;
		}
		System.out.println("Total Time Interval "+totalTime);
		
		
	}
	
	
	public static class SortByStart implements Comparator<Interval>{

		@Override
		public int compare(Interval o1, Interval o2) {
			
			return o1.start - o2.start;
		}
		
	}
	
	public static class Interval {
		public Interval(int start, int end){
			this.start = start;
			this.end = end;
		}
		int start;
		int end;
	}

}

- Anonymous January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Sample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ArrayList<Interval> input = new ArrayList();
		input.add(new Interval(0,1));
		input.add(new Interval(2,6));
		input.add(new Interval(3,8));
		input.add(new Interval(1,4));
		input.add(new Interval(10,14));
		
		Collections.sort(input,new SortByStart());

		ArrayList<Interval> result = new ArrayList<>();
		
		for(int i = 0 ; i < input.size() ; i++){
			if(result.isEmpty()){
				result.add(new Interval(input.get(i).start,input.get(i).end));
			}else{
				if(input.get(i).start > result.get(result.size()-1).end){
					result.add(new Interval(input.get(i).start,input.get(i).end));
				} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
					result.get(result.size()-1).end = input.get(i).end;
				}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
					// Discard interval
				}
			}
			
		}
		int totalTime = 0;
		for(int i = 0 ; i < result.size() ; i++){
			//System.out.println(result.get(i).start+" "+result.get(i).end);
			totalTime += result.get(i).end - result.get(i).start;
		}
		System.out.println("Total Time Interval "+totalTime);
		
		
	}
	
	
	public static class SortByStart implements Comparator<Interval>{

		@Override
		public int compare(Interval o1, Interval o2) {
			
			return o1.start - o2.start;
		}
		
	}
	
	public static class Interval {
		public Interval(int start, int end){
			this.start = start;
			this.end = end;
		}
		int start;
		int end;
	}

}

- Kamal January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Sample {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		ArrayList<Interval> input = new ArrayList();
		input.add(new Interval(0,1));
		input.add(new Interval(2,6));
		input.add(new Interval(3,8));
		input.add(new Interval(1,4));
		input.add(new Interval(10,14));
		
		Collections.sort(input,new SortByStart());

		ArrayList<Interval> result = new ArrayList<>();
		
		for(int i = 0 ; i < input.size() ; i++){
			if(result.isEmpty()){
				result.add(new Interval(input.get(i).start,input.get(i).end));
			}else{
				if(input.get(i).start > result.get(result.size()-1).end){
					result.add(new Interval(input.get(i).start,input.get(i).end));
				} else if(input.get(i).start <= result.get(result.size()-1).end && input.get(i).end > result.get(result.size()-1).end){
					result.get(result.size()-1).end = input.get(i).end;
				}else if(input.get(i).start < result.get(result.size()-1).end && input.get(i).end <= result.get(result.size()-1).end){
					// Discard interval
				}
			}
			
		}
		int totalTime = 0;
		for(int i = 0 ; i < result.size() ; i++){
			//System.out.println(result.get(i).start+" "+result.get(i).end);
			totalTime += result.get(i).end - result.get(i).start;
		}
		System.out.println("Total Time Interval "+totalTime);
		
		
	}
	
	
	public static class SortByStart implements Comparator<Interval>{

		@Override
		public int compare(Interval o1, Interval o2) {
			
			return o1.start - o2.start;
		}
		
	}
	
	public static class Interval {
		public Interval(int start, int end){
			this.start = start;
			this.end = end;
		}
		int start;
		int end;
	}

}

- kamal.hasanjk January 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int calc(int[][] intervals) {
		TreeMap<Integer, Integer> map = new TreeMap<>();

		for (int[] is : intervals) {
			if (!map.containsKey(is[0]) || map.get(is[0]) < is[0])
				map.put(is[0], is[1]);
		}

		List<Object> keyList = Arrays.asList(map.keySet().toArray());

		int start = (Integer) keyList.get(0);
		int end = map.get(start);
		int diff = 0;
		
		for (int i = 1; i < keyList.size(); i++) {
			int c = (Integer) keyList.get(i);
			int d = map.get(c);

			if (end < c)
				diff += c - end;

			end = Math.max(end, d);
		}
		return end - start - diff;
	}

- genco January 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My rather specific solution. I need more practice, but went with the simple to construct/understand brute force approach.

int timeElapsed(int[][] timeIntervals)
    {    
    	int elapsedTime = 0;
    	int tempEnd = 0;
    	int tempBegin = 0;
    	
    	// Sort Array by start time
    	Arrays.sort(timeIntervals,Comparator.comparing((int [] arr) -> arr[0]));
    	
    	for(int i  = 0; i <  timeIntervals.length; i++)
    	{
    		tempBegin = timeIntervals[i][0];
    		for(int j = i+1; j < timeIntervals.length; j++)
    		{
    			if(timeIntervals[i][1] <= timeIntervals[j][1] 
    					&& timeIntervals[i][1] >= timeIntervals[j][0])
    			{
    				i = j;
    				break;
    			}
    		}
    		
    		if(tempEnd < timeIntervals[i][1])
    		{
	    		tempEnd = timeIntervals[i][1];
	    		elapsedTime += tempEnd - tempBegin;
    		}
    	}
    	
    	System.out.println("Time elapsed " + elapsedTime);
		return elapsedTime;
    }

- rook January 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I used this task to finally start practicing Python.
At least amount of lines of code is small enough to make me think that solution is quite simple :-)
{pairs=[(1,4),(6,8),(2,4),(7,9),(10,15)]
hours = set()
for first,last in pairs:
i = first
while i<=last:
print(i)
hours.add(i)
i+=1
print("total hours=",len(hours))}

- MSiam January 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my first code in Python. At least I like simplicity and because of lack of practice in Python I have very small idea on efficiency of it.

pairs=[(1,4),(6,8),(2,4),(7,9),(10,15)]
hours = set()
for first,last in pairs:
	i = first
	while i<=last:	
		print(i)
		hours.add(i)
		i+=1
print("total hours=",len(hours))

- MKisunko January 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can handle real time interval addition

//Reak time time interval Parsing.
using System;
using System.Collections.Generic;

public class Solution
{
    public enum Stat
    {
        BeginOverlap,
        EndOverLap,
        InternalEnclosedOverlap,
        ExternalEnclosedOverlap,
        ContinuousMerge,
        NoOverlap
    }
    public class Interval
    {
        public int Start;
        public int End;

        public Interval(int s, int e)
        {
            Start = s;
            End = e;
        }

        public Stat IsOverlap(Interval inte)
        {
            if (inte.Start < Start && inte.End > End)
                return Stat.ExternalEnclosedOverlap;
            else if (inte.Start > Start && inte.End < End && inte.Start < End)
                return Stat.InternalEnclosedOverlap;
            else if (inte.Start > Start && inte.End > End && inte.Start < End)
                return Stat.EndOverLap;
            else if (inte.Start < Start && inte.End < End && inte.End > Start)
                return Stat.BeginOverlap;
            else if (inte.End == Start || inte.Start == End)
                return Stat.ContinuousMerge;
            else
                return Stat.NoOverlap;
        }
    }

    public class IntervalHandler
    {
        public List<Interval> iList;
        public int Length;

        public IntervalHandler()
        {
            iList = new List<Interval>();
            Length = 0;
        }

        public void AddInterval(int s, int e)
        {
            if (s > e)
                return;

            if(iList.Count.Equals(0))
            {
                iList.Add(new Interval(s, e));
                return;
            }

            for(int i = 0; i<iList.Count; i++)
            {
                switch(iList[i].IsOverlap(new Interval(s, e)))
                {
                    case Stat.BeginOverlap:
                        iList[i].Start = s;
                        return;
                    case Stat.EndOverLap:
                        HandleEndOverLap(new Interval(s, e));
                        return;
                    case Stat.InternalEnclosedOverlap:
                        return;
                    case Stat.ExternalEnclosedOverlap:
                        HandleExternalEnclosedOverLap(new Interval(s, e));
                        return;
                    case Stat.ContinuousMerge:
                        HandleContinuousMerge(i,new Interval(s, e));
                        return;
                }
            }
            AddNewInterval(new Interval(s, e));
        }

        private void HandleContinuousMerge(int index, Interval interval)
        {
            iList[index].Start = Math.Min(iList[index].Start, interval.Start);
            iList[index].End = Math.Max(iList[index].End, interval.End);
        }

        private void AddNewInterval(Interval interval)
        {
            int i = 0;
            while(i < iList.Count && iList[i].Start > interval.Start)
            {
                i++;
            }
            iList.Insert(i, interval);
        }

        private void HandleExternalEnclosedOverLap(Interval interval)
        {
            //for external enclosed overlap : interval is so fucking big the first interval cant handle shit 
            //so go over all the intervals till the new intervals end is matched and merge all the passed intervals
            int i = 0;
            while (iList.Count > 0 && interval.End > iList[i].End && (interval.Start < iList[i].End))
            {
                if (interval.Start > iList[i].Start)
                    interval.Start = iList[i].Start;
                iList.RemoveAt(i);                
            }
            iList.Insert(0, interval);            
        }

        private void HandleEndOverLap(Interval interval)
        {
            //for End overlap check for other intervals after the first interval if it overlaps them then merge all of them into one big long interval otherwise merge the first and new interval
            int i = 0;
            
            while(iList.Count>0 && interval.End > iList[i].End)
            {
                iList.RemoveAt(i);
            }
            if (iList.Count > 0 && iList[i].Start < interval.End)
                iList.RemoveAt(i);
            iList.Insert(0, interval);            
        }        

        public void PrintIntervals()
        {
            foreach(var interval in iList)
            {
                Console.WriteLine(interval.Start + "   " + interval.End);
            }
            Console.WriteLine("-------------------------------");
        }
    }
    
    public static void Main()
    {
        IntervalHandler handler = new IntervalHandler();

        handler.AddInterval(2,4);
        handler.AddInterval(1, 2);
        handler.AddInterval(4,6);
        //handler.AddInterval();

        handler.PrintIntervals();

        handler.AddInterval(3,5);

        handler.PrintIntervals();

        Console.Read();
    }
}

- morpheus January 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class IntervalsTotalTime{

	public static class Interval{
		int start;
		int end;
		Interval(int s, int e){
			this.start=s;
			this.end=e;
		}
	}
	
	public static int solution(List<Interval> list) {
		
		list.sort((i1, i2) -> (i1.start - i2.start));

		int start = list.get(0).start;
		int end = list.get(0).end;
		int gap = 0;
		
		for(int i=1; i<list.size(); i++) {
			Interval interval = list.get(i);
			if(interval.start <= end)
				end = Math.max(end, interval.end);
			else if(interval.start > end) {
				gap += interval.start - end;
				end = interval.end;
			}
		}
		
		return end - start - gap;
	}
	
	public static void main(String[] args) {
		List<Interval> list = new ArrayList();
		list.add(new Interval(1,4));
		list.add(new Interval(6,8));
		list.add(new Interval(2,4));
		list.add(new Interval(7,9));
		list.add(new Interval(10,15));
		System.out.println(solution(list));
		
	}
}

- Shaum January 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Facebook1 {

    Set<Integer> arraySet = new HashSet<>();

    public static void main(String[] args) {

        Facebook1 fb1 = new Facebook1();
        fb1.totalInterval( new int[][]{ {1, 4}, {6, 8}, {2, 4}, {7, 9}, {10, 15} } );
    }

    void totalInterval(int[][] input){

        int totalInter = 0;

        for (int[] inputPair : input) {

            int first = inputPair[0];
            int second = inputPair[1];

            for (int i = first; i < second; i++) {
                arraySet.add(i);
            }

        }

        System.out.println(arraySet);

//        for (int i = 0; i < arraySet.size(); i ++) {
//            if (arraySet.get(i) == 1)
//                totalInter = totalInter + 1;
//        }

        System.out.println(arraySet.size());
    }
}

- deep.kulshreshtha January 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int FindInterval(List<Tuple<int, int>> input)
{
if (input == null || !input.Any())
{
return 0;
}

input.Sort();

var interval = 0;

var array = new List<int>();

foreach (var item in input)
{
if (item.Item1 > item.Item2)
{
continue;
}

if (array.Any())
{
if (item.Item1 > array.Min() && item.Item2 < array.Max())
{
continue;
}

if (item.Item1 >= array.Min() && item.Item1 <= array.Max() && item.Item2 > array.Max())
{
interval += item.Item1 - array.Max();
}
else if (item.Item1 < array.Min() && item.Item2 >= array.Min() && item.Item2 <= array.Max())
{
interval += array.Min() - item.Item1;
}
else if (item.Item1 <= array.Min() && item.Item2 >= array.Max())
{
interval = item.Item2 - item.Item1;
}
else
{
interval += item.Item2 - item.Item1;
}
}
else
{
interval += item.Item2 - item.Item1;
}

array.Add(item.Item1);
array.Add(item.Item2);

array.Sort();
}

return interval;
}

- Elena January 29, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- aonecoding4 January 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Facebook
 * <p>
 * Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
 * For example:
 * input = [(1,4), (2,3)]
 * return 3
 * input = [(4,6), (1,2)]
 * return 3
 * input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
 * return 11
 */
public class Interval {
    static class Pair {
        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    List<Pair> list = new ArrayList<>();

    void addAll(Pair[] pairs) {
        Arrays.stream(pairs).forEach(this::add);
    }

    void add(Pair p2) {
        int min = p2.a, max = p2.b;
        for (int i = 0; i < list.size(); i++) {
            Pair p1 = list.get(i);
            if (!(max < p1.a || min > p1.b)) {
                min = Math.min(p1.a, min);
                max = Math.max(p1.b, max);
                list.remove(i);
            }
        }
        list.add(new Pair(min, max));
    }

    int getSum() {
        return list.stream().mapToInt(p -> p.b - p.a).sum();
    }

    void clear() {
        list.clear();
    }

    public static void main(String[] args) {
        Interval interval = new Interval();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
        System.out.println(interval.getSum());
        interval.clear();

//        { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
        interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
        System.out.println(interval.getSum());
        interval.clear();
    }

}

- easy February 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Facebook
 * <p>
 * Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
 * For example:
 * input = [(1,4), (2,3)]
 * return 3
 * input = [(4,6), (1,2)]
 * return 3
 * input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
 * return 11
 */
public class Interval {
    static class Pair {
        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    List<Pair> list = new ArrayList<>();

    void addAll(Pair[] pairs) {
        Arrays.stream(pairs).forEach(this::add);
    }

    void add(Pair p2) {
        int min = p2.a, max = p2.b;
        for (int i = 0; i < list.size(); i++) {
            Pair p1 = list.get(i);
            if (!(max < p1.a || min > p1.b)) {
                min = Math.min(p1.a, min);
                max = Math.max(p1.b, max);
                list.remove(i);
            }
        }
        list.add(new Pair(min, max));
    }

    int getSum() {
        return list.stream().mapToInt(p -> p.b - p.a).sum();
    }

    void clear() {
        list.clear();
    }

    public static void main(String[] args) {
        Interval interval = new Interval();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
        System.out.println(interval.getSum());
        interval.clear();

//        { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
        interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
        System.out.println(interval.getSum());
        interval.clear();
    }

}

- easy February 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Facebook
 * <p>
 * Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
 * For example:
 * input = [(1,4), (2,3)]
 * return 3
 * input = [(4,6), (1,2)]
 * return 3
 * input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
 * return 11
 */
public class Interval {
    static class Pair {
        int a, b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    List<Pair> list = new ArrayList<>();

    void addAll(Pair[] pairs) {
        Arrays.stream(pairs).forEach(this::add);
    }

    void add(Pair p2) {
        int min = p2.a, max = p2.b;
        for (int i = 0; i < list.size(); i++) {
            Pair p1 = list.get(i);
            if (!(max < p1.a || min > p1.b)) {
                min = Math.min(p1.a, min);
                max = Math.max(p1.b, max);
                list.remove(i);
            }
        }
        list.add(new Pair(min, max));
    }

    int getSum() {
        return list.stream().mapToInt(p -> p.b - p.a).sum();
    }

    void clear() {
        list.clear();
    }

    public static void main(String[] args) {
        Interval interval = new Interval();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)});
        System.out.println(interval.getSum());
        interval.clear();

        interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)});
        System.out.println(interval.getSum());
        interval.clear();

//        { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}}
        interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)});
        System.out.println(interval.getSum());
        interval.clear();
    }

}

- easy February 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ {{{ import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Facebook * <p> * Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals. * For example: * input = [(1,4), (2,3)] * return 3 * input = [(4,6), (1,2)] * return 3 * input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}} * return 11 */ public class Interval { static class Pair { int a, b; Pair(int a, int b) { this.a = a; this.b = b; } } List<Pair> list = new ArrayList<>(); void addAll(Pair[] pairs) { Arrays.stream(pairs).forEach(this::add); } void add(Pair p2) { int min = p2.a, max = p2.b; for (int i = 0; i < list.size(); i++) { Pair p1 = list.get(i); if (!(max < p1.a || min > p1.b)) { min = Math.min(p1.a, min); max = Math.max(p1.b, max); list.remove(i); } } list.add(new Pair(min, max)); } int getSum() { return list.stream().mapToInt(p -> p.b - p.a).sum(); } void clear() { list.clear(); } public static void main(String[] args) { Interval interval = new Interval(); interval.addAll(new Pair[]{new Pair(1, 4), new Pair(2, 3)}); System.out.println(interval.getSum()); interval.clear(); interval.addAll(new Pair[]{new Pair(4, 6), new Pair(1, 2)}); System.out.println(interval.getSum()); interval.clear(); interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15)}); System.out.println(interval.getSum()); interval.clear(); interval.addAll(new Pair[]{new Pair(1, 4), new Pair(6, 8), new Pair(2, 4), new Pair(7, 9), new Pair(10, 15), new Pair(4,6)}); System.out.println(interval.getSum()); interval.clear(); interval.addAll(new Pair[]{new Pair(1, 10), new Pair(5, 8), new Pair(7, 9)}); System.out.println(interval.getSum()); interval.clear(); // { { 3, 7 }, { 4, 5 }, {10, 20}, {8, 15}} interval.addAll(new Pair[]{new Pair(3, 7), new Pair(4,5), new Pair(10, 20), new Pair(8, 15)}); System.out.println(interval.getSum()); interval.clear(); } } }}} }}} - Anonymous February 08, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include <vector>
#include <map>

int returnHours(vector<vector<int> intervals)
{
  int ans=0;
  map<int,int>  freq;
  int sz = intervals.size();
  for (int ind=0;ind<sz;++ind)
  {
    for (int start=intervals[ind][0];start<intervals[ind][1];++start)
    {
      if(freq[start]==0)
      {
        freq[start]=1;
        ++ans;
      }
    }
  return ans;
}

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

int get_time_covered( int[][] input; int size){
  
  int save = new int[size][2];
  int save_size = 0, time_covered = 0;

  save[0][0] = input[0][0]; 
  save[0][1] = input[0][1];  
  save_size = 1;
  time_covered = save[0][1] - save[0][0]

  for( i = 1; i < size; i++) {      
    start  = input[i][0];           
    end    = input[i][1];           
    p = -1;
    new_start = start;
    
    for( j = 0; j < save_size; j++) {  
      if( (start > save[j][0] && start < save[j][1]) && save[j][1] > new_start){
        new_start = save[j][0];    //8
        if( new_start >= end) continue;
      
        p = j;
      }
    }
  
    time_covered = time_covered + (end - new_start);
  
    if( p > -1){
      save[p][1] = new_start;
      continue;
    }
  
    save[save_size][0] = new_start; 
    save[save_size][1] = end; 
  
    save_size++;
  }
  
  return time_covered;
}

- engineer.udays February 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inspired on aonecoding4 I have implemented a Python solution which I find easier to read:

def calcSegments(segments):
    segments = sorted(segments, key=lambda segment: segment[0])
    last = 0
    r = 0
    for seg in segments:
        l1 = max(last,seg[1])
        diff = l1 - max(last, seg[0])
        if diff > 0:
            r+=diff
        last = l1
    return r

- juangirini February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Instead of sorting, you could use an array of 24 to store the intervals in order, each start index storing the end index.

function getTotalTime(times) {
  const intervals = Array(24).fill(0)

  for (let t of times) {
    let [start, end] = t
    if (intervals[start] &&
      end > intervals[start]) {
      intervals[start] = end
    }
    else intervals[start] = end
  }

  // second pass, counting the intervals
  let i = 0
  let total = 0
  let count = 0
  let end = 0
  while (i < intervals.length) {
    if (intervals[i] && intervals[i] > end) {
      count += (intervals[i] - i)
      // amotize
      if (i < end) count -= (end - i)
      end = intervals[i]
    }
    if (i == end) {
      total += count
      count = 0
    }
    i += 1
  }
  return total
}

- 0x February 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from operator import sub


def calculate_intervals(array):
    return sum(abs(sub(*t)) for t in array)

- B0B501337 March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from operator import sub


def calculate_intervals(array):
    return sum(abs(sub(*t)) for t in array)

- Anonymous March 01, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done without sorting in O(n) by using a Set of hours.

int getCoverage(int[][] segments) {
        Set<Integer> hours = new HashSet<Integer>();
        for (int[] segment : segments) {
            for (int i=segment[0]; i<segment[1]; i++)
                hours.add(i);
        }
        return hours.size(); 
    }

- Yoad March 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Without using  arrays.sort and comparator
//using quick sort
static void calcIntervals(){
		int[][]segments = {{1,4}, {13,18}, {5,8}, {7,9}, {10, 15}};
		int pivot=segments.length/2;
		swapElement(segments,pivot, segments.length-1);
		sort( segments, 0, segments.length-1);
		printArrays(segments);
		int lastVal=0;
		int totalHrs=0;
		for(int i=0; i< segments.length;i++){
			totalHrs += Math.max(segments[i][1],lastVal) - Math.max(segments[i][0],lastVal);
			lastVal= Math.max(segments[i][1],lastVal);
		}
		System.out.println("Result="+ totalHrs);
	}
	static void swapElement(int [][] segments, int a,int  b){
		int[] temp=segments	[a];
		segments[a]= segments[b];
		segments[b]= temp;
	}
	static void sort(int [][] segments, int start,int  end){
		int lastElement= end -1;
		if(lastElement> start){
			while (start < lastElement){
				if(segments[start][0]> segments[end][0]){
					swapElement(segments, start, lastElement);
					lastElement--;
				}else{
					start++;
				}
			}	
			if(segments[start][0]> segments[end][0]){
				swapElement(segments, start, end);
				sort(segments,0,start );
				sort(segments,start+1,end );
			}
		}
	}

- Anonymous March 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def total_time(times):
    # build a set of all the individual hours, count them.
    segments = {}
    for start, finish in times:
        segments.update([(x, x+1) for x in range(start, finish)])
    return len(segments)

- kremer March 21, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It looks like many of these 'solutions' are wrong. Do they print test cases?

package intervalCover;

import java.util.Arrays;
import java.util.Comparator;

class Interval {
	public int a;
	public int b;

	public Interval(int a, int b) {
		this.a = a;
		this.b = b;
	}
}

class IntervalComp implements Comparator<Interval> {
	@Override
	public int compare(Interval o1, Interval o2) {
		int l = o1.a - o2.a;
		int r = o2.b - o2.b;
		return l == 0 ? r : l;
	}
}

public class IntervalCover {

	private static Interval[] p1;
	private static Interval[] p2;
	private static Interval[] p3;
	private static Interval[] p4;

	public static void main(String[] args) {
		p1 = new Interval[2];
		p1[0] = new Interval(1, 4);
		p1[1] = new Interval(2, 3);

		p2 = new Interval[2];
		p2[0] = new Interval(4, 6);
		p2[1] = new Interval(1, 2);

		p3 = new Interval[5];
		p3[0] = new Interval(1, 4);
		p3[1] = new Interval(6, 8);
		p3[2] = new Interval(2, 4);
		p3[3] = new Interval(7, 9);
		p3[4] = new Interval(10, 15);

		p4 = new Interval[4];
		p4[0] = new Interval(1, 4);
		p4[1] = new Interval(6, 8);
		p4[2] = new Interval(8, 10);
		p4[3] = new Interval(10, 15);

		System.out.println("one  = " + ic(p1) + " correct " + 3);
		System.out.println("two  = " + ic(p2) + " correct " + 3);
		System.out.println("three = " + ic(p3) + " correct " + 11);
		System.out.println("four  = " + ic(p4) + " correct " + 12);
	}

	public static int ic(Interval[] intervals) {
		Arrays.sort(intervals, new IntervalComp());
		int minval = 0;
		int sum = 0;
		int min = minval;
		int max = minval;
		int total = 0;
		for (Interval i : intervals) {
			total = total + (i.b - i.a);
			// is there a gap between intervals?
			if (i.a >= max) {
				if (min == minval) {
					min = i.a;
					if (i.b > max)
						max = i.b;
					//System.out.println("FIRST (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
				} else if (max > min) {
					sum = sum + (max - min);
					//System.out.println("Gap (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
					min = i.a;
					max = i.b;
				}
			} else { // i.a < max
				if (min == minval)
					min = i.a;
				if (i.b > max)
					max = i.b;
				//System.out.println("Extend (" + i.a + ", " + i.b + ") " + min + "/" + max + " " + sum);
			}
		}
		if (max > min)
			sum = sum + (max - min);
		// System.out.println("Total = " + total);
		return sum;
	}
}

- w7cook May 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def merge(I1,I2):
lp,rp = I1
l,r = I2
# print(lp,rp,l,r)
# complete intersect
if l <= rp and r <= rp:
return [(lp,rp)]
#partial intersect
elif l <= rp and r > rp:
return [(lp,r)]
#no intersection
else:
return []



def intervalTotalRange(arr):

merged = []

for i in range(1,len(arr)):
prev = i -1
curr = i
m = merge(arr[prev],arr[curr])
if len(m) == 1:
merged = arr[0:prev] + m + arr[curr+1:]
return intervalTotalRange(merged)

print(arr)





intervalTotalRange([(1,4),(2,3)])
intervalTotalRange([[1,10],[5,8],[7,9]])
inp = sorted([(1,4), (6,8), (2,4), (7,9),(10,15)])
# print (inp)
intervalTotalRange(inp)

- varun May 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

function interval(start,stop){
  return {"start": start, "stop": stop};
}

function calculate(intervals){
  var arr = [];
  intervals.forEach(i => {
    for(var tmp = i["start"]; tmp < i["stop"]; tmp++){
      arr[tmp] = 1;  
    }
  })
 console.log(arr.filter(i => i === 1).length); 
}

var intervals = [interval(1,4), 
                 interval(6,8),
                 interval(2,4),
                 interval(7,9),
                 interval(10,15)
                ]

calculate(intervals);

- Prasanna July 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals. 
// For example:
// input = [(1, 4), (2, 3)]
// return 3
// input = [(4, 6), (1, 2)]
// return 3
// input = {{ 1, 4 }, { 6, 8 }, { 2, 4 }, { 7, 9 }, { 10, 15 }}
// return 11

function findStartLaterThan(sortedIntervals, value, startPos, endPos) {
  var minIndex = startPos || 0
  var maxIndex = endPos || sortedIntervals.length

  while (maxIndex - minIndex > 0) {
    var index = Math.floor((minIndex + maxIndex) / 2)
    //    console.debug('findStartLaterThan index=' + index)

    if (sortedIntervals[index].start <= value && (!sortedIntervals[index + 1] || sortedIntervals[index + 1].start > value)) {
      return index
    } else if (sortedIntervals[index].start > value) {
      maxIndex = index
    } else {
      minIndex = index
    }
  }
}

function insertInterval(sortedIntervals, interval) {

  var index = findStartLaterThan(sortedIntervals, interval.start)

  var endIndex = findStartLaterThan(sortedIntervals, interval.end, index)

  if (sortedIntervals.length == 0) {
    sortedIntervals.push(interval)
    return
  }

  if (sortedIntervals[index].end >= interval.start) {
    if (sortedIntervals[endIndex].end >= interval.end) {
      if (index == endIndex) {
        // the new interval is dropped
      } else {
        // index ... endIndex is merged into one, drop the new interval
        sortedIntervals[index].end = sortedIntervals[endIndex].end
        sortedIntervals.splice(index + 1, endIndex - index)
      }
    } else {
      if (index == endIndex) {
        sortedIntervals[index].end = interval.end
      }
      else {
        sortedIntervals[index].end = interval.end
        sortedIntervals.splice(index + 1, endIndex - index)
      }
    }
  } else {
    if (sortedIntervals[endIndex].end >= interval.end) {
      if (index == endIndex) {
        // Not possible
      } else {
        // index ... endIndex is merged into one, drop the new interval
        sortedIntervals[endIndex].start = interval.start
        sortedIntervals.splice(index + 1, endIndex - index - 1)
      }
    } else {
      if (index == endIndex) {
        sortedIntervals.splice(index + 1, 0, interval)
      }
      else {
        sortedIntervals[endIndex].start = interval.start
        sortedIntervals[endIndex].end = interval.end
        sortedIntervals.splice(index + 1, endIndex - index - 1)
      }
    }
  }
}

function count(randomIntervals) {
  var sortedIntervals = [{ start: 0, end: 0 }]

  for (var interval of randomIntervals) {
    insertInterval(sortedIntervals, { start: interval[0], end: interval[1], })
  }

  var sum = 0
  for (var interval of sortedIntervals) {
    sum += interval.end - interval.start
  }

  return sum
}

console.log(count([[1, 4], [2, 3]]))
console.log(count([[4, 6], [1, 2]]))
console.log(count([[1, 4], [6, 8], [2, 4], [7, 9], [10, 15]]))

- sheng August 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {

  int low; int high; Node left; Node right;
  Node(int low, int high) {
    this.low = low;
    this.high = high;
    this.left=null;
    this.right=null;
  }
  static Node insert(int low, int high, Node root) {
    if (root == null)
      return new Node(low, high);
    // lies within root interval, do nothing
    if (root.low <= low && root.high>=high)
      return root;
    // lies to right, no intersection
    if (root.high <= low) {
      root.left = insert(low, high, root.left);
      return root;
    }
    // lies to left, no intersection
    if (root.low >= high) {
      root.right = insert(low, high, root.right);
      return root;
    }
    // intersect with left boundary
    if (root.low > low) {
      root.left = insert(low, root.low, root.left);
    }
    // intersect with right boundary
    if (root.high < high) {
      root.right = insert(root.high, high, root.right);
    }
    return root;
  }

  static int count(Node root) {
      if (root == null) return 0;
      return root.high - root.low + count(root.left) + count(root.right);
  }

  public static void main(String args[]){
      Node root = null;
      root = insert(1,4, root);
      root = insert(2,10, root);
      root = insert(1,7, root);
      System.out.println(count(root));
  }
}

- UK October 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {

  int low; int high; Node left; Node right;
  Node(int low, int high) {
    this.low = low;
    this.high = high;
    this.left=null;
    this.right=null;
  }
  static Node insert(int low, int high, Node root) {
    if (root == null)
      return new Node(low, high);
    // lies within root interval, do nothing
    if (root.low <= low && root.high>=high)
      return root;
    // lies to right, no intersection
    if (root.high <= low) {
      root.left = insert(low, high, root.left);
      return root;
    }
    // lies to left, no intersection
    if (root.low >= high) {
      root.right = insert(low, high, root.right);
      return root;
    }
    // intersect with left boundary
    if (root.low > low) {
      root.left = insert(low, root.low, root.left);
    }
    // intersect with right boundary
    if (root.high < high) {
      root.right = insert(root.high, high, root.right);
    }
    return root;
  }

  static int count(Node root) {
      if (root == null) return 0;
      return root.high - root.low + count(root.left) + count(root.right);
  }

  public static void main(String args[]){
      Node root = null;
      root = insert(1,4, root);
      root = insert(2,10, root);
      root = insert(1,7, root);
      System.out.println(count(root));
  }
}

- Kiran T October 20, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Text;

namespace Facebook
{
    public class TimeInterval
    {
        public void CoveredTime()
        {
            List<int[]> list = new List<int[]>()
            {
                new int[] {1,6},
                new int[] {2,9},
                new int[] {3,5}
            };

           Console.WriteLine(CoveredTime(list));
           Console.ReadLine();
        }
        public int CoveredTime(List<int[]> list)
        {
            if (list == null || list.Count == 0) return 0;
            int coveredTime = list[0][1] - list[0][0];
            List<int[]> coveredList = new List<int[]>();
            coveredList.Add(list[0]);
            for(int i=1; i<list.Count;i++)
            {
                coveredTime += GetCoveredTime(coveredList, list[i]);
            }

            return coveredTime;
        }

        private int GetCoveredTime(List<int[]> list, int[] interval)
        {
            int covered = 0;
         
            foreach(int[] period in list)
            {
                if(interval[0] < period[0] && interval[1] <=period[0])
                {
                    if (interval[1] == period[0])
                    {
                        period[0] = interval[0];
                    }

                    covered = interval[1] - interval[0];
                    break;
                }
                else if(interval[0] >= period[1])
                {
                    if(interval[0] == period[1])
                    {
                        period[1] = interval[1];
                    }
                    covered = interval[1] - interval[0];
                    break;
                }
                else if(interval[0] >= period[0] && interval[0] < period[1] && interval[1] > period[1])
                {
                    covered = interval[1] - period[1];
                    period[1] = interval[1];
                    break;
                }
            }

            return covered;
        }
    }
}

- p.rubanantony June 14, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindTotalTimeIntervals {
	public static void main(String[] args) {
		List<Integer[]> input = new ArrayList<>();
		input.add(new Integer[]{1,4});
		input.add(new Integer[]{6,8});
		input.add(new Integer[]{2,4});
		input.add(new Integer[]{7,9});
		input.add(new Integer[]{10,15});

		Set<String> set = new HashSet<>();
		input.forEach(array -> {
			int start = array[0];
			int end = array[1];
			for(int i = start; i < end; i++) {
				String key = i + "-" + (i + 1);
				set.add(key);
			}
		});
		System.out.println(set.size());
	}
}

- esoner.sezgin September 16, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <set>
#include <vector>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it_up, it_low;
  std::vector<std::pair<int,int>> freq;
  
  std::pair<int, int> p1 = { 1, 4 };
  std::pair<int, int> p2 = { 6, 8 };
  std::pair<int, int> p3 = { 2, 4 };
  std::pair<int, int> p4 = { 7, 9 };
  std::pair<int, int> p5 = { 10, 15 };
  
  freq.push_back(p1);
  freq.push_back(p2);
  freq.push_back(p3);
  freq.push_back(p4);
  freq.push_back(p5);
  
  for (auto it = freq.begin(); it != freq.end(); it++) {
      
      it_up = myset.upper_bound(it->first);
      it_low = myset.lower_bound(it->first);
      if (it_up == myset.end() || it_low == myset.begin()) {
        myset.insert(it->first);
      }
      
      it_up = myset.upper_bound(it->second);
      if (it_up == myset.end()) {
        myset.insert(it->second);
        
        it_low = myset.lower_bound(it->second);
        auto nx = std::prev(it_low, 1);
          if (*nx != it->first) {
              myset.erase(nx);
          }
      }
  }
  
  int sum = 0;
  auto it = myset.begin();
  for (int i = 0; i < myset.size() - 1; i+=2) {
    auto nx = std::next(it, 1);
    sum += abs(*nx - *(it));
    it = std::next(it, 2);
  }
  
  std::cout << sum << '\n';

  return 0;
}

- Arturo October 09, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <set>
#include <vector>

int main ()
{
  std::set<int> myset;
  std::set<int>::iterator it_up, it_low;
  std::vector<std::pair<int,int>> freq;
  
  std::pair<int, int> p1 = { 1, 4 };
  std::pair<int, int> p2 = { 6, 8 };
  std::pair<int, int> p3 = { 2, 4 };
  std::pair<int, int> p4 = { 7, 9 };
  std::pair<int, int> p5 = { 10, 15 };
  
  freq.push_back(p1);
  freq.push_back(p2);
  freq.push_back(p3);
  freq.push_back(p4);
  freq.push_back(p5);
  
  for (auto it = freq.begin(); it != freq.end(); it++) {
      
      it_up = myset.upper_bound(it->first);
      it_low = myset.lower_bound(it->first);
      if (it_up == myset.end() || it_low == myset.begin()) {
        myset.insert(it->first);
      }
      
      it_up = myset.upper_bound(it->second);
      if (it_up == myset.end()) {
        myset.insert(it->second);
        
        it_low = myset.lower_bound(it->second);
        auto nx = std::prev(it_low, 1);
          if (*nx != it->first) {
              myset.erase(nx);
          }
      }
  }
  
  int sum = 0;
  auto it = myset.begin();
  for (int i = 0; i < myset.size() - 1; i+=2) {
    auto nx = std::next(it, 1);
    sum += abs(*nx - *(it));
    it = std::next(it, 2);
  }
  
  std::cout << sum << '\n';

  return 0;
}

- arturocu81 October 09, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

With some bit operation

public class TimeSlot {
	
	public static int findUsedTimeSlots(int[][] times) {
		if(times == null || times[0].length!= 2)
			return -1;
		int usedTime =0;
		
		for(int i = 0; i < times.length; i++) {
			for(int j = times[i][0]; j < times[i][1]; j++) {
				usedTime |= 1 << j;
			}
		}
		
		int count = 0;
		while(usedTime != 0) {
			usedTime = usedTime & (usedTime -1);
			count++;
		}
		
		return count;
	}
	
	public static void main(String[] args) {
		int[][] times = new int[][]{{1,4}, {6,8}, {2,4}, {7,9}, {10,15}};
		
		System.out.println(findUsedTimeSlots(times));
	}

}

- Endi December 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int time_covered(const std::vector<std::pair<int, int>>& intervals) {
	if (intervals.empty()) {
		return 0;
	}
	auto sorted_intervals = intervals;
	std::sort(sorted_intervals.begin(), sorted_intervals.end(), [](const std::pair<int, int>& pa, const std::pair<int, int>& pb) { return pa.first < pb.first;  });
	int sum = 0;
	int start = sorted_intervals[0].first;
	int end = sorted_intervals[0].second;
	for (int i = 1; i < sorted_intervals.size(); ++i) {
		if (sorted_intervals[i].first <= end) {
			end = std::max(sorted_intervals[i].second, end);
		}
		else {
			sum += end - start;
			start = sorted_intervals[i].first;
			end = sorted_intervals[i].second;
		}
	}
	sum += end - start;
	return sum;
}

- Omri.Bashari May 05, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def flattern_sum(intervals):
    result = [0] * 24
    for i in intervals:
        start_time, end_time = i
        for time_interval in range(start_time, end_time, 1): 
                result[time_interval-1] = 1
    return sum(result)

And some tests

def tests():
    input0 = [(1,10),(5,8),(7,9)]
    temp_result = flattern_sum(input0)
    if temp_result != 9: 
        print(f"test failed {temp_result}")
    else: 
        print("Test1: Ok")

    input1 = [(1,4), (2,3)]
    temp_result = flattern_sum(input1)
    if temp_result != 3: 
        print(f"test failed {temp_result}")
    else: 
        print("Test1: Ok")

    input2 = [(4,6), (1,2)]
    temp_result = flattern_sum(input2)
    if temp_result != 3: 
        print(f"test failed {temp_result}")
    else: 
        print("Test1: Ok")

    input3 = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
    temp_result = flattern_sum(input3)
    if temp_result != 11: 
        print(f"test failed {temp_result}")
    else: 
        print("Test1: Ok")


if __name__ == "__main__":
    tests()

- yp November 24, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int solve(int[][] intervals){
Arrays.sort(intervals, (a,b)->a[0]-b[0]);
PriorityQueue<Integer> queue = new PriorityQueue<>();
Deque<Integer> deque = new ArrayDeque<>();
queue.add(intervals[0][1]);
deque.add(intervals[0][0]);
int count = 0;
int start = 0;
int end = 0;
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>queue.peek()){
end = 0;
while(!queue.isEmpty() && queue.peek()<intervals[i][0]){
end = queue.remove();
}
start = deque.getFirst();
deque.clear();
count += end-start;
}
queue.add(intervals[i][1]);
deque.add(intervals[i][0]);
}
start = deque.getFirst();
while(!queue.isEmpty()){
end = queue.remove();
}
count += end-start;
return count;
}

- Akash Deep April 25, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[][] solve(int[][] intervals){
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);
        int start = intervals[0][0];
        int end = intervals[0][1];
        List<int[]> list = new ArrayList<>();
        for(int i=1;i<intervals.length;i++){
            int currStart = intervals[i][0];
            int currEnd = intervals[i][1];
            if(currStart<=end && currEnd>=end){
                end = currEnd;
            }else if(currStart>end){
                list.add(new int[]{start,end});
                start = currStart;
                end = currEnd;
            }
        }
        list.add(new int[]{start,end});
        int[][] res = new int[list.size()][2];
        for(int i=0;i<res.length;i++){
            res[i] = list.get(i);
        }
        return res;
    }

- Akash Deep April 26, 2022 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

python code

pairs=[(1,4),(6,8),(2,4),(7,9),(10,15)]

hours = 0
for i in pairs:
    hours +=i[1]-i[0]
print(hours)

- pro100Istomin1988 April 05, 2019 | Flag Reply


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