10 Oct 2020

Approaching Interview Questions: Meeting Times

Lately I’ve been trying to move on to cooler positions, so I’ve found myself tackling the dreaded whiteboard interview questions, both practicing them and dealing with them in person. As someone from a non-traditional background who hasn’t had to go through a lot of rigorous interview questions, it’s been a real struggle to find posts on the internet that aren’t just people copying other people’s work or not verbalizing their thought process.

I somehow managed to get a code screen with Bloomberg’s engineering team as my first interview, and when I “sat” with the interviewer on the shared HackerRank IDE, I was given the following problem about meeting times. The question seemed easy enough, but it definitely caught me off guard; I managed to get through it, but I was unsure enough that it disqualified me from the rest of the interview loop. I spent some time trying to decode it based off of various online resources some time later, and it finally clicked.

This post will attempt to explain the thought process for this question and what one can do to put their best foot forward. Remember that interviews aren’t just about getting the interview questions right, the interviewer is more than likely going to be a coworker you’ll be interacting with frequently! Show them your stuff, because they want to know you’re not just gonna be a code drone/monkey!

The Problem

There’s a hypothetical software company that has a calendar program for keeping track of all the meetings that go on during any given day (standups, sprint planning, etc.). However, there’s no system in place for making sure people are all available for a new meeting! Given an unordered collection of meetings, create a method to merge any meetings that overlap (i.e., one meeting has a starting time in the middle of another unrelated yet currently active meeting) and return an ordered list of the merged and unmerged meetings.

The Short Version

If you’ve already put some work into this question or you just need a refresher, here’s a tl;dr.

If the interviewer hasn’t already created/established a Meeting class, create one with StartTime and EndTime properties. The types of these properties will depend on what the interviewer states that the input looks like (i.e., C# DateTimes for times, int for numeric representation of chunks of time)
Since the meetings are unsorted, we have to sort them or else we won’t have a reliable way to pick a meeting to start with. Create a sorted clone of the list of meetings so the Meeting objects have different references. Later on we’ll be performing an in-place modification.
Once sorted, put the first meeting from the now-sorted list of meeting objects into the list you plan to return to the caller; this meeting object will be our jumping-off point where we determine whether or not to merge the subsequent meeting object(s) with it.
Two meetings overlap if the prior meeting’s ending time is greater than or equal to the subsequent meeting’s starting time, which translates to firstMeeting.EndTime >= secondMeeting.StartTime as our “if” statement for determining if we merge the first and second meeting or simply add the second meeting.
Remember how I mentioned in step 2 that we’d be performing an in-place modification? While looping through the new list created in step 2, if the meetings have to be merged, perform an in-place modification on the “first” Meeting object so the “first” meeting’s end time is the later of the two meetings end times. Otherwise, add the second meeting to the “merged” list.
Once the loop is done, return the “merged” list. Done!

The Long Version

Creating a foundation

To start this off, if the interviewer hasn’t created a class to represent a Meeting, do so based on the sample input. Bloomberg used full times, so the Meeting class should look like the following for this demonstration:

public class Meeting
{
    public DateTime StartTime { get; set; }
    public DateTime EndTime { get; set; }

    public Meeting(DateTime start, DateTime end)
    {
        StartTime = start;
        EndTime = end;
    }
}

Take a few seconds and think about what the criteria for overlapping meetings are; it’s when two meetings are going on at the same time, right? Not exactly, but a good start.

A good way to really determine the foundation for your logic is to look at some kind of input. When I was interviewing with the Bloomberg engineer, I was given three test times to work with. If your interviewer gives you test inputs to work with, use them to create a really easy example input that you can easily code for.

List<Meeting> sampleTimes = new List<Meeting>()
{
    new Meeting(/** 10:00 am, 12:00pm */),
    new Meeting(/** 11:00 am, 11:45am */),
}

Note: One thing I particularly enjoyed about the interview was that the interviewer didn’t want me to waste time dealing with the parsing. Most interviewers won’t get on your case about their input until your code is already hashed out.

So, we’ve got two inputs. We know that they overlap because the meeting at 11am is happening in the middle of the meeting at 10am. How do we represent that in a more concrete manner, like in code?

The end time of the first meeting is later than the start time of the second meeting!

Why the end time, specifically? Why not check the start times? Consider the following: what if both meetings started at 10am? You’d have to check the end time anyway, so why have an extra condition that’ll make things more complicated?

Unfortunately, we’re going to have to deal with some complexity right off the bat:

We knew they overlapped because we designated that there was a “first” and a “second” meeting. Remember that the actual input for this question is unordered. We’ll need to think of a way to decide what’s “first” and “second”.
How do we handle cases where the end time for the first meeting is EQUAL to the start time of the second meeting? You just know someone’s gonna schedule back-to-back meetings.
What if the second meeting ends BEFORE the first meeting? This happens! What if one team is just having standup while another is having a sprint planning meeting?

Note: I made the second observation during my interview, but the interviewer made the other two points. Sometimes you won’t figure out all the edge cases, but do your best. Depending on the quality of the interviewer, they’ll try to help you with edge cases. Even with easy ones, if you’re just starting out, you won’t catch everything.

Given everything we know, we can cobble something together for our code definition:

if (firstMeeting.EndTime > secondMeeting.StartTime)
{

}
else if (firstMeeting.EndTime == secondMeeting.StartTime)
{

}
else if (firstMeeting.EndTime < secondMeeting.EndTime)
{

}

This might not be right for our purposes, but we can visualize what conditions we have as code. It’s ugly but it fits the need of just getting something out there for the interviewer to see.

Take a step back now that we’ve got something on the screen. Don’t we want to merge anything that overlaps, including when one meeting ends immediately as another is starting? Yes we do: simplify the first condition to be >= instead of just > and our condition is way better:

if (firstMeeting.EndTime >= secondMeeting.StartTime)
{

}
else
{

}

Applying what we’ve created

So we’ve got ourselves some decent logic for merging our meetings. Now, the usual first instinct is to use two for loops to compare each meeting against all the other subsequent meetings, but in this case we’ll end up writing a LOT of hard-to-write and hard-to-read code that we can’t really explain that well. Even worse, we already know it’s O(n^2) in performance! So, in order to write something legible and faster, we’ll need to keep a few tricks and pitfalls in mind.

Remember, all of our incoming meetings are unordered! We’re going to be establishing a “first” and “second” meeting, so we need things to be in some kind of order, no two ways around it. Just because something’s out of order doesn’t mean it has to be!

However, we don’t want to modify the items in the list being provided to our method, so we’ll want to leverage some preexisting language feature and make a collection that’s got the same values in different memory locations. For C# users, this can be accomplished with a LINQ query:

var sortedMeetings = meetings.Select(m => new Meeting(m.StartTime, m.EndTime)).OrderBy(m => m.StartTime).ToList();

C# specific: The select creates new Meeting objects, and then we OrderBy meeting start time. LINQ queries produce IEnumerables, so we’ll need to convert it ToList as well.

Our first trick starts out like this: when we create the List<Meeting> where all of our merged meetings will go, we’ll stick the very first sorted meeting into the merged meeting list that we’re going to return to the caller. Why’s that? We can leverage in-place modification!

We’ll be using in-place modification to solve two problems at once:

We’ll only have to have one loop
We’ll be able to designate a “first” and “second” meeting, where the “first” is the meeting already in the sequence.

We designate the last value in the list of merged meetings to a variable, and using it with our condition:

foreach (var meeting in sortedMeetings)
{
    var lastMergedMeeting = sortedMeetings.Last();

    if (lastMergedMeeting.EndTime >= meeting.StartTime)
    {
        // If the first (current) and second (last merged) meetings overlap,
        // simply modify the second (last merged) meeting's end time with
        // the later end time value
    }
    else
    {
        // Otherwise, the current meeting doesn't overlap, so we can just 
        // safely add it to the list without fear
        mergedMeetings.Add(meeting);
    }
}

Why the last value? Remember that we’re either merging meetings so an entire block of time is covered by one Meeting object, or we’re adding a meeting that doesn’t overlap with any others. Once we add a meeting that doesn’t overlap, we need to select that newly-added meeting as our “first” meeting during the comparison.

With that, we’ve created a readable and efficient solution, covering all the tricks along the way! The final code should look something like this:

public List<Meeting> MergeMeetings(List<Meeting> meetings)
{
    // Sort the unsorted meetings, ensuring that we're creating new Meeting objects so we don't end up modifying the originals
    var sortedMeetings = meetings.Select(x => new Meeting(x.StartTime, x.EndTime)).OrderBy(m => m.StartTime).ToList();
    // The list of merged meetings, with the first meeting from the now-sorted meeting list added to it
    var mergedMeetings = new List<Meeting> { sortedMeetings.First() };

    foreach (var meeting in sortedMeetings)
    {
        var lastMergedMeeting = mergedMeetings.Last();

        if (lastMergedMeeting.EndTime >= meeting.StartTime)
        {
            /**
            Implementation dependent: if using integers to represent blocks of time,
            update the EndTime property of the lastMergeMeeting using Math.Max.

            If using DateTimes, you'll have to perform some comparison logic to see if
            the current meeting end time is greater than the last merged meeting's end
            time; if so, update the EndTime property of the last merged meeting with the
            current meeting's EndTime property.
            */

            /** Integer-based

            lastMergedMeeting.EndTime = Math.Max(lastMergedMeeting.EndTime, meeting.EndTime);
            */

            // DateTime-based

            if (lastMergedMeeting.EndTime < meeting.EndTime)
            {
                lastMergedMeeting.EndTime = meeting.EndTime;
            }
            // else, leave the last merged meeting's end time alone
        }
        else
        {
            mergedMeetings.Add(meeting);
        }
    }

    return mergedMeetings;
}