## Facebook Interview Question for Software Engineers

Country: United States

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

Sort by starting time and traverse. Keep current ending point and sum so far.

``````public static int totalTimeOn(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]);

int ending = 0, ans = 0;
for(int[] i : intervals) {
ans += Math.max(i[1] - Math.max(i[0], ending), 0);
ending = Math.max(ending, i[1]);
}

return ans;
}``````

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

``````static uint? mergeIntervals(IEnumerable<Tuple<uint, uint>> times)
{
if (times == null || !times.Any())
return null;

var ordered = times.OrderBy(t => t.Item1);

uint sum = 0;
var merged = new Tuple<uint, uint>(ordered.First().Item1, ordered.First().Item2);

foreach(var time in ordered)
{
if(time.Item1 > merged.Item2)
{
sum += merged.Item2 - merged.Item1;
merged = new Tuple<uint, uint>(time.Item1, time.Item2);
}
else if(time.Item2 > merged.Item2)
merged = new Tuple<uint, uint>(merged.Item1, time.Item2);
}

sum += merged.Item2 - merged.Item1;

return sum;
}``````

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

``````/* There's a room with a TV and people are coming in and out to watch it. The TV
* is on only when there's at least a person in the room.
*
* For each person that comes in, we record the start and end time. We want to
* know for how long the TV has been on. In other words:
*
* 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)]
* # > 3
* # input = [(4,6), (1,2)]
* # > 3
* # input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* # > 11
*/

/* In order to correct calculate continues time when TV was on, we need to
* merge/collapse interleaving intervals together.
*
* [[1,4], [2,3]] => [1,4]
* [[2,3], [1,2]] => [1,3]
*/
function collapse(intervals) {
return intervals.sort(function(a,b){ return a[0] - b[0];})
.reduce(function(ret, curr) {
if(ret.length == 0) {
return [curr];
}

var last = ret[ret.length - 1];
if(last[1] >= curr[0]) {
ret[ret.length - 1] = [
last[0],
curr[1] > last[1] ? curr[1] : last[1]];
} else {
ret.push(curr);
}

return ret;
}, []);
}

function tvOn(intervals) {
return collapse(intervals).reduce(function(acc, curr) {
return acc + (curr[1] - curr[0]);
}, 0);
}

module.exports = {
tvOn: tvOn,
collapse: collapse
};``````

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

``````/* There's a room with a TV and people are coming in and out to watch it. The TV
* is on only when there's at least a person in the room.
*
* For each person that comes in, we record the start and end time. We want to
* know for how long the TV has been on. In other words:
*
* 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)]
* # > 3
* # input = [(4,6), (1,2)]
* # > 3
* # input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* # > 11
*/

/* In order to correct calculate continues time when TV was on, we need to
* merge/collapse interleaving intervals together.
*
* [[1,4], [2,3]] => [1,4]
* [[2,3], [1,2]] => [1,3]
*/
function collapse(intervals) {
return intervals.sort(function(a,b){ return a[0] - b[0];})
.reduce(function(ret, curr) {
if(ret.length == 0) {
return [curr];
}

var last = ret[ret.length - 1];
if(last[1] >= curr[0]) {
ret[ret.length - 1] = [
last[0],
curr[1] > last[1] ? curr[1] : last[1]];
} else {
ret.push(curr);
}

return ret;
}, []);
}

function tvOn(intervals) {
return collapse(intervals).reduce(function(acc, curr) {
return acc + (curr[1] - curr[0]);
}, 0);
}

module.exports = {
tvOn: tvOn,
collapse: collapse
};``````

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

keeping track of all intervals, adjusting them when a new interval falls in the current ones range

``````import java.util.*;
public class Question
{

public static void main(String[] args)
{
int[][] inputOne = {{1,4},{2,3}};
int[][] inputTwo = {{4,6},{1,2}};
int[][] inputThree = {{1,4},{7,8},{2,4},{7,9},{10,16}};

System.out.println("total time one: " +  totalTime(inputOne));
System.out.println("total time two: " + totalTime(inputTwo));
System.out.println("total time three: " + totalTime(inputThree));

}

public static int totalTime(int[][] input){

if(input == null ||input.length == 0){
return 0;
}

int totalTime = 0;

ArrayList<int[]> totalIntervals = new ArrayList<int[]>();

int[] firstInterval = {input[0][0], input[0][1]};

for(int i = 1; i < input.length; i++){

boolean updatedInterval = false;

int index = 0;

while(!updatedInterval){

int[] currentInterval = totalIntervals.get(index);

if(input[i][0] >= currentInterval[0] && input[i][1] <= currentInterval[1]){

updatedInterval = true;

}else if(input[i][0] < currentInterval[0] && input[i][1] >= currentInterval[0]){

currentInterval[0] = input[i][0];

if(input[i][1] > currentInterval[1]){

currentInterval[1] = input[i][1];
}

updatedInterval = true;

}else if(input[i][1] > currentInterval[1] && input[i][0] <= currentInterval[1]){

currentInterval[1] = input[i][1];

if(input[i][0] < currentInterval[0]){

currentInterval[0] = input[i][0];
}

updatedInterval = true;

}else{

if(index < totalIntervals.size() - 1){

index++;
}else{

int[] newInterval = {input[i][0], input[i][1]};
updatedInterval = true;
}

}
}

}

for(int i = 0; i < totalIntervals.size(); i++){

int[] currentInterval = totalIntervals.get(i);
totalTime += (currentInterval[1] - currentInterval[0]);
}

}
}``````

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

``````public static int calculateTotalActiveTime(int[] comeInTimeArray,int[] leaveTimeArray){

int lastPowerOnTime=-1;
Map<Integer,Integer> timeActivePeopleMap=new HashMap<Integer,Integer>();
for(int person=0;person<comeInTimeArray.length;person++){
updateTimeActivePeopleMap(timeActivePeopleMap,comeInTimeArray[person],1);
updateTimeActivePeopleMap(timeActivePeopleMap,leaveTimeArray[person],-1);
}
int totalActiveTime=0;
int lastTurnOnTime=0;
boolean isTVOn=false;
int currentPeopleInTheRoom=0;
for(Map.Entry<Integer,Integer> entry: timeActivePeopleMap.entrySet()){
currentPeopleInTheRoom+=entry.getValue();
if(!isTVOn){
if(currentPeopleInTheRoom>0){
lastTurnOnTime=entry.getKey();
isTVOn=true;
}
}else{
if(currentPeopleInTheRoom<=0){
totalActiveTime+=entry.getKey()-lastTurnOnTime;
isTVOn=false;
}
}
}

}

public static void updateTimeActivePeopleMap(Map<Integer,Integer> mapToBeUpdated,int mapItem,int delta){
Integer activePeople=mapToBeUpdated.get(mapItem);
if(activePeople==null){
mapToBeUpdated.put(mapItem,delta);
}else{
mapToBeUpdated.put(mapItem,activePeople + delta);
}
}``````

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

``````import java.util.*;

public class TimeIntervalProblem {
public static void main(String[] args) {
System.out.println(findSumIntervals(ptList));
ptList = new ArrayList<TimeInterval>();
System.out.println(findSumIntervals(ptList));
ptList = new ArrayList<TimeInterval>();
System.out.println(findSumIntervals(ptList));
}
public static int findSumIntervals(List<TimeInterval> ptList) {
// sort ptList by TimeInterval.in
sort(ptList);
//merge intervals if they are overlapping
List<TimeInterval> list = mergeIntervals(ptList);
return sumIntervals(list);
}
public static int sumIntervals(List<TimeInterval> ptList) {
//use any sort here, since its a small list for the examples, using insertion sort here:
int sum = 0;
for(TimeInterval ti: ptList){
sum += ti.out - ti.in;
}
return sum;
}
public static void sort(List<TimeInterval> ptList) {
//use any sort here, since its a small list for the examples, using insertion sort here:
for(int i= 1; i< ptList.size(); i++){
for(int j = 0; j< i; j++){
if(ptList.get(i).in < ptList.get(j).in){
TimeInterval temp = ptList.get(i);
for(int k = i; k> j; k--){
ptList.set(k, ptList.get(k-1));
}
ptList.set(j, temp);
}
}
}
}
public static List<TimeInterval> mergeIntervals(List<TimeInterval> ptList) {
TimeInterval previousInterval = null;
for(int i=0; i< ptList.size(); i++){
TimeInterval ti = ptList.get(i);
if(previousInterval == null){
previousInterval = ti;
continue;
}
//check overlapping
if(ti.in <= previousInterval.out && ti.out > previousInterval.out){
previousInterval.out = ti.out;
} else if (ti.in > previousInterval.out){
previousInterval = ti;
}
if(i == ptList.size() -1){
}
}
return list;
}
}
class TimeInterval{
int in;
int out;
TimeInterval(int in, int out){
this.in = in;
this.out = out;
}
}``````

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

My solution in PHP, probably ther could be something more efficienmt

``````// php code is wrapped in <?php tags

class IntervalSeeker {

protected \$_intervals;

public \$min = PHP_INT_MAX;

public \$max = 0;

public \$total_interval = [];

function __construct(array \$intervals) {
\$this->_intervals = \$intervals;
}

function find_interval() {
\$this->find_min_max_in_intervals();
\$this->create_range_array();
\$this->iterate_over_intervals();
return \$this->find_not_covered_intervals();
}

function find_min_max_in_intervals() {
foreach( \$this->_intervals as \$interval ) {
\$min = \$interval[0];
\$max = \$interval[1];

if ( \$min < \$this->min ) {
\$this->min = \$min;
}

if ( \$max > \$this->max ) {
\$this->max = \$max;
}
}
}

function create_range_array() {
for ( \$iter = \$this->min; \$iter <= \$this->max; \$iter++ ) {
\$this->total_interval[\$iter] = false;
}
}

function iterate_over_intervals() {
foreach( \$this->_intervals as \$interval ) {
\$min = \$interval[0];
\$max = \$interval[1];

for ( \$iter = \$min + 1; \$iter <= \$max; \$iter++ ) {
\$this->total_interval[\$iter] = true;
}
}
}

function find_not_covered_intervals() {
\$count = 0;

foreach( \$this->total_interval as \$covered ) {
if ( true === \$covered ) {
\$count++;
}
}

return \$count;
}
}

\$interval = new IntervalSeeker( [[1,4], [6,8], [2,4], [7,9], [10,15]] );
echo \$interval->find_interval(); // 11``````

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

Solution in PHP

``````// php code is wrapped in <?php tags

class IntervalSeeker {

protected \$_intervals;

public \$min = PHP_INT_MAX;

public \$max = 0;

public \$total_interval = [];

function __construct(array \$intervals) {
\$this->_intervals = \$intervals;
}

function find_interval() {
\$this->find_min_max_in_intervals();
\$this->create_range_array();
\$this->iterate_over_intervals();
return \$this->find_not_covered_intervals();
}

function find_min_max_in_intervals() {
foreach( \$this->_intervals as \$interval ) {
\$min = \$interval[0];
\$max = \$interval[1];

if ( \$min < \$this->min ) {
\$this->min = \$min;
}

if ( \$max > \$this->max ) {
\$this->max = \$max;
}
}
}

function create_range_array() {
for ( \$iter = \$this->min; \$iter <= \$this->max; \$iter++ ) {
\$this->total_interval[\$iter] = false;
}
}

function iterate_over_intervals() {
foreach( \$this->_intervals as \$interval ) {
\$min = \$interval[0];
\$max = \$interval[1];

for ( \$iter = \$min + 1; \$iter <= \$max; \$iter++ ) {
\$this->total_interval[\$iter] = true;
}
}
}

function find_not_covered_intervals() {
\$count = 0;

foreach( \$this->total_interval as \$covered ) {
if ( true === \$covered ) {
\$count++;
}
}

return \$count;
}
}

\$interval = new IntervalSeeker( [[1,4], [6,8], [2,4], [7,9], [10,15]] );
echo \$interval->find_interval(); // 11``````

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

``````/* There's a room with a TV and people are coming in and out to watch it. The TV
* is on only when there's at least a person in the room.
*
* For each person that comes in, we record the start and end time. We want to
* know for how long the TV has been on. In other words:
*
* 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)]
* # > 3
* # input = [(4,6), (1,2)]
* # > 3
* # input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
* # > 11
*/

import java.util.*;

public class TVInterval {

public static void main(String[] args) {

int[][] inputOne = {{1,4},{2,3}};
int[][] inputTwo = {{4,6},{1,2}};
int[][] inputThree = {{1,4},{7,8},{2,4},{7,9},{10,16}};

System.out.println(calculate(inputOne));
System.out.println(calculate(inputTwo));
System.out.println(calculate(inputThree));
}

public static int calculate(int[][] intervals) {

System.out.println(Arrays.deepToString(intervals));

int[] bit = new int[24];
for(int k = 0; k < bit.length; k++)
bit[k] = 0;

for(int k = 0; k < intervals.length; k++) {
int i = intervals[k][0];
int j = intervals[k][1];
for(i += 1; i <=j ; i++)
bit[i] += 1;
}

int sum = 0;
for(int k = 0; k < bit.length; k++)
if(bit[k] > 0)
sum += 1;

return sum;
}
}``````

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

Using an unordered set (C++) makes the code rather short:
int tv_on_time(vector<vector<int>> times)
{
unordered_set<int> tv_on;
for(int i=0;i<times.size();i++)
{
for(int j=times[i][0];j<times[i][1];j++)
{
tv_on.emplace(j);
}
}
return tv_on.size();
}

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

var arr2D = [[1,4], [6,8], [2,4], [7,9], [10,15]]
func sort(_ arr: [[Int]]) -> [[Int]] {
return arr.sorted { (a, b) -> Bool in
return a[0] < b[0]
}
}

func totalTime(_ arr: [[Int]]) -> Int {
var ending = 0, ans = 0
for i in arr {
ans += max(i[1] - max(i[0], ending), 0)
ending = max(ending, i[1])
}

return ans
}

let time = totalTime(sort(arr2D)) // time is 11

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

Swift Version::::

``````var arr2D = [[1,4], [6,8], [2,4], [7,9], [10,15]]
func sort(_ arr: [[Int]]) -> [[Int]] {
return arr.sorted { (a, b) -> Bool in
return a[0] < b[0]
}
}

func totalTime(_ arr: [[Int]]) -> Int {
var ending = 0, ans = 0
for i in arr {
ans += max(i[1] - max(i[0], ending), 0)
ending = max(ending, i[1])
}

return ans
}

let time = totalTime(sort(arr2D)) // time is 11``````

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

``````def offtime1(input0):
# Get earlist and latest time points 'start' and 'end' of observation
# Construct set() with all integer values between start and end (inclusive)
# Iterate through tuples and delete the integers that fall within the tuple's range.

start = sorted(input0, key=lambda tup: tup[0])[0][0]
end = sorted(input0, key=lambda tup: tup[1])[-1][1]
d = set(range(start,end+1))
for i, j in input0:
d1 = set(range(i, j+1))
d= d.difference(d1)
return len(d)``````

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

``````def offtime1(input0):
# Get earlist and latest time points 'start' and 'end' of observation
# Construct set() with all integer values between start and end (inclusive)
# Iterate through tuples and delete the integers that fall within the tuple's range.

start = sorted(input0, key=lambda tup: tup[0])[0][0]
end = sorted(input0, key=lambda tup: tup[1])[-1][1]
d = set(range(start,end+1))
for i, j in input0:
d1 = set(range(i, j+1))
d= d.difference(d1)
return len(d)``````

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

The greedy algorithm

``````def totalOnTime(times):
times.sort(key = lambda x: x[0]) # nlogn
total = 0
last_start = 0
curr_max = 0
for interval in times:
if interval[0]>curr_max:
total+=curr_max-last_start
curr_max = interval[1]
last_start = interval[0]
else:
total+=(interval[0]-last_start)
last_start = interval[0]
if interval[1]>curr_max:
curr_max = interval[1]
total+=curr_max-last_start

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

``````import java.util.*;
public class TvOnInterval {

public static int getTvOnInterval(int[][] arr){
int[] arrival = new int[arr.length]; // arrival times array
int[] exit = new int[arr.length]; // exit times array

for(int i=0;i<=arr.length-1;i++){
arrival[i] = arr[i][0];
exit[i] = arr[i][1];
}

Arrays.sort(arrival); // sort
Arrays.sort(exit); //sort

int i=0;
int j=0;
int iStart = -1;  // tv start time (first time on or when switched on after off)
int guestCount=0; // guests in room at any point of time
int tvOnTime=0; // total time Tv is ON

while(i<=arr.length-1 && j <= arr.length-1){
if(arrival[i] < exit[j]){
if(guestCount == 0){
iStart=i;  // Tv is first turned on pr turned on after an off - after guestCount was 0
}
guestCount++;
i++;
}else if(exit[j] < arrival[i]){
guestCount--;
if(guestCount == 0){ // Tv is turned off
System.out.println("iStart="+arrival[iStart]+" jEnd="+exit[j]);
tvOnTime = tvOnTime + (exit[j]-arrival[iStart]);
}
j++;
} else{
// else one arrival one exist no change
i++;
j++;
}
}

// last exit time of j
System.out.println("iStart="+arrival[iStart]+" jEnd="+exit[exit.length-1]);
tvOnTime = tvOnTime + (exit[exit.length-1] - arrival[iStart]);
return tvOnTime;
}

public static void main(String[] args) {

int[][] arr = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}};
System.out.println("Total Tv On time : "+ getTvOnInterval(arr));
}
}``````

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

Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.

``````public static int mergeSegments(int[][] segments) {
if(segments.length == 0) return 0;

TreeMap<Integer, Integer> map = new TreeMap<>();

for(int[] s: segments) {

int start, end;
Integer sKey = map.floorKey(s[0]);
if(sKey == null || map.get(sKey) < s[0]) {
start = s[0];
end = s[1];
} else {
start = sKey;
end = Math.max(s[1], map.get(sKey));
}

Integer next = map.higherKey(start);
while(next != null && map.get(next) <= end) {
end = Math.max(map.get(next), end);
map.remove(next);
next = map.higherKey(next);
}
map.put(start, end);
}

int sum = 0;
for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
sum += entry.getValue() - entry.getKey();
}
return sum;
}``````

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.