Interview Question Software Engineer / Developers
Country: United States
How does this approach sound like?
Assumptions:
- Meetings start at 8:00 AM and end at 6:00 pm (this can be changed to a 24 hour as well, but just for brevity).
- Meeting minimum time is 15 minutes, so that means each hour will have 4 divisions.
- 8 to 6 = 10 hours = 10 * 4 = 40 divisions total.
Now,
Assign each time slot a digit, alphabet, code, whatever... for now lets say a digit.
So if a meeting is scheduled from 10-10.30 am, so we'd add 9 and 10 into the HashSet.
(Logic: 8-8.15 = 1, 8.15 - 8.30 = 2, 8.30 - 8.45 = 3, ....... 10-10.15 and 10.15-10.30 = 9 and 10... and so on)
Now let's say someone tries to find a meeting from 10.15-10.45, we'll look for codes 10 and 11. The HashSet already has the entry 10, so that's a collision right there!
Time complexity to 'look up' = O(1), time complexity to add all the meetings from the arraylist = O(n).
Can't you just count how many meeting objects you have? Can't they all be in the same room? Maybe I don't understand the problem. We're not given information on the capacity of room and such.
Well if 2 meetings have overlapping times, then you need 2 rooms for them. But if they don't overlap, then 1 room suffice. So the question is about finding the maximum number of overlapping meetings at any given time.
Let's take an example to understand the question. I am not using long for start and end times, just using int for simplicity.
M1: 9-10
M2: 10-11
M3: 10:30-11
M4: 12-1
If you observe, total amount of conference rooms required are just 2 for all the meetings. That's because you can use the same room for M1 and M2, but since M3's start time is less than M2's (or other active meetings) end time, you will have to grep a new conf room. And as for M4, the meeting starts after all the 3 meetings are over. Hope that clarifies the question.
My solution was to sort the meetings by start times. As you iterate through the meetings, add the end times to the min-heap by key = end time. Then for each iteration, check if startTime of current meeting < extract-min(heap). If so, you will increment the counter for counting conference rooms.
Complexity will be O(nlogn). That's because the loop runs for n times and heap operation is O(logn). And sorting the input vector of conference rooms by start times takes O(nlogn). So, overall complexity is O(nlogn). I think this is optimal. It is a problem discussed in algorithms book of Eva Tardos (found it after interview)
Well, this took me much much longer than it should have, but here is my solution:
public struct Meeting
{
public long startTime;
public long endTime;
public Meeting(long sTime, long eTime)
{
startTime = sTime;
endTime = eTime;
}
}
public class Room
{
public List<Meeting> meetings;
public Room()
{
meetings = new List<Meeting>();
}
public bool try_schedule_meeting(Meeting meeting)
{
foreach (Meeting scheduledMeeting in meetings)
{
if ((meeting.startTime < scheduledMeeting.endTime) && (meeting.endTime > scheduledMeeting.startTime))
return false;
}
meetings.Add(meeting);
return true;
}
}
public class Scheduler
{
List<Room> rooms;
public Scheduler()
{
rooms = new List<Room>();
}
public List<Room> schedule_meetings(List<Meeting> meetings)
{
for(int i = 0; i < meetings.Count; ++i)
{
bool IsMeetingScheduled = false;
foreach(Room room in rooms)
{
if (room.try_schedule_meeting(meetings[i]))
{
IsMeetingScheduled = true;
break;
}
}
if(!IsMeetingScheduled)
{
Room newRoom = new Room();
newRoom.try_schedule_meeting(meetings[i]);
rooms.Add(newRoom);
}
}
return rooms;
}
}
static void Main(string[] args)
{
List<Meeting> meetings = new List<Meeting>();
Meeting m1 = new Meeting(8, 10);
Meeting m2 = new Meeting(9, 10);
Meeting m3 = new Meeting(10, 11);
Meeting m4 = new Meeting(8, 12);
meetings.Add(m1);
meetings.Add(m2);
meetings.Add(m3);
meetings.Add(m4);
Scheduler s = new Scheduler();
List<Room> rooms = s.schedule_meetings(meetings);
Console.WriteLine("Number of Rooms: {0}", rooms.Count);
int i = 1;
foreach(Room r in rooms)
{
Console.WriteLine("Room: {0}", i++);
int j = 1;
foreach(Meeting m in r.meetings)
{
Console.WriteLine("Meeting: {0}", j++);
Console.WriteLine("\tStart: {0}", m.startTime);
Console.WriteLine("\t End: {0}", m.endTime);
}
Console.WriteLine();
}
}
Test Output:
Number of Rooms: 3
Room: 1
Meeting: 1
Start: 8
End: 10
Meeting: 2
Start: 10
End: 11
Room: 2
Meeting: 1
Start: 9
End: 10
Room: 3
Meeting: 1
Start: 8
End: 12
This one is a brute force algorithm.
Also, why are you returning back after this check:
{
if ((meeting.startTime < scheduledMeeting.endTime) && (meeting.endTime > scheduledMeeting.startTime))
return false;
}
You are not iterating through each scheduled meeting. I think my solution so far O(nlogn) time seems to be better (see above)
You would return because if the meeting to be scheduled overlaps with a meeting previously found in that room, you wouldn't be able to schedule the new meeting in that room as it conflicts with an existing meeting and would have to move to the next room.
Here's the c++ version:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool timeLess(int a, int b)
{
int d = abs(a) - abs(b);
if (d == 0)
return a < b;
return d < 0;
}
struct Meeting {
int start;
int end;
};
int main(int argc, char**argv)
{
Meeting allMeetings[] = {
{1, 3},
{2, 4},
{6, 7},
{4, 6},
{5, 6}
};
int N = sizeof(allMeetings) / sizeof(allMeetings[0]);
vector<int> times;
for (int i = 0; i < N; i++) {
times.push_back(allMeetings[i].start);
times.push_back(-allMeetings[i].end);
}
sort(times.begin(), times.end(), timeLess);
int rooms = 0;
int maxRooms = 0;
for (int i : times) {
if (i > 0) {
// hit the meeting start time
rooms++;
if (rooms > maxRooms)
maxRooms = rooms;
}
else {
// hit the meeting end time
rooms--;
}
}
cout << "max number of rooms needed is " << maxRooms << endl;
}
Actually this problem is a variation to question 15551781, for which there exists Marzullo algorithm.
Complexity should be o(n*log(n)) + o(n*m) , by which n is the number of meetings, and m is the max meeting room number.
package com.cc.question;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
class Mtg
{
long startTime;
long endTime;
Room room;
public Mtg(long startTime, long endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
};
class Room{
boolean isOccupied = false;
Mtg occupiedMtg = null;
}
public class MtgScheduler implements Comparator<Mtg>{
private Mtg[] meetings;
private List<Room> mtgRooms = new ArrayList<>();
public MtgScheduler(Mtg[] meetings) {
this.meetings = meetings;
}
public int minMtgRoomNum() {
//sort meetings by startTime
Arrays.sort(meetings,this);
//iterate the meetings by start time, and schedule each of them
for(int i=0;i < meetings.length;i++) {
Mtg meeting = meetings[i];
Room room = findVacancy(meeting);
if(room == null) {
room = allocateNewRoom();
}
room.isOccupied = true;
room.occupiedMtg = meeting;
}
return mtgRooms.size();
}
public Room allocateNewRoom() {
Room room = new Room();
mtgRooms.add(room);
return room;
}
//depend upon the meeting, release any room if the meeting is over; then find the vacancy;
public Room findVacancy(Mtg meeting) {
Room vacancyRoom = null;
for(int i=0;i<mtgRooms.size();i++) {
Room room = mtgRooms.get(i);
if(room.isOccupied) {
if(room.occupiedMtg.endTime<= meeting.startTime) // release the room if the meeting is over
{
room.isOccupied = false;
room.occupiedMtg = null;
}
}
}
for(int i=0;i<mtgRooms.size();i++) {
Room room = mtgRooms.get(i);
if(room.isOccupied == false) {
vacancyRoom = room;
break;
}
}
return vacancyRoom;
}
@Override
public int compare(Mtg o1, Mtg o2) {
if(o1 == null || o2 == null)
return 0;
if(o1.startTime< o2.startTime)
return -1;
else if (o1.startTime> o2.startTime) {
return 1;
}
return 0;
}
}
// Test Case class
package com.cc.question;
import junit.framework.Assert;
import org.junit.Test;
public class SchedulerTest {
@Test
public void testScheduler() {
Mtg[] meetings = {new Mtg(7, 10),new Mtg(11, 13), new Mtg(9, 11), new Mtg(11, 14), new Mtg(12, 13),new Mtg(13, 15),new Mtg(15, 16)};
MtgScheduler scheduler = new MtgScheduler(meetings);
int minMtgRoomNum = scheduler.minMtgRoomNum();
Assert.assertEquals(minMtgRoomNum, 3);
}
}
How does this approach sound like?
Assumptions:
- Meetings start at 8:00 AM and end at 6:00 pm (this can be changed to a 24 hour as well, but just for brevity).
- Meeting minimum time is 15 minutes, so that means each hour will have 4 divisions.
- 8 to 6 = 10 hours = 10 * 4 = 40 divisions total.
Now,
Assign each time slot a digit, alphabet, code, whatever... for now lets say a digit.
So if a meeting is scheduled from 10-10.30 am, so we'd add 9 and 10 into the HashSet.
(Logic: 8-8.15 = 1, 8.15 - 8.30 = 2, 8.30 - 8.45 = 3, ....... 10-10.15 and 10.15-10.30 = 9 and 10... and so on)
Now let's say someone tries to find a meeting from 10.15-10.45, we'll look for codes 10 and 11. The HashSet already has the entry 10, so that's a collision right there!
Time complexity to 'look up' = O(1), time complexity to add all the meetings from the arraylist = O(n).
int minConfRoomsII(vector<meeting*> endmeet)
{
int current = 1;
vector<meeting*> startmeet(endmeet);
sort(endmeet.begin(), endmeet.end(), endcomp);
sort(startmeet.begin(), startmeet.end(), startcomp);
int maxcount = 1;
int i = 1, j = 0;
while(i < startmeet.size() && j < endmeet.size())
{
if(startmeet[i]->start < endmeet[j]->end)
{
current += 1;
i++;
maxcount = max(current, maxcount);
}
else
{
current -= 1;
j++;
}
}
return maxcount;
}
@animageofmine
This is in-fact a 20-min question. You just need to increase the number of room when start time of next meeting is before end-time of previous meeting and keep track of global max.
Suppose meeting structure is: meet (ST, ET) (ST: start time and ET: end time)
1. sort the meetings in order of start time
2. initially, number of meeting room rooms=1, max_rooms=1;
3.
from (j=0,i=1; i<n;i++) (when order starts from 0) {
while (meeting[i].ST < meeting[j].ET)
{ rooms++; i++;}
if (rooms > max_rooms)
max_rooms = rooms;
j++;
}
return max_rooms;
We do not require sorting at all. No need. Using sorting, things are incredibly easy. There is a neat and fun way of solving this.
/*
If the precision of the meetings are in integers
that is 2:30 to 3:30, then we can simply quantize
the minimal value which is 30 mins meeting time min.
Then the problem becomes finding the time quantum of 30 mins
which contains the maximum overlap of meetings.
We encode the time 11:30 as 11.5 -> 115 and take a 5 as 30 mins.
This can easily be done.
This can be solved in Theta(N). Observe:
*/
def find_min_rooms( list_of_meetings ) {
// simply carry on a counter ...
counter = dict()
for ( meeting : list_of_meetings ){
for ( s = meeting.start * 10 ; s <= meeting.end * 10 ; s+= 5 ){
counter[s] += 1 ?? counter[s] = 1
}
}
#(m,M) = minmax( counter.values )
return M
}
- Anonymous February 15, 2014struct Meeting { int start; int end; Meeting(int s, int e) {start=s; end=e;} }; bool mysortfunc(Meeting a, Meeting b) { return a.end<b.end; } int compute_min_confrooms(vector<Meeting>& meetings) { // sort meetings w.r.t. their end times sort(meetings.begin(),meetings.end(),mysortfunc); int peak = 0; queue<Meeting> Q; Q.push(meetings[0]); for(int i=1; i<meetings.size(); i++) { while(!Q.empty() && Q.front().end < meetings[i].start) { Q.pop(); } Q.push(meetings[i]); peak = max(peak, (int)Q.size()); } return peak; }