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

- mcopes73 February 08, 2017 | Flag Reply
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;
        }

- promoisha February 09, 2017 | Flag Reply
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
};

- Max February 09, 2017 | Flag Reply
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
};

- Max February 09, 2017 | Flag Reply
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]};
    
    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;
  }
}

- DCIS February 09, 2017 | Flag Reply
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;
          }
        }
    }
    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); 
        }    
  }

- Emre Bayram February 12, 2017 | Flag Reply
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) {
		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;
	}
}

- Mei Li February 12, 2017 | Flag Reply
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

- Nicola Peluchetti February 12, 2017 | Flag Reply
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

- Anonymous February 12, 2017 | Flag Reply
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;
	}
}

- I'm assuming the time is hours. February 13, 2017 | Flag Reply
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();
}

- ronshub88 February 13, 2017 | Flag Reply
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

- Rupak February 22, 2017 | Flag Reply
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

- Rupak February 22, 2017 | Flag Reply
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)

- sociologist0 February 24, 2017 | Flag Reply
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)

- sociologist0 February 24, 2017 | Flag Reply
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			
	return total

- shwinzypie March 06, 2017 | Flag Reply
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));
	}
}

- Mayank Jain August 10, 2017 | Flag Reply
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;
    }

- aonecoding February 08, 2017 | 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