CareerCup

just exploring this idea:

create 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?

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.

"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.

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

Here I think we can use a List and arrange in the order of which they occur. Each list items can have a collision List item as a reference in it. So here we dont really need to allocate memory in the beginning and there would be no memory wastage.

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;

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.

I would suggest to use bitset as a replacement of array[48] to reduce memory consumption. Open Hashing is a good idea as well.

The calendar data structure is like sparse matrix. And I think adjacency lists are the best way to represent sparse matrix.

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.