Facebook Interview Question for SDE1s


Country: United States




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

I got the question wrong, an example would be (if it's not the intersection of all, what it probably isn't):
Input: [1..2],[4..6],[5..7],[3..5],[9..11]
Output: 2,5,6,7,10

- Chris October 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What first comes out of my mind is:

If the intervals are all non negative numbers, and the maximum value for 'end' is known beforehand and not too large, use Segment Tree or BIT (Binary Indexed Tree) implementation for a range queries data structure.

interface RangeQueries {
  void set(int start, int end, int value);
  int getSum(int start, int end);
}

We know that both Segment Tree and BIT support above operations in O(log N) time. So code would look as follows.

public List<Integer> countCoverLength(Iterator<Interval> stream){
  List<Integer> runningCoverLength = new ArrayList<>();

  // here SIZE is the maximum value interval.end can have + 1
  RangeQueries rangeQueries = new BITRangeQueries(SIZE);

  // whole range is set to 0
  rangeQueries.set(0, SIZE - 1, 0);

  while (stream.hasNext()){
    Interval interval = stream.next();

    // update the interval
    rangeQueries.set(interval.start, interval.end, 1);

    // get updated cover length
    int coverLength = rangeQueries.getSum(0, SIZE - 1);

    runningCoverLength.add(coverLength);
  }

  return runningCoverLength;
}

Time complexity is O(N log M), where N is the amount if intervals in the stream and M the maximum value interval.end can have. Additional O(M) space is required for any of RangeQueries implementation, however in practice BIT performs better in this case.

Interviewer may say that's not the solution he is looking for, but I think it worths to mention it at least. A follow up on how BIT/Segment Tree work might be up next if interviewer likes this approach.

- Anonymous October 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think this is pretty much just the problem where you are given a list of intervals, and a single interval and you just want to merge the interval into this list of intervals. You just have to loop through each interval in your iterator and then add the amount covered to your running total.

The only trick is to keep the running total space covered which isn't really too bad.

In other words, the pseudocode is something like

while I have intervals in my interval stream
             get the next interval
             merge the next interval and return the amount covered plus the merged list
             add the amount covered to my running total of amount covered and append to my result
             use the merged list for the next iteration of the loop.

The java 8 implementation using a priority queue to handle sorting:

import java.util.*;

/**
 */
public class IntervalCoverLength {

	/**
	 * Interval object with some stuff to make it more easily readible when debugging.
	 */
	static class Interval {
		int low;
		int hi;

		@Override
		public String toString() {
			return "{" + low +
					", " + hi + "}";
		}

		public Interval(int low, int hi) {
			this.low = low;
			this.hi = hi;
		}

		public int amountCovered() {
			return this.hi - this.low + 1;
		}

		public static Interval copy(Interval src) {
			return new Interval(src.low, src.hi);
		}
	}

	/**
	 * Wrapper class to capture the result of a single merging operation.
	 */
	static class Wrapper {
		int coverLength;
		PriorityQueue<Interval> covered;

		public Wrapper(int covered, PriorityQueue<Interval> unmerged) {
			this.coverLength = covered;
			this.covered = unmerged;
		}
	}

	/**
	 * Primary loop that goes through the intervals and actually merges a single interval at a time.
	 * @param intervals
	 * @return
	 */
		public static List<Integer> countCoverLength(Iterator<Interval> intervals) {
		PriorityQueue<Interval> covered = new PriorityQueue<>(Comparator.comparingInt(i -> i.low));
		List<Integer> runningTotal = new ArrayList<>();

		while(intervals.hasNext()) {
			Interval cur = intervals.next();

			Wrapper wrapper = mergeIntervals(covered, cur);

			int totalAmountCovered = runningTotal.size() > 0 ? runningTotal.get(runningTotal.size() - 1) : 0;

			runningTotal.add(totalAmountCovered + wrapper.coverLength);
			covered = wrapper.covered;
		}

		return runningTotal;
	}

	/**
	 * The primary logic which basically solves the problem of merging an interval to an existing collection of intervals
	 * @param covered
	 * @param inserting The original interval that I want to insert
	 * @return
	 */
	private static Wrapper mergeIntervals(PriorityQueue<Interval> covered, Interval inserting) {
		Interval toIns = Interval.copy(inserting);  //This is the interval that I am actually going to insert (could be modified based on what intervals it overlaps).

		PriorityQueue<Interval> merged = new PriorityQueue<>(covered.comparator());
		int newLengthUnmerged = inserting.amountCovered();
		/**
		 * The for loop goes through each interval and determines what interval is the resultant interval that should
		 * actually be added.
		 */
		for (Interval interval : covered) {
			/**
			 * If the interval is completely not covered, then just add it. Duh...
			 */
			if (toIns.low > interval.hi || toIns.hi < interval.low) {
				merged.add(interval);
			} else {
				/**
				 * If the interval that I am inserting overlaps with the top part of the interval,
				 * then my new lower bound should be either the lower bound of the current interval,
				 * or the interval that I am inserting
				 */
				if (toIns.low < interval.hi) {
					toIns.low = Math.min(interval.low, toIns.low);
					if (toIns.low == interval.low) { //The amount that is actually going to be covered is going to be deducted due to some amount having been covered already.
						newLengthUnmerged -= (Math.abs(interval.hi - inserting.low) + 1);
					}
				}
				/**
				 * If the interval that I am inserting overlaps with part of the bottom interval,
				 * I set my interval that I am inserting to now have an upper bound same as the
				 * top interval to insert.
				 */
				if (toIns.hi > interval.low) {
					toIns.hi = Math.max(interval.hi, toIns.hi);
					if (toIns.hi == interval.hi) {
						newLengthUnmerged -= (Math.abs(inserting.hi - interval.low) + 1);
					}
				}
			}
		}

		if (newLengthUnmerged < 0) { //Floor at 0
			newLengthUnmerged = 0;
		}

		merged.add(toIns);

		return new Wrapper(newLengthUnmerged, merged);
	}

	/**
	 * Simple routine that shortens the amount of typing needed.
	 * @param low
	 * @param hi
	 * @return
	 */
	public static Interval of(int low, int hi) {
		return new Interval(low,hi);
	}

	/**
	 * Main function goes through the example provided by the problem.
	 * @param args
	 */
	public static void main(String...args) {
             
                //Test case from original code prints [2, 5, 6, 7, 10]
		List<Interval> intervals = Arrays.asList(
				of(1, 2),
				of(4, 6),
				of(5, 7),
				of(3, 5),
				of(9, 11)
		);

		System.out.println(countCoverLength(intervals.iterator()));

                //Completely overlapped prints: [5, 5]
		List<Interval> intervals2 = Arrays.asList(
				of(1, 5),
				of(3, 4)
		);

		System.out.println(countCoverLength(intervals2.iterator()));

                //Partially overlapped on the upper end prints: [9, 11]
		List<Interval> intervals3 = Arrays.asList(
				of(1, 9),
				of(2, 11)
		);

		System.out.println(countCoverLength(intervals3.iterator()));

                //partially overlapped on the bottom prints [5, 8]
		List<Interval> intervals4 = Arrays.asList(
				of(5, 9),
				of(2, 7)
		);

		System.out.println(countCoverLength(intervals4.iterator()));
	}
}

- liuben10 October 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To make it efficient, we can maintain Interval Search Tree.
For purposes of an interview, we can keep a list of sorted, not overlapping intervals. For each interval coming from the stream, we calculate how much of new coverage the interval brings, and then, we apply the new coverage to the existing intervals.
This can be improved by applying a binary search for finding overlapping intervals, and/or skip list/linked list for keeping the running list of intervals short.

#include <iostream>
#include <vector>

using namespace std;

class Interval {
	public:
		Interval(int start, int end)
		{
			start_ = start;
			end_ = end;
		}
		int start_, end_;
};

int NewCoverage(vector<Interval> &a, Interval const &in)
{
	int new_coverage = 0;
	int i = 0;
	for (; i < a.size() && a[i].start_ < in.end_; ++i) {
		if (in.start_ < a[i].start_ &&
			in.end_ > a[i].start_)
		{
			int delta = (i > 0 && a[i - 1].end_ > in.start_)
				? a[i].start_ - a[i - 1].end_
				: a[i].start_ - in.start_;
			new_coverage += delta;
			a[i].start_ -= delta;
		}
		if (in.end_ > a[i].end_ &&
			in.start_ < a[i].end_)
		{
			int delta = (i + 1 < a.size() && a[i + 1].start_ < in.end_)
				? a[i + 1].start_ - a[i].end_
				: in.end_ - a[i].end_;
			new_coverage += delta;
			a[i].end_ += delta;
		}
	}
	if (new_coverage == 0) {
		new_coverage = in.end_ - in.start_;
		a.insert(a.begin() + i, in);
	}
	return new_coverage;
}

int main(int argvc, char const **argv)
{
	vector<Interval> stream({Interval(1, 2), Interval(4, 6), Interval(5, 7), Interval(3, 5), Interval(9, 11)});
	vector<Interval> a;
	int covered = 0;

	for (auto in : stream) {
		covered += NewCoverage(a, in);
		cout << covered << ": ";
		for (auto el : a) {
			cout << el.start_ << "-" << el.end_ << ", ";
		}
		cout << "\n";
	}

	return 0;
}

- Alex November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using C++ STL "Set" as balanced tree and keeping track of intervals.
+ Deleting intervals when we insert new overlapping intervals.
+ Intervals expected in [start,end) format.

#include<iostream>
#include<vector>
#include<stack>
#include<utility>
#include<set>

using namespace std;

class intervalTracker
{
public:
	int total;
	set< pair<int,int> > tree;
	
	intervalTracker(): total(0)
	{}
	
	void insert( pair<int,int> range )
	{
		if( tree.empty() )
		{
			tree.insert(range);
			total += (range.second - range.first);
		}
		
		// This is not the first node, so now we find a correct place to install this
		pair<int,int> tmp = { range.first, INT_MAX };
		auto it = tree.upper_bound( tmp );
		
		// update previous neighbor 
		if( it != tree.begin() )
		{
			if( (--it)->second < range.first )
			{
				++it;
			}
			else
			{
				range.first = it->first;
				range.second = max( it->second, range.second );
				total -= ( it->second - it->first );
				it = tree.erase(it);
			}
		}
		
		// itertor still points to upper bound, regardless erased node or not
		// check next neighbor for overlapping intervals
		while( it != tree.end() && range.second >= it->first )
		{
			total -= ( it->second - it->first);
			range.second = max( it->second, range.second );
			it = tree.erase( it);
		}
		
		total += ( range.second - range.first );
		tree.insert(range);		
	}
	
	vector<int> addIntervals( const vector<pair<int,int>>& intervals)
	{
		vector<int> result;
		for( auto x : intervals )
		{
			insert(x);
			result.push_back( total );
		}
		return result;
	}
};
int main()
{
	vector< pair<int,int> > intervals = {{1,3},{4,7},{5,8},{3,6},{9,12}};
	intervalTracker iTrack;
	vector<int> result = iTrack.addIntervals( intervals );
	
	for(int i=0; i<result.size(); ++i)
	{
		cout << result[i] << " ";
	}
	return 0;
}

- mr.robot.fun.society November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As mentioned by others, I need to maintain the intervals that cover and don't overlap.
This can be done using a BST keeping start in order. I need to ensure nothing overlaps,
that is, when I insert an interval, I might need to merge. If I merge, I only count
the part of the interval that was not already covered.

time complexity: O(n*lg(n))
space complexity: O(n)

I think the implementation can be significantly less complex. Didn't test corner
cases tough.

It turns out it's slightly easier to implement using half open intervals.

With Fenwicks (Binary index tree) we can't do much good here because the intersection function of intervals is not reversible (unlike e.g. sum).

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

using namespace std;

struct Interval 
{
	int start_, end_;
};

void countCoveredLength(const vector<Interval>& stream) 
{
	int covered_space = 0;
	map<int, int> covered({ { numeric_limits<int>::min(), numeric_limits<int>::min() }, 
		{ numeric_limits<int>::max(), numeric_limits<int>::max() } }); // map<start, end>
	for (const Interval& i : stream) {
		if (i.start_ != i.end_) { // ignore empty intervals
			auto it = prev(covered.upper_bound(i.start_)); // it points to interval that starts before i
			if (it->second < i.start_) { // if it ends before i starts, add a new one
				it = covered.insert(it, { i.start_, i.start_ });
			}
			while (it->second < i.end_) { // if i ends after it, extend tree
				auto it_next = next(it);
				if (it_next->first <= i.end_) { // next interval in tree starts before i ends, merge them
					covered_space += it_next->first - it->second;
					it->second = it_next->second;
					covered.erase(it_next);
				}
				else { // next interval in tree starts after i ends
					covered_space += i.end_ - it->second; // new end - old end
					it->second = i.end_;
				}
			}
		}
		cout << covered_space << " ";
	}
}

int main()
{
	countCoveredLength({ {1,3},{4,7},{5,8},{3,6},{9,12} }); 
}

- Chris November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question can be translated into several ways.
From looking on the function definition, it returns a list of integers:

public List<Integer> countCoverLength(Iterator<Interval> stream);

The total cover length calculation... is it from min to max? or is it the sum of all length calculations?

The next code will calculate all covers and then sum them:

package com.cracking.facebook;

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

public class TotalLengthCover {

	public static void main(String[] args) {
		Iterator<Interval> stream = MockIntervalStream();
		List<Integer> coverList = CountCoverLength(stream);
		
		System.out.println("Cover List: " + Arrays.toString(coverList.toArray()) );
		System.out.println("Total: " + TotalCoverLength(coverList) );
	}
	
	public static int TotalCoverLength(List<Integer> list) {
		int sum = 0;
		for(int i=0; i<list.size(); i++) {
			sum += list.get(i);
		}
		return sum;
	}
	
	public static List<Integer> CountCoverLength(Iterator<Interval> stream) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		while(stream.hasNext()) {
			Interval interval = stream.next();
			list.add(interval.covered());
		}
		
		return list;
	}
	
	public static class Interval {
		public int start;
		public int end;
		
		public Interval(int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		public int covered() {
			return Math.abs(this.start - this.end);
		}
	}

	public static Iterator<Interval> MockIntervalStream() {
		Hashtable<Integer, Interval> table = new Hashtable<Integer, Interval>();
		
		table.put(1, new Interval(5, 12));
		table.put(2, new Interval(20, 12));
		table.put(3, new Interval(189, 260));
		table.put(4, new Interval(0, -10));
		
		return table.values().iterator();
	}
}

Output:
Cover List: [10, 71, 8, 7]
Total: 96

- ProTechMulti November 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class MyClass {
static class Interval{
int start;
int end;
Interval(int s, int e){
start = s;
end = e;
}
}
public static List<Integer> countCoverLength(Iterator<Interval> stream){
int low = Integer.MAX_VALUE;
int high = Integer.MIN_VALUE;
while(stream.hasNext()){
Interval it = stream.next();
if(it.start < low) low = it.start;
if(it.end > high) high = it.end;
}
List<Integer> li = new ArrayList<>();
li.add(low); li.add(high);

return li;
}

public static void main(String args[]) {
Interval i1 = new Interval(2,4);
Interval i2 = new Interval(-2,3);
Interval i3 = new Interval(3,5);
List l = new ArrayList();
l.add(i1); l.add(i2); l.add(i3);
System.out.println(countCoverLength(l.iterator()));
}
}

- aav November 02, 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