In our previous posts, we’ve covered topics like string, tree, linked list and so forth. In this week’s coding interview question, we’re going to discuss something different.
If you have taken many coding interviews, you will know that a lot of questions are quite close to real life projects and don’t have a focus on specific data structures. Some people find it hard at first glance. However, with some analysis, you’ll realize that there are no different from other questions.
In this post, we’ll mainly talk about interval problems and some common techniques you can use when getting stuck.
Given a list of meeting times, checks if any of them overlaps. The follow-up question is to return the minimum number of rooms required to accommodate all the meetings.
Let’s start with an example. Suppose we use interval (start, end) to denote the start and end time of the meeting, we have the following meeting times: (1, 4), (5, 6), (8, 9), (2, 6).
In the above example, apparently we should return true for the first question since (1, 4) and (2, 6) have overlaps. For the follow-up question, we need at least 2 meeting rooms so that (1, 4), (5, 6) will be put in one room and (2, 6), (8, 9) will be in the other.
The meeting room scheduling problem was asked by Facebook very recently and there are quite a few similar problems.
Again, if you haven’t seen this problem before, spend a couple of minutes to think about it.
Let’s start with the first question – check if there are overlaps. I used to interview people with a similar problem and I’ve seen that quite a few candidates tended to enumerate “all cases” with tons of if-else clause. In reality, you are never done because there are always some corner cases your algorithm won’t cover.
There are basically two suggestions here. First, it’s always recommended to start coding after you are confident enough about your solution. Many people like to write code while thinking, which won’t really work in an interview since you don’t have much time. If you think thoroughly about the enumeration approach, it shouldn’t be hard to know that it won’t work in certain cases.
Secondly, when you get stuck, a good approach is to manually try some examples and understand how it works. Let me explain this more. If you manually check if there’re overlaps in the above example, you’ll need to draw each interval in a 1-D space and check if any two intervals overlap. One lesson we learned from this example is that only two “nearby” intervals are able to overlap, which indicates that we may sort all of them and then only check nearby intervals.
In fact, sorting intervals by the start time is an extremely common approach in interval questions. After we sort all the intervals, we can just traverse and check if the next interval’s start point is larger than the current one’s end point.
There’s another way to do that. If you see the sorted intervals as an array of start and end points in order, you can keep a counter. Go over the points one by one in order. When you get a start point, increase the counter by one and decrease by one when it’s an end point. If there’s no overlap, the counter can never get above 1.
The time complexity of sorting is O(NlogN) and the checking overlap is O(N). So overall it’s O(NlogN).
How many meeting rooms do we need at least in order to accommodate all the meetings?
With all the analysis above, it shouldn’t be hard to solve the follow-up question. Think about this: if there’s a timestamp that has 3 intervals covered, we need at least 3 meeting rooms. Otherwise, at least two of those 3 meetings have conflict. With that in mind, we know that if we can find the timestamp with most intervals covered, then the number of covered intervals is the number of meeting rooms we need.
So how to calculate the maximum number of covered intervals? In fact, following the above counter analysis, the max value of the counter is the maximum number of covered intervals. This is because for a given timestamp if there are N unclosed start point in front it, this timestamp must be covered by N intervals.
Some people might find it hard to figure this out. And I’ll tell you that the solution doesn’t come from nowhere. If you try with several examples and draw them on a paper, you will realize how obvious it is.
The biggest thing in this post is to try with examples. Whenever you get stuck, you should consider trying few examples to understand how you can solve the problem as a human. In fact, you might be able to copy the same strategy in a program. Also, some examples can simplify the problem and make it easier to get the essence.
Another thing is that sorting and iterating over the sorted intervals are very common techniques in similar problems. For instance, another popular question is to merge a list of intervals that might have overlaps. After reading this post, you should be able to solve this question with no problem at all.