Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Hi nikolay.d,
Please explain the logic behind your code.
That would make it easier to understand it.
Thanks! :)
@Pratik, by sorting absolute values, you are putting all start & end events in chronological order.
Now when you loop, if you encounter a positive number, it means a meeting is starting, you need an extra room so +1. If you encounter a negative number, it means a meeting has finished, you release a room so -1.
At the end of the loop, take max number of meeting room you need at any time to be results.
- Sort the interval by ascending order of start time (e.g. {2,5}, {3,4}, {6,10} ...}
- Maintain a min heap priority queue, sorted by ascending order of finish time (e.g. when first two timeslots are added, {3,4} is top of the heap)
- Keep track of the size of the queue. The maximum size of the queue at any point is our final answer.
- At time of adding next element if its start time is smaller than priority queue's top element's end time, then we need to add an element in priority queue (and update max size if necessary)
- At time of adding next element if its start time is greater than priority queue's top element's end time, then pop all elements from the priority queue, whose end time is smaller than next elements's start time. Then add the next element.
class Event{
int time;
EventType type;
Event(int time, EventType type){
this.time = time;
this.type = type;
}
}
enum EventType{
int cardinality;
EventType(int cardinality){
this.cardinality = cardinality;
}
END(0),BEGIN(1);
}
public int getMinimumRooms(List<Interval> slots){
if(slots == null || slots.size() <1){
return 0;
}
List<Event> events = new ArrayList<Event>();
for(Interval interval:slots){
events.add(new Event(interval.getStartTime(), EventType.BEGIN);
events.add(new Event(interval.getEndTime(), EventType.END);
}
Collections.sort(events,new Comparator<Event>(){
public int compareTo(Event one , Event two){
if(one.time == two.time){
return one.cardinality - two.cardinality;
}
return one.time - two. time;
}});
int roomCount = 0;
int max =0;
for(Event anEvent:events){
if(event.type == BEGIN){
++roomCount;
}else{
--roomCount;
}
if(max<roomCount){
max = roomCount;
}
}
return max;
}
First, sort the times by end time in a list L. Now, start from the first interval, do interval scheduling to see how many intervals are valid with the first interval.
Remove such intervals and put into one bucket.
Now with the first interval left in L, do the same thing. repeat this process until there are no intervals left in L. The number of buckets generated is the number of rooms needed.
We know that the minimum number will be found at the point of highest overlap between schedules. Similar to my answer to the question for finding whether schedules overlap, you can keep track of how many times any one hour slot is used, and simply find the highest slot.
in python:
def find_min_req_rooms(sched_list):
slots = [0 for x in range(0,24)]
for sched in sched_list:
for hour in range(sched[0],sched[1] + 1):
slots[hour] += 1
max = 0
for x in slots:
if x > max:
max = x
return max
The runtime here is O(nm) where n is the total number of schedule entries and m is the largest number of hours in any schedule entry.
- sort the timeslots from in ascending order
- create an empty array int[24] representing 24 hours of the day
- iterate over timeslots filling the array for that hour with [1] if only 1 timeslot has that hour inside it's interval otherwise fill with N if N timeslots intersects on that hour
at the end pick MAX value of array.
- max value will be your min. number of rooms.
- if it only contains intervals from the same calendar day
- if hourly granularity is good enough solution
and you don't need to sort the array (that would make it O(n*log(n))), because you don't use the sortedness of the array later, so without sorting you are done in O(n) [assuming that finding the maximum of the 24 slots is O(1) as it's independent from n]
var meetings = [
{ start: 2, end: 5},
{ start: 3 , end: 4},
{ start: 5, end :9},
{ start: 2, end: 3},
{ start:4, end:8}
];
function GetRoomCount(meetings){
if(meetings.length<1){
return 0;
}
var roomCount =0;
var current;
for(i=0;i<meetings.length-1;i++){
if(meetings[i]!=null){
current = meetings[i];
for(j=0;j<meetings.length;j++){
if(i!==j){
if(meetings[j]!==null){
if((meetings[j].end <= meetings[i].start) || meetings[j].start >= meetings[i].end){
if(meetings[j].start< meetings[i].start){
tt = meetings[j].start;
meetings[i].start =tt;
}
if(meetings[j].end > meetings[i].end){
tt= meetings[j].end;
meetings[i].end = tt;
}
meetings[j]= null;
}
}
}
}
}
}
console.log(meetings);
//console.log(hours);
return meetings.filter(function(a){ return a!==null; }).length;
}
console.log("No. of rooms required = " + GetRoomCount(meetings));
for(i =0 ;i<meetings.length;i++){
if(meetings[i]!=null){
console.log('Room busy from : ' + meetings[i].start + ' to ' + meetings[i].end);
}
}
var meetings = [
{ start: 2, end: 5},
{ start: 3 , end: 4},
{ start: 5, end :9},
{ start: 2, end: 3},
{ start:4, end:8}
];
function GetRoomCount(meetings){
if(meetings.length<1){
return 0;
}
var roomCount =0;
var current;
for(i=0;i<meetings.length-1;i++){
if(meetings[i]!=null){
current = meetings[i];
for(j=0;j<meetings.length;j++){
if(i!==j){
if(meetings[j]!==null){
if((meetings[j].end <= meetings[i].start) || meetings[j].start >= meetings[i].end){
if(meetings[j].start< meetings[i].start){
tt = meetings[j].start;
meetings[i].start =tt;
}
if(meetings[j].end > meetings[i].end){
tt= meetings[j].end;
meetings[i].end = tt;
}
meetings[j]= null;
}
}
}
}
}
}
console.log(meetings);
//console.log(hours);
return meetings.filter(function(a){ return a!==null; }).length;
}
console.log("No. of rooms required = " + GetRoomCount(meetings));
for(i =0 ;i<meetings.length;i++){
if(meetings[i]!=null){
console.log('Room busy from : ' + meetings[i].start + ' to ' + meetings[i].end);
}
}
I am not providing code for now. just the algorithms.
Think of this as knapsack problem. How many meeting you can assign to a room.and since it is a knapsack problem, we should maximize the meetings for the room. Now for the remaining meeting, we do knapsack problem again until there is no more meeting. So the code is the following
int room = 0;
while(meetings in the list is not empty){
knapsack(meetings in the list);
room++;
}
now, how to implement knapsack is something that we should focus. dynamic programming is generally the solution to it.
def assignMeetingToRoom(meeting):
list = [meeting[0]]
meeting.remove(meeting[0])
for i in meeting:
lasttime = list[len(list)-1][0]
if i[1] >= lasttime:
list.append(i)
meeting.remove(i)
def NumberOfMeetingRoom(meeting):
# assuming that meeting is a list that contains a list of meeting
# where each meeting contains a list of two item, namely, ending time
# and starting time
# i.e. [[e1, s1], [e2, s2], [e3, s3]]
meeting.sort()
room = 0
while len(meeting) != 0:
assignMeetingToRoom(meeting)
room += 1
return room
public static int FindMinimumMeetingRoomsReqd(int[,] meetingtimes)
{
if(meetingtimes == null || meetingtimes.Length == 0)
{
return default(int);
}
Dictionary<int,int> slots = new Dictionary<int,int>();
for(int i = 0 ; i < meetingtimes.Length /2 ; i++)
{
if(!slots.ContainsKey(meetingtimes[i,0]))
{
slots.Add(meetingtimes[i, 0], 1);
}
else
{
slots[meetingtimes[i, 0]] += 1;
}
}
IEnumerable<KeyValuePair<int, int>> result = slots.OrderByDescending(key => key.Value);
KeyValuePair<int,int> Top = result.ElementAt(0);
Console.WriteLine("Min number of rooms : {0}, slot with highest overlaps is at hour 2: {1} - {2}", Top.Value, Top.Key, Top.Key+1);
return Top.Value;
}
import java.util.*;
class TimeSlot implements Comparable<TimeSlot>
{
int start,end;
TimeSlot(int start,int end)
{
this.start=start;
this.end=end;
}
//@Overrride
public int compareTo(TimeSlot elem)
{
if(this.start>elem.start)
return 1;
else if(this.start<elem.start)
return -1;
else
return 0;
}
}
class CountingRooms
{
static int noRooms(TimeSlot[] arr)
{
Arrays.sort(arr);
int maxOverlap=1;
int overlap=0;
for(int i=0;i<arr.length-1 && overlap+i<arr.length-1 ;++i)
{
int j=i+1;
TimeSlot temp=arr[j];
TimeSlot present=arr[i];
overlap=0;
while(temp.start<present.end && j<arr.length)
{
temp=arr[j];
overlap++;
++j;
System.out.println("in overlap");
}
if(overlap+1>maxOverlap)
{
maxOverlap=overlap+1;
}
}
return maxOverlap;
}
public static void main(String[] st)
{
TimeSlot[] arr={new TimeSlot(2,5),new TimeSlot(4,9)};
System.out.println("total no of rooms neede: "+noRooms(arr));
}
}
1. sort by start time
2. keep a min heap to maintain end times
#include<iostream>
#include<vector>
#include<functional>
#include<queue>
using namespace std;
struct Meeting {
int start;
int end;
Meeting() : start(-1), end(-1) {}
Meeting(int start, int end) : start(start), end(end) {}
};
bool myCompare(Meeting a, Meeting b) {
return a.start <= b.start;
}
// time complexity = O(nlogn + nlogn) = O(nlogn)
int GetMinMeetingRooms(vector<Meeting>& times) {
if (times.size() <= 1) {
times.size();
}
std::sort(times.begin(), times.end(), myCompare);
priority_queue<int, vector<int>, greater<int> > pq;
int minMeetings = 1;
int j = 0;
for (int i = 0; i < times.size() - 1; ++i) {
j = i + 1;
if (times[j].start >= times[i].end) {
continue;
} else {
if (!pq.empty() && pq.top() <= times[j].start) {
pq.pop();
} else {
minMeetings++;
pq.push(times[i].end);
}
}
}
return minMeetings;
}
This will work:
int findMinMeetingRooms(schedulesList):
sort schedulesList by startTime
int lastEndTime = schedules[0].endTime
int maxOverlap = 1
int currentOverlap = 1
for i = 1 -> schedules.size() - 1:
boolean overlaps = ((schedules[i].startTime - lastEndTime) < 0)
if (overlaps):
currentOverlap += 1
else:
currentOverlap = 1
if (currentOverlap > maxOverlap):
maxOverlap = currentOverlap
lastEndTime = schedules[i].endTime
return maxOverlap
This will work:
int findMinMeetingRooms(schedulesList):
sort schedulesList by startTime
int lastEndTime = schedules[0].endTime
int maxOverlap = 1
int currentOverlap = 1
for i = 1 -> schedules.size() - 1:
boolean overlaps = ((schedules[i].startTime - lastEndTime) < 0)
if (overlaps):
currentOverlap += 1
else:
currentOverlap = 1
if (currentOverlap > maxOverlap):
maxOverlap = currentOverlap
lastEndTime = schedules[i].endTime
return maxOverlap
Here is C++ version of answer.
Running time of this algorithm is O(nlogn) due to the sorting.
#include<vector>
#include<iostream>
using namespace std;
struct Schedule{
int start;
int end;
Schedule():start(-1), end(-1){}
Schedule(int s, int e):start(s), end(e){}
};
struct Room {
Schedule last;
Room(){}
Room(Schedule s):last(s){}
};
int count_meeting_rooms (Schedule* input, int len)
{
int i = 0, r= 0;
quicksort(input, 0, len-1);
print_array(input, len);
vector<Room>rooms;
for (i = 0; i < len; i ++)
{
if (rooms.size() == 0)
{
rooms.push_back(Room());
}
for (r = 0; r < rooms.size(); r++)
{
if (rooms[r].last.start == -1 || rooms[r].last.end <=input[i].start)
{
rooms[r].last = input[i];
break;
}
}
if (r >= rooms.size())
{
rooms.push_back(Room(input[i]));
}
}
return rooms.size();
}
If the time is in integer and is military time, then we can use an array to keep track any overlaps (back to back not consider overlap)
public int findRooms(int[] startTime, int[] endTime)
{
int maxRoom = 1;
int[] sch = new int[24];
for(int a=0;a<startTime.length;a++){
for(int i=startTime[a];i<endTime[a];i++)
{
sch[i]++;
maxRoom = Math.max(maxRoom,sch[i]);
}
}
return maxRoom;
}
write a function that calculates the minimum number of meeting rooms that can accommodate given schedules
input: same
output: # of rooms
Also back to back events are allowed e.g. {2,5} {5,9} correct o/p:1
#include <iostream>
#include <algorithm>
using namespace std;
struct Schedule{
int start;
int end;
};
// Compares two intervals according to their staring time.
// This is needed for sorting the intervals using library
bool compareInterval(Schedule i1, Schedule i2)
{
return (i1.start < i2.start);
}
int count_meeting_rooms(Schedule* input, int len)
{
// sort the intervals in increasing order of start time
sort(input, input + len, compareInterval);
// rooms_needed indicates number of meeting rooms needed at a time
int rooms_needed = 1, result = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process all events in sorted order
while (i < len && j < len)
{
// If next event in sorted order is start time, increment count of
// rooms needed
if (input[i].start < input[j].end)
{
rooms_needed++;
i++;
if (rooms_needed > result) // Update result if needed
result = rooms_needed;
}
else // Else decrement count of rooms needed
{
rooms_needed--;
j++;
}
}
return result;
}
int main()
{
Schedule arr[] = { { 2, 5 }, { 5, 9 }, { 3, 4 } };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The Number of meeting rooms required to accomodate the schedules is - " << count_meeting_rooms(arr, n)<<endl;
return 0;
}
Some sorting based solutions here have a bug.
We need to pull all instances of given time before making a final decision on current number. E.g. if at the same time 2 openings and 1 closings the total increment should be +1. But if in your algorithm openings come before closings we'll get +2!
Concrete example: {1, 2}, {2, 3}, {2, 4}. Since quick sort is not stable it could be the case than we get 1O, 2O, 2O, 2C, 3C, 4C. I use "O" to denote opening, "C" to denote closing instead of playing with sign. Your algorithm returns 3, but the correct answer is 2.
In other word algorithm should process closings before openings if they come at the same time.
- Put all numbers in a simple array but the end time with a negative sign
- Sort the array by the absolute value of elements
- Do a simple for loop, keeping a current value of number of currently scheduled meetings; if the current number is positive - increase it by 1, otherwise - decrease by 1
- Keep track of its maximum value - that's the answer
C++:
- nikolay.d March 24, 2015#include <iostream> #include <cstdlib> using namespace std; int compare (const void *a, const void *b) { int aa = *(int*)a; int bb = *(int*)b; if (aa < 0) aa = -aa; if (bb < 0) bb = -bb; if (aa == bb) { return *(int*)a - *(int*)b; } return aa-bb; } int main() { int a[] = {5,-9,2,-5,3,-4}; int cur = 0, max = 0; qsort(a, sizeof(a)/sizeof(int), sizeof(int), compare); for (int i : a) { if (i>0) { cur++; if (cur>max) max = cur; } else { cur--; } } cout << max; }