Facebook Interview Question for Software Engineer / Developers


Team: Infrastructure
Country: United States
Interview Type: Phone Interview




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

This sounds like unweighted interval scheduling (which is greedy):

Order all the events on the calendar by their ending time in a list. Then,
loop through all of the events. For each event, remove all events in the list that it intersects, then continue to the next event in the list and repeat the process.

If there are certain events that are more valuable (more weight), then do the weighted interval scheduling algorithm which uses dynamic programming

- Skor January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the same algorithm I implemented in C++. Note that I'm using ints for start and end times for simplification.

#include <algorithm>
#include <vector>

struct Event
{
	int start, end;
};

bool mySort(Event a, Event b)
{
	return a.end < b.end;
}

// Note: Events are sorted
void removeIntersecting(std::vector<Event> &events, Event e)
{
	std::vector<Event>::iterator it = events.begin();
	while (it != events.end() && it->start < e.end)
	{
		++it;
	}
	events.erase(events.begin(), it);
}

int maxEvents(std::vector<Event> events)
{
	int result = 0;
	std::sort(events.begin(), events.end(), mySort);
	while (!events.empty())
	{
		++result;
		removeIntersecting(events, events[0]);
	}
	return result;
}

- Nick March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This can be solved using greedy algorithm

- Bond January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1) Sort events by the END time
2) Enumerate sorted array
3) If current event doesn't intersect last added event add it to result array

- Oleksii January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This sounds like unweighted interval scheduling (which is greedy):

Order all the events on the calendar by their ending time in a list. Then,
loop through all of the events. For each event, remove all events in the list that it intersects, then continue to the next event in the list and repeat the process.

If there are certain events that are more valuable (more weight), then do the weighted interval scheduling algorithm which uses dynamic programming

- Skor January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem seems a bit unclear as find the maximum non intersecting events in a Calendar. So either is actually asking for all non-intersecting events or asking for max per day anyway it is trivial to find per day so I'll implement both.

public class Event
{
	public int Start {get; set; }
	public int End {get; set; }
}


public static int GetNonIntersectingEvents(List<Event> events)
{
	// Count== 0 is 0 intersection, Count == 1 is 1 intersection
	if(events.Count < 2) 
	{
		return events.Count;
	}

	// This acts like a heap so sorting is O(n log n) as every insertion is O(logn)
	SortedDictionary<int, Event> sb = new SortedDictionary<int, List<Event>>();

	foreach(Event e in events)
	{
		if(sb.ContainsKey(e.Start))
			sb[e.Start].Add(e);
		else
			sb.Add(e.Start, new List<Event>(){ e});
	}
	
	List<Event> sortedEvents = new List<Events>();

	foreach(var kvp in sd)
	{
		sortedEvents.AddRange(kvp.Value);
	}

	int result = 0;
	
	bool intersect = false;
	Event prev =  sortedEvents[0].Clone;
	
	for(int i = 1; i < sortedEvents.Count; i++)
	{
		Event curr = sortedEvents[i];

		if(prev.End > curr.Start)
		{
			intersect = true;
			if(curr.End > prev.End)
			{	
				// Union of intersections
				prev.End = curr.End
			}
		}
		else // Means that current breaks the previous
		{
			// Check if the prev had an intersection
			if(intersect == false)
			{
				results++;
			}

			intersect = false;
			prev = curr.Clone();
		}
	}
	
	if(intersect == false)
	{
		result++;
	}

	return result;
}

In the case where it is asking for the max intersections based on Days

// Assuming events on two days will be two separate events per day.
public class Day
{
	public readonly List<Event> Events = new List<Events>();
	...
	...
}

public static int CalculateMaxNonIntersectingEvents(List<Day> days)
{
	int max = 0;

	if(days == null || days.Count == 0) return 0;

	foreach(Day d in days)
	{
		int temp = GetNonIntersectingEvents(d.Events);
		if(temp > max)
		{
			max = temp;
		}
	}

	return max;
}

- Nelson Perez January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Interval tree anyone??

- Lazad January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ code. ( Sort by ending time + next event begin time >= previous event end time )

typedef std::pair<unsigned int, unsigned int> event;

bool sort_sec ( const event &a, const event &b ) {
	if ( a.second == b.second ) 
		return a.first < b.first;
	return a.second < b.second;
}

void job_sched( vector<event> &events) {
	// sort by ending time
	sort( events.begin(), events.end(), sort_sec );

	int end=0;
	for(int i=0; i<events.size(); ++i) {
		// if current event begins after the previous one ends, it can be scheduled
		if ( events[i].first >= end ) {
			cout << "{" << events[i].first << "," << events[i].second << "}\t";
			end = events[i].second;
		}
	}
	cout << endl;
}

- indianspartan January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool CompareTime(const Event& left, const Event& right)
{
	return left.end < right.end;
}

int FindNonIntersectingEvents(vector<Event> events)
{
	int count = 0;
	if (events.empty())
	{
		return count;
	}	
	
	count = 1;
	std::sort(events.begin(), events.end(), CompareTime);
	Event prev = events[0];
	for (int i = 1; i < events.size(); i++)
	{
		Event next = events[i];
		if (prev.end <= next.start)
		{
			prev = next;
			count++;
		}
		else
		{
			if (prev.end > next.end)
			{
				prev = next;
			}
		}
	}
	return count;
}

- Anonymous January 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution.
I assumes the question is to return the number of unique events given list of random events.

int count_unique_events(vector<event*>& events)
{
	quick_sort(events, 0, events.size()-1);
	event * cur = 0;
	vector<event*>::iterator iter = events.begin();
	while(iter != events.end())
	{
		if (!cur)
		{
			cur = (*iter);
			iter++;
			continue;
		}

		if (cur->end >= (*iter)->start)
		{
			iter = events.erase(iter);
		} else {
			cur = (*iter);
			iter++;
		}		
	}
	return events.size();
}

- hankm2004 August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Frist, sort events by its start time. Second, start with the first event, put it to the stack. Check if the 'new' event has overlap:
a) If NOT, add it to the stack.
b) If YES, it can intersect only with the last event (events were sorted). If the stop time of this new event is less the stop time of that on the stack, replace them.
Retun the size of the stack;

A sample code is below:

public int maxEvents(Event[] a) {
	Arrays.sort(a); 	// assume Event is Comparable
	int N = a.length();
	Stack<Event> stk = new Stack<Event>();
	stk.push(a[0]); 	// push the first event on the stack

	for (int k=1; k<M, k++) {
		Event curr = a[k];
		Event last  = stk.peek();
		if (last.stop >= curr.start)	// no overlap
			stk.push(e); 
		else							// overlap
			if (curr.stop < last.stop) {
				stk.pop(); 		// replace event
				stk.push(curr); 
			}

	}
	return stk.size();
}
public class Event implemnts Comparable<Event>{
	public int start;
	public int stop;
	...
}

- autoboli January 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sort on what?

- Nelson Perez January 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sort w.r.t. start time hence

public class Event implemnts Comparable<Event> {
...
	public int compareTo(Event other) {
		if (this.start < other.start) return -1;
		if (this.start > other.start) return 1;
		return 0;
	}
}

- autoboli January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

As question is : maximum number of non-intersecting events (not to consider any event which intersect with any other event), in your case you are considering events which are interesting. For example, lets say events are: 1-3, 2-4, 4-6, 6-8, 7-9, 9-10 in sorted order. Then answer should be 4-6 and 9-10. I would like to modify your approach by adding one extra bit which we put with each element in stack.
Step 1: Sort by starting time.
Step 2: Put first element in stack, when adding next element check if start time of next is in between start and end of top element, then check if take max (end time on top of stack, end time of next). Replace this with end time of top element and mark this as not useful. This will stay on top.
Step 3. When a element comes which is not in the range of top element. Top element is marked, then remove this marked element and add this next element.

For my example:
Step 1: 1-3, not marked
Step 2: 1-4, marked
Step 3: Remove 1-4 and add 4-6.
Step 4: 4-6, 6-8(top) not marked
Step 5: 4-6, 6-9(top) marked
Step 6: 4-6, Remove 6-9 from top and add 9-10 on top.
Step 7. One all are done check if top is marked, if no then we are done, if yes, then remove top.

Now our answer is 4-6 and 9-10.

- myth January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It depends on interpretation. My interpretation is that there are events in the calendar e.g. football matches. The goal is to find a maximum number of football matches I can actually see.

If the sorted events were, say: 1-4, 2-3, 4-6, 6-8, 7-9, 9-10
Below is a trace of the stack in every iteration, there are three possible oprations when new event comes, these are: add, keep, replace
1: stack: 1-4
2: stack: 2-3 // replace, 2-3 intersects but ends earlier
3: stack: 2-3, 4-6 // add, does not intersect
4: stack: 2-3, 4-6 // keep, 6-8 intersects and ends later
5: stack: 2-3, 4-6, 7-9 // add, does not intersect
6: stack: 2-3, 4-6, 7-9 // keep, 9-10 intersects and ends later

It looks correct to me. I can see no more than 3 football matches.

- autoboli January 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect Solution!

- Anonymous January 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks the stack is not necessary. Just keep tracking the count.

- Sheli January 11, 2015 | Flag


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