Interview Cake

You're out of free questions.

Upgrade now

Your company built an in-house calendar tool called HiCal. You want to add a feature to see the times in a day when everyone is available.

To do this, you’ll need to know when any team is having a meeting. In HiCal, a meeting is stored as an object of a Meeting class with integer properties startTime and endTime. These integers represent the number of 30-minute blocks past 9:00am.

class Meeting { private $startTime; private $endTime; public function __construct($startTime, $endTime) { // number of 30 min blocks past 9:00 am $this->startTime = $startTime; $this->endTime = $endTime; } public function getStartTime() { return $this->startTime; } public function setStartTime($startTime) { $this->startTime = $startTime; } public function getEndTime() { return $this->endTime; } public function setEndTime($endTime) { $this->endTime = $endTime; } public function __toString() { return "($this->startTime, $this->endTime)"; } }

For example:

new Meeting(2, 3); // meeting from 10:00 – 10:30 am new Meeting(6, 9); // meeting from 12:00 – 1:30 pm

Write a function mergeRanges that takes an array of multiple meeting time ranges and returns an array of condensed ranges.

For example, given:

[ new Meeting(0, 1), new Meeting(3, 5), new Meeting(4, 8), new Meeting(10, 12), new Meeting(9, 10) ]

your function would return:

[new Meeting(0, 1), new Meeting(3, 8), new Meeting(9, 12)]

Do not assume the meetings are in order. The meeting times are coming from multiple teams.

Write a solution that's efficient even when we can't put a nice upper bound on the numbers representing our time ranges. Here we've simplified our times down to the number of 30-minute slots past 9:00 am. But we want the function to work even for very large numbers, like Unix timestamps. In any case, the spirit of the challenge is to merge meetings where startTime and endTime don't have an upper bound.

Look at this case:

[new Meeting(1, 2), new Meeting(2, 3)]

These meetings should probably be merged, although they don't exactly "overlap"—they just "touch." Does your function do this?

Look at this case:

[new Meeting(1, 5), new Meeting(2, 5)]

Notice that although the second meeting starts later, it ends before the first meeting ends. Does your function correctly handle the case where a later meeting is "subsumed by" an earlier meeting?

Look at this case:

[new Meeting(1, 10), new Meeting(2, 6), new Meeting(3, 5), new Meeting(7, 9)]

Here all of our meetings should be merged together into just new Meeting(1, 10). We need keep in mind that after we've merged the first two we're not done with the result—the result of that merge may itself need to be merged into other meetings as well.

Make sure that your function won't "leave out" the last meeting.

We can do this in time.

What if we only had two ranges? Let's take:

[new Meeting(1, 3), new Meeting(2, 4)]

These meetings clearly overlap, so we should merge them to give:

[new Meeting(1, 4)]

But how did we know that these meetings overlap?

We could tell the meetings overlapped because the end time of the first one was after the start time of the second one! But our ideas of "first" and "second" are important here—this only works after we ensure that we treat the meeting that starts earlier as the "first" one.

How would we formalize this as an algorithm? Be sure to consider these edge cases:

  1. The end time of the first meeting and the start time of the second meeting are equal. For example: [new Meeting(1, 2), new Meeting(2, 3)]
  2. The second meeting ends before the first meeting ends. For example: [new Meeting(1, 5), new Meeting(2, 3)]

Here's a formal algorithm:

  1. We treat the meeting with earlier start time as "first," and the other as "second."
  2. If the end time of the first meeting is equal to or greater than the start time of the second meeting, we merge the two meetings into one time range. The resulting time range's start time is the first meeting's start, and its end time is the later of the two meetings' end times.
  3. Else, we leave them separate.

So, we could compare every meeting to every other meeting in this way, merging them or leaving them separate.

Comparing all pairs of meetings would take time. We can do better!

If we're going to beat time, maybe we're going to get time? Is there a way to do this in one pass?

It'd be great if, for each meeting, we could just try to merge it with the next meeting. But that's definitely not sufficient, because the ordering of our meetings is random. There might be a non-next meeting that the current meeting could be merged with.

What if we sorted our array of meetings by start time?

Then any meetings that could be merged would always be adjacent!

So we could sort our meetings, then walk through the sorted array and see if each meeting can be merged with the one after it.

Sorting takes time in the worst case. If we can then do the merging in one pass, that's another time, for overall. That's not as good as , but it's better than .

First, we sort our input array of meetings by start time so any meetings that might need to be merged are now next to each other.

Then we walk through our sorted meetings from left to right. At each step, either:

  1. We can merge the current meeting with the previous one, so we do.
  2. We can't merge the current meeting with the previous one, so we know the previous meeting can't be merged with any future meetings and we throw the current meeting into mergedMeetings.
function mergeRanges($meetings) { $meetingsCopy = []; foreach ($meetings as $meeting) { $meetingsCopy[] = clone $meeting; } // sort by start time $sortedMeetings = $meetingsCopy; usort($sortedMeetings, 'compareMeetingsByStartTime'); // initialize mergedMeetings with the earliest meeting $mergedMeetings = [$sortedMeetings[0]]; for ($i = 1; $i < count($sortedMeetings); $i++) { $currentMeeting = $sortedMeetings[$i]; $lastMergedMeeting = $mergedMeetings[count($mergedMeetings) - 1]; // if the current meeting overlaps with the last merged meeting, use the // later end time of the two if ($currentMeeting->getStartTime() <= $lastMergedMeeting->getEndTime()) { $latestEndTime = max($lastMergedMeeting->getEndTime(), $currentMeeting->getEndTime()); $lastMergedMeeting->setEndTime($latestEndTime); // add the current meeting since it doesn't overlap } else { $mergedMeetings[] = $currentMeeting; } } return $mergedMeetings; } function compareMeetingsByStartTime($meetingA, $meetingB) { return $meetingA->getStartTime() > $meetingB->getStartTime() ? 1 : -1; }

time and space.

Even though we only walk through our array of meetings once to merge them, we sort all the meetings first, giving us a runtime of . It's worth noting that if our input were sorted, we could skip the sort and do this in time!

We create a new array of merged meeting times. In the worst case, none of the meetings overlap, giving us an array identical to the input array. Thus we have a worst-case space cost of .

  1. What if we did have an upper bound on the input values? Could we improve our runtime? Would it cost us memory?
  2. Could we do this "in place" on the input array and save some space? What are the pros and cons of doing this in place?

This one arguably uses a greedy approach as well, except this time we had to sort the array first.

How did we figure that out?

We started off trying to solve the problem in one pass, and we noticed that it wouldn't work. We then noticed the reason it wouldn't work: to see if a given meeting can be merged, we have to look at all the other meetings! That's because the order of the meetings is random.

That's what got us thinking: what if the array were sorted? We saw that then a greedy approach would work. We had to spend time on sorting the array, but it was better than our initial brute force approach, which cost us time!

Reset editor

Powered by qualified.io

. . .