Facebook Interview Question
Software EngineersCountry: United States
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;
}
/* 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
};
/* 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
};
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]};
totalIntervals.add(firstInterval);
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]};
totalIntervals.add(newInterval);
updatedInterval = true;
}
}
}
}
for(int i = 0; i < totalIntervals.size(); i++){
int[] currentInterval = totalIntervals.get(i);
totalTime += (currentInterval[1] - currentInterval[0]);
}
return totalTime;
}
}
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;
}
}
}
return totalActiveTime;
}
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);
}
}
import java.util.*;
public class TimeIntervalProblem {
public static void main(String[] args) {
List<TimeInterval> ptList = new LinkedList<TimeInterval>();
ptList.add(new TimeInterval(1, 4));
ptList.add(new TimeInterval(2, 3));
System.out.println(findSumIntervals(ptList));
ptList = new ArrayList<TimeInterval>();
ptList.add(new TimeInterval(4, 6));
ptList.add(new TimeInterval(1, 2));
System.out.println(findSumIntervals(ptList));
ptList = new ArrayList<TimeInterval>();
ptList.add(new TimeInterval(1, 4));
ptList.add(new TimeInterval(6, 8));
ptList.add(new TimeInterval(2, 4));
ptList.add(new TimeInterval(7, 9));
ptList.add(new TimeInterval(10, 15));
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) {
List<TimeInterval> list = new LinkedList<TimeInterval>();
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){
list.add(previousInterval);
previousInterval = ti;
}
if(i == ptList.size() -1){
list.add(previousInterval);
}
}
return list;
}
}
class TimeInterval{
int in;
int out;
TimeInterval(int in, int out){
this.in = in;
this.out = out;
}
}
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
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
/* 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;
}
}
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
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
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)
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)
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
return total
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));
}
}
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;
}
Sort by starting time and traverse. Keep current ending point and sum so far.
- mcopes73 February 08, 2017