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

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

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

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

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

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.

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

([[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?

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

}

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]):

Too naive?

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

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<>();
start = current.get(0);
end = current.get(1);
}
}

ArrayList<Integer> temp = new ArrayList<>();

return result;

}``````

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

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<>();
start = current.get(0);
end = current.get(1);
}
}

ArrayList<Integer> temp = new ArrayList<>();

return result;

}``````

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

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<>();
start = current.get(0);
end = current.get(1);
}
}

ArrayList<Integer> temp = new ArrayList<>();

return result;

}``````

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

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

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

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

Collections.sort(input,new SortByStart());

ArrayList<Interval> result = new ArrayList<>();

for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
}else{
if(input.get(i).start > result.get(result.size()-1).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){
}
}

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

}``````

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

Collections.sort(input,new SortByStart());

ArrayList<Interval> result = new ArrayList<>();

for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
}else{
if(input.get(i).start > result.get(result.size()-1).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){
}
}

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

}``````

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

Collections.sort(input,new SortByStart());

ArrayList<Interval> result = new ArrayList<>();

for(int i = 0 ; i < input.size() ; i++){
if(result.isEmpty()){
}else{
if(input.get(i).start > result.get(result.size()-1).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){
}
}

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

}``````

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

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

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)
i+=1
print("total hours=",len(hours))}

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)
i+=1
print("total hours=",len(hours))``````

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

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.PrintIntervals();

handler.PrintIntervals();

}
}``````

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();
System.out.println(solution(list));

}
}``````

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) {

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++) {
}

}

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

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.Sort();
}

return interval;
}

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

/**
* <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) {
}

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

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

}``````

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;

/**
* <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) {
}

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

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

}``````

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;

/**
* <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) {
}

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

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
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;
}``````

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

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

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

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

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

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++)
}
return hours.size();
}``````

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

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

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

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

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)

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

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

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

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

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.