Amazon Interview- Design Meeting Scheduler [closed]

Question

Lately, I took an interview. I was asked to design a meeting scheduler, just like in the Microsoft outlook calendar or the gmail calendar. I proposed that I will create an array of 48 for each day. Every 30 min representing the array entry.

I have to make sure that the next appointment does not collide with a previous meeting.

My solution works fine but it wastes too much memory.

Can anyone please tell me how do I find a better solution to detect collision for meetings.

I don't know all the meetings at the beginning. They will be added randomly later.

Thanks,

Answer 1

Start with an empty list of meetings, each with a start_time and duration. We will maintain a sorted list of meetings by start_time.

To add a meeting to the list, find where it belongs in the list by performing a binary search. Once you find the index, perform two checks to avoid a collision; consider the meetings immediately before and after the to-be-inserted meeting (if they exist).

1. Assert the before-meeting's start_time + duration does not exceed the new meeting's start_time.
2. Assert the new meeting's start_time+duration does not exceed the after-meeting's start_time.

If the assertions are satisfied, add the meeting to the list.

This add operation takes O(log(list_size)) time.

Note: This approach assumes that adding a meeting with an overlap is an invalid operation. If overlaps are allowed to exist, you would have to check beyond the meetings immediately preceding/subsequent the new meeting.

Answer 2

We can have a Tree structure (BST) for storing the requests (Request object: start time/end time/date/priority etc.). By doing so, add/delete/search/update operations can be achieved by O(height_of_tree). If we use a balanced tree, we can get the optimized running time. i.e. O(log n) for each of the above mentioned operations.

This approach is better than the sorted list approach as the list is backed by an fixed sized array in case of ArrayList which takes O(n) for copying the elements from old array to new array. If we use a linkedlist, binary search is not possible.

Comments welcome!

Answer 3

Here is my solution which inserts using binary search

public class MeetingScheduler {

    static class Meeting implements Comparable<Meeting> {
        Date startTime;
        Date endTime;
        int duration;

        public static final int MINUTE = 60000;

        //duration in minutes
        Meeting(Date startTime, int duration) {
            this.startTime = startTime;
            this.duration = duration;
            this.endTime = new Date(startTime.getTime() + (MINUTE * duration));

        }

        @Override
        public int compareTo(Meeting o) {
            if (this.endTime.compareTo(o.startTime) < 0) {
                return -1;
            }//end time is before the other's start time
            if (this.startTime.compareTo(o.endTime) > 0) {
                return 1;
            }////start time is after the other's end time
            return 0;
        }

        @Override
        public String toString() {
            return "meeting {" +
                    "from " + startTime +
                    ", minutes=" + duration +
                    '}';
        }
    }

    private List<Meeting> meetings = new ArrayList<Meeting>();

    public Meeting bookRoom(Meeting meeting) {

        if (meetings.isEmpty()) {
            meetings.add(meeting);
            return null;
        } else {
            int pos = -Collections.binarySearch(meetings, meeting);
            if (pos > 0) {
                meetings.add(pos-1, meeting);
                return null;
            } else {
                return meetings.get(-pos);
            }
        }
    }

    public List<Meeting> getMeetings() {
        return meetings;
    }

    public static void main(String[] args) {
        MeetingScheduler meetingScheduler = new MeetingScheduler();

        Meeting[] meetingsToBook = new Meeting[]{
                //October 3rd 2014
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 15, 00), 15),
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 16, 00), 15),
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 17, 00), 60),
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 18, 00), 15),
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 14, 50), 10),
                new Meeting(new Date(2014 - 1900, 10 - 1, 3, 14, 55), 10)
        };

        for (Meeting m : meetingsToBook) {
            Meeting oldMeeting = meetingScheduler.bookRoom(m);
            if (oldMeeting != null) {
                System.out.println("Could not book room for " + m + " because it collides with " + oldMeeting);
            }
        }

        System.out.println("meetings booked: " + meetingScheduler.getMeetings().size());

        for (Meeting m : meetingScheduler.getMeetings()) {
            System.out.println(m.startTime + "-> " + m.duration + " mins");
        }

    }
}