Amazon Interview Question
Software Engineer / DevelopersTeam: AWS
Country: United States
package com.test;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import static com.test.MeetingScheduler.TimeSlot.createNewSlot;
public class MeetingScheduler {
private Map<TimeSlot, Meeting> meetings = new HashMap<>();
public static void main(String[] args)
{
MeetingScheduler scheduler = new MeetingScheduler();
System.out.println(scheduler.add(new Meeting("First meeting"), createNewSlot("03/01/2013 08:00", "03/01/2013 08:30")));
System.out.println(scheduler.add(new Meeting("Second meeting"), createNewSlot("03/01/2013 08:30", "03/01/2013 09:30")));
System.out.println(scheduler.add(new Meeting("Third meeting"), createNewSlot("03/01/2013 07:30", "03/01/2013 08:15")));
System.out.println(scheduler.add(new Meeting("Fourth meeting"), createNewSlot("03/01/2013 09:15", "03/01/2013 09:45")));
scheduler.printAllMeetings();
}
private void printAllMeetings() {
System.out.println(meetings);
}
public boolean add(Meeting meeting, TimeSlot timeSlot)
{
for(TimeSlot slot : meetings.keySet())
{
if (slot.collidesWith(timeSlot))
{
return false;
}
}
meetings.put(timeSlot, meeting);
return true;
}
public static class Meeting
{
private String title;
public Meeting(String title)
{
this.title = title;
}
public String toString()
{
return title;
}
}
public static class TimeSlot
{
private Date beginDate;
private Date endDate;
public TimeSlot(Date beginDate, Date endDate) {
this.beginDate = beginDate;
this.endDate = endDate;
}
public boolean collidesWith(TimeSlot timeSlot) {
if (timeSlot.beginDate.getTime() > beginDate.getTime()
&& timeSlot.beginDate.getTime() < endDate.getTime())
{
return true;
}
if (timeSlot.endDate.getTime() > beginDate.getTime()
&& timeSlot.endDate.getTime() < endDate.getTime())
{
return true;
}
return false;
}
public static TimeSlot createNewSlot(String beginDate, String endDate)
{
SimpleDateFormat format = new SimpleDateFormat("MM/dd/yyyy hh:mm");
try {
return new TimeSlot(format.parse(beginDate), format.parse(endDate));
} catch (ParseException e) {
e.printStackTrace();
}
return null;
}
public String toString()
{
return "Begin Date = " + beginDate.toString() + ", End Date = " + endDate.toString();
}
}
}
Umm. Why not keep an interval tree? It can detect collisions etc. too.
Not sure why would anyone mention hashtable as there can have a partial interval overlap.
Yes - interval tree or segment tree will perform better in this case.
Have to develop the tree according to minimum time interval chosen.
Insertion and look up for collision will also take o(log n) time.
Now to get the all appointments for an interval - we can design in such a way that each node will hold number of appointments present in that interval. So, all appointments for a day can be retrieve easily - we have take the list of root node i.e. [0-47].
Since we already know there are no overlaps in the tree, we do not need complex data structure. Just have both start-time and end-time in the nodes, construct BST with start-time as the key.
To check overlap for new meeting request, search BST for node with start time just less than the start time of new meeting start time. End time of that node should not exceed start time of new meeting. Again search BST for node with start time just greater than start time of new meeting start time. Start time of that node should not be less than start time of new meeting. If both conditions are satisfied, there is no overlap. Insert the new meeting request node in the BST.
"Collisions" should be a give-away. What data-structure has collisions and does not waste memory? Answer- an open hashtable. The key can be whatever minimum interval you'd like to maintain for an appointment. You can create the appointment object for each appointment and set the value for each time key you'd like the appointment to occupy. A lookup on that time key would give you the pointer to the appointment and attempting to create an appointment in an allocated key would cause a collision. Further, since it's an open hash, you allocate a bucket for all minimum-intervals in a day, but don't have to allocate an appointment object up front like you would with the array implementation.
If by interval you mean the total minutes, then I guess you would have to create a chain of all appointments for that time interval. Also you will have to create a separate such hashtable for each day.
If the interval is the time frame, then you need to have a way to see if the given time interval collides with any other appointment times interval. k-d tree provides such a structure to find an interval with which a given key collides.
I agree with the idea of using hashtable. The hashtable will use the {year+month+date} as the key and the value as a k-d tree of the intervals. So if the interval for which you are trying to create the appointment overlaps with an interval in the kd tree, you will get the collision.
I wouldn't use a hash table because it would be difficult to get a list of appointments for a particular day, which is an important and common function of a calendar. You would have to lookup every possible hash value (there 1440 minutes in a day) which is incredibly inefficient.
Also, how would you find collisions with a hash table? You need to know the start and end of an appointment to detect collisions, and a hash table could only key on one or the other. Even if you could key on both (somehow), the start and/or end times would have to line up exactly. A hash lookup would miss a collision between a 1pm-2pm appointment and a 1:30pm-2:30pm appointment.
How about interval trees? They're simple BST's (key being starting time of an appointment) but store time range and the max ending time seen in the sub-tree at every node to improve detecting collisions. Search & insertion will be logarithmic.
If a root has start and end time as start1, end1 and maxend (for the subtree) and a new time interval (start2, end2) has to be inserted condition for collision check will be:
if(start2 >= maxend)
// No collision in this sub-tree
else // Collision in sub-tree
if (end2 <= start1 || start2>end1) // No collision with this node's interval
else
{
// Collision
}
I will use a resizeable array. Because we don't know how many meetings can there be. I will add each new meeting interval in sorted order. Because our array will be sorted each insertion will take logn time . All the entries will be in pair , so the time at even position will be starting time of a meeting and the next value will be the ending time of that meeting. Using this information we can detect if there will be collision or not.
If one wish to store all possible meetings , he will have to use hashtable but I think the question demands not to store them.
I believe you had been asked to create a 'calendar memo' utility.
You could make the 'Memo' class subscribe to a custom publisher that would invoke a specific method in the Memo class.
The publisher will have four lists. one for the year[as large your system needs], 1 for month[max size 12], 1 for date [max size 30], 1 for time [max size 24 'hours']. (you may want to split up the time list for minutes and hours). The lists will contain references ordered by the designation of the list.
The publisher will invoke an 'alarm' method in Memo depending on its subscription request.
The publisher instance will repeatedly request system time. First polling through the year list. If found a match then looking for the matched items in the months list then further through the days list and so on. Once you find a match you invoke the 'alarm' method for those instances of 'Memo's' .
The Memo class can then contain code to acquire information pertaining to that date and time.
The idea is that, no matter how many memos you have. you wouldn't need to cycle through all of them for every minute. You progressively cut down the size of the memos you need to handle as you go through the lists. In addition since the lists are ordered, you don't need to iterate through the whole lists.
Hope this helps and the design makes sense.
Feel free to point out enhancements or changes.
:-D
Also, one could expand on this structure to make it distributed in nature where many clients could push memos into the cloud.
Since Date implements Comparable every person can have a list of 'busy' dates. This way the meeting duration doesn't have to be constrained for 30 min (or whatever slot length you have chosen)
Given a date and list of persons, check if that date collides with existing 'busy' dates
for(Person p : personsRequiredForMeeting)
{
for(Slot busySlot : busySlots)
{
if(meetingRequestSlot.getStartTime() >= busySlot.getStartTime() &&
meetingRequestSlot.getStartTime() >= busySlot.getStartTime())
{
return false;
}
}
}
addMeetingRequestSlot(personsRequiredForMeeting);
return true;
correction: if(meetingRequestSlot.getStartTime() >= busySlot.getStartTime() &&
meetingRequestSlot.getEndTime() <= busySlot.getEndTime())
Use bits of an int for showing 30mins. One int will have 32 bits so with one integer value we can represent 16 hours when consider one bit as 30min. So for representing one day, we need 2 integer values or 64bit one int. This way we can finish it using only one bit and to find a free meeting, simply & it with original int. If it is free and scheduled or it with original value and update it.
How about something like this:
1) An array of 1440 minutes for the whole day
2) Each time a meeting is scheduled fill the minutes with 1 from the start of the meeting to the (n-1)th minute of the meeting.
3) Mark the nth minute as -1 to denote that this is an end
This is simply to allow a meeting to be scheduled when another ends at the same minute.
e.g 1pm to 1.15pm (Meeting1), Meeting 2 should be allowed at 1.15pm to 2pm.
Here is the code I wrote to design; (Appreciate any feedback / comments)
public class Calendar {
static int time [] = new int[1440];
public static void main(String args[]){
String s[] = {"15:30","1:30","1:15","15:00"};
String e[] = {"18:35","13:28","1:30","15:29"};
System.out.println(scheduler(s, e));
}
public static int calculateMinute(int hour, int minute){
return hour*60+minute;
}
public static boolean timeClashChecker(int start, int end){
for(int i=start;i<=end;i++){
if(i==end){
time[i] = -1;
}
else if(time[i]==1){
return false;
}
else if(time[i]==-1){
time[i]=1;
}
else{
time[i]=1;
}
}
return true;
}
public static int parser(String time){
String [] timeParts = time.split(":");
int hour = Integer.parseInt(timeParts[0].trim());
int minute = Integer.parseInt(timeParts[1].trim());
return calculateMinute(hour,minute);
}
public static boolean scheduler(String start[], String end[]){
for(int i=0;i<start.length;i++){
int startMeeting = parser(start[i]);
int endMeeting = parser(end[i]);
boolean result = timeClashChecker(startMeeting,endMeeting);
if(result == false){ //clash check
return false;
}
}
return true;
}
}
Steps:
1) Create a minute array of 1440
2) When a meeting is requested to be scheduled (1.30pm to 2pm), find the minutes
and update the n-1 minutes of the meeting with 1 in the minute array
3) The end of the meeting's minute needs to be -1 to avoid a clash with any meeting starting
when this ends; 2pm.
Would appreciate feedback on the following design:
public class Calendar {
static int time [] = new int[1440];
public static void main(String args[]){
String s[] = {"15:30","1:30","1:15","15:00"};
String e[] = {"18:35","13:28","1:30","15:29"};
System.out.println(scheduler(s, e));
}
public static int calculateMinute(int hour, int minute){
return hour*60+minute;
}
public static boolean timeClashChecker(int start, int end){
for(int i=start;i<=end;i++){
if(i==end){
time[i] = -1;
}
else if(time[i]==1){
return false;
}
else if(time[i]==-1){
time[i]=1;
}
else{
time[i]=1;
}
}
return true;
}
public static int parser(String time){
String [] timeParts = time.split(":");
int hour = Integer.parseInt(timeParts[0].trim());
int minute = Integer.parseInt(timeParts[1].trim());
return calculateMinute(hour,minute);
}
public static boolean scheduler(String start[], String end[]){
for(int i=0;i<start.length;i++){
int startMeeting = parser(start[i]);
int endMeeting = parser(end[i]);
boolean result = timeClashChecker(startMeeting,endMeeting);
if(result == false){ //clash check
return false;
}
}
return true;
}
}
I agree with one of the comments that we have to practically think of frequent data access patterns of Calendar and design with that in mind. Collision is something we should attribute since it was explicitly mentioned by interviewer
I would define this as a hashtable with key as date and value as a Binary Heap where each node corresponds to hour of the day and 12 hr (in 0-24) is root node. Binary heap provides the O(log N) once within a date. Each node contains a list of all meetings that start at that hour and a duration field on when it ends. Each meeting also has a unique ID that is issued when a meeting is scheduled. If a meeting spans across multiple hours then each node in tree contains its part of the schedule so lets say if meeting is from 2-3:30pm then Node 14 will contain duration 1 hr and node 15 will contain 30 mins. Both meetings will have same meeting ID so when data is retrieved, a simple groping can be used to detect start and end time. Same thing for meetings spanning multiple days. Detecting a collision is easy now since you go to corresponding date and hour node and see if there is a conflict. Deleting a meeting will mean removing from all nodes across which meeting spans.
Advantages of this approach
- List all meetings for a day O(1)
- Find a meeting in specific hour day. O(log 24) since 24 hours in a day
- Detecting a collision. Same a above
- Searching for meeting in a time range O(log 24)
- This can scale quite good using a key/value store.
Disadvantages
- Searching for meetings by title or invites or scheduler. We can solve this by storing another data structure with meeting attributes to hour / start time mapping
Start with full day 'available time'.
With every person you parse, remove the time that he is not available from our initial structure.
Also remove the slots which are less than the meeting time that we need
By the end we will have the intervals where every person is free.
just exploring this idea:
- jimmy514in March 10, 2013create a bst, with meeting as the node..
if the root of the meeting is null, and you have one meeting, create a root = new meeting()
make pointer ptr = root;
now, if you have a list of meetings,
for each meeting mi, there is a arrival time a_i,
and departure d_i
if( a_i is between ptr.arrival_time and ptr.departure time)
return
if( a_i> ptr.departure_time) ptr=ptr-> right;
if(d_i< ptr.arrival_time) ptr= ptr->left;
}// loop through all the meetings..
and construct a binary tree..
let me know what you think on this?