Facebook Interview Question
Software Engineer / DevelopersTeam: Infrastructure
Country: United States
Interview Type: Phone Interview
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;
}
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
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;
}
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;
}
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;
}
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();
}
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;
...
}
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;
}
}
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.
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.
This sounds like unweighted interval scheduling (which is greedy):
- Skor January 09, 2015Order 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