Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

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.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

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?

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Reset editor

Powered by

. . .