I was given this question at an interview for a position I just got rejected by, so looking to improve and see what better answers there are!
Input: List of meetings Output: Can conference room fit all the meetings
It was an open ended problem so I was kinda flustered. My first stab at it was probably too much in terms of set up (he was probably just looking for a solution, not so much for a grasp of object oriented principles) and I think I totally diverged from the
Output, but still going to paste my answer anyway:
class Meeting attr_accessor :start_time attr_accessor :end_time def does_not_overlap?(start_time, end_time) self.start_time < start_time && self.end_time < end_time || self.start_time > start_time && self.end_time > end_time || end end class ConferenceRoom attr_accessor :meetings def initialize self.meetings =  end def bulk_schedule(list_of_meetings) currently_scheduled_meetings = self.meetings list_of_meetings.each do |meeting| self.meetings.each do |scheduled_meeting| if currently_scheduled_meetings.does_not_overlap?(meeting) schedule(meeting) else raise "Conference room can't fit all meetings" end end end end def schedule(meeting) self.meetings << meeting end end
My brute force solution was this, which was just to loop through the array of meetings and see if any of them were scheduled at a certain time range when scheduling new meetings. This runs in \$O(n^2)\$ since I have to loop through an array for each element in another array. When he asked how I would optimize it, I said I would use a hash with the time range as keys and loop through those instead. However, thinking back on this I don't think that would improve things at all.
My friend said to sort the array and do binary search on it. However, I don't get how I would do that given the meetings have 2 properties we have to keep in mind (start time and end time), not just one. Can someone shed some light?