Design a meeting scheduler:
How you will identify conflicting meetings?
How you will design data structure and supporting algorithm so that System will suggest Best Available Meeting time considering the fact that many folks on the invite might be in different geography.
Approach: Using Array and Binary search
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).
Assert the before-meeting's start_time + duration does not exceed the new meeting's start_time.
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.
Approach 2: using BST
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.
Useful Discussion:------------------
http://stackoverflow.com/questions/15150188/amazon-interview-design-meeting-scheduler
https://www.careercup.com/question?id=15555745
http://www.careercup.com/question?id=5720778041458688
How you will identify conflicting meetings?
How you will design data structure and supporting algorithm so that System will suggest Best Available Meeting time considering the fact that many folks on the invite might be in different geography.
Approach: Using Array and Binary search
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).
Assert the before-meeting's start_time + duration does not exceed the new meeting's start_time.
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.
Approach 2: using BST
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.
Useful Discussion:------------------
http://stackoverflow.com/questions/15150188/amazon-interview-design-meeting-scheduler
https://www.careercup.com/question?id=15555745
http://www.careercup.com/question?id=5720778041458688
No comments:
Post a Comment