Approaching Interview Questions: Movie Lengths That Cover The Duration Of A Flight

This question was one I got from InterviewCake and I was particularly unhappy with how the answer explained the “why”.

The Problem

A fictional airliner is trying to build a suggestion system to choose two movies that have a combined runtime equivalent to the duration of the flight, i.e., the runtimes of Movie A and Movie B will equal the time it takes to fly from one stop to another. We’re tasked with writing a method that takes an integer flightLength (in minutes) and an array of movieLengths (also in minutes) as arguments and returns a bool indicating whether or not there are two movies in the sequence whose sum equals flightLength.

Assumptions and guidelines provided by InterviewCake:

• Any given passenger will watch exactly 2 movies
• Don’t make a given passenger watch the same movie twice
• Optimize for runtime over memory

The Short Version

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

1. Your first thought might be to have a nested loop. This is a good brute force solution to get some code on screen/the whiteboard. However, O(n^2) is too slow, and it’s possible that the nested loop approach will find a movie of the exact same length that just so happens to be the exact same movie.

2. Important keywords, phrases, and requirements to note from the problem:

   • exactly 2 movies
   • don’t make the user watch the same movie twice - uniqueness
   • two movies in the sequence whose sum equals flightLength These are all signals that we can use a particular strategy with a Set where we take the difference between the flight time and each movie in the sequence, and if we see the difference in the set, we know there are two movies that match the duration of the flight.

3. The one shimmering hope regarding interview questions is that patterns and strategies start to become apparent the more questions one sees. For questions where you have a “master” value to compare against and a sequence of inputs in order to determine a true/false statement, your can start to think about implementing a Set based solution.

The Long Version

We’re given two pieces of data to work with: an integer that represents the total time it’ll take for a given flight to get from point A to point B, and an array of integers that represent the length in minutes of various movies.

We know that we have to see if there’s a pair of numbers in the array that add up to the length of the flight. We know this because the question has told us that we can assume that any given passenger will watch exactly 2 movies. We don’t have to actually return that pair of numbers, however, we just have to verify that they exist. However, another key phrase we have to be aware of is that the passenger shouldn’t be forced to watch the same movie twice, which signals that the pair of numbers must be unique.

The super easy way of doing this is to simply have a pair of nested loops which checks each number in the array against each number in the array again to see if there’s a pair that adds up to the provided integer, while ensuring that the nested loops skip over anything pair of numbers that are the exact same number.

As usual, nested loops are slow in the grand scheme of programming since they result in a O(n^2) runtime for large data sets. This kind of problem is easy once you know the “trick” for doing it in an efficient manner and it’ll fit into larger and/or harder problems in the future.

The things we know:

• We need a set of numbers of some kind: in this case, a pair
• The numbers in that set need to be unique
• That set of numbers needs to sum up to the provided “flight length” input

I’ve bolded the word “set” because that’s exactly what we need for this problem. A Set (or HashSet in C#) is a data structure in the vein of a list; what’s special about a Set is that it cannot contain duplicate values. Using a Set, it’s possible to have a O(n) runtime by using a Set and a single loop rather than a O(n^2) algorithm that uses nested loops.

How are we gonna actually use a Set to our advantage here? We have an integer that represents the length of our flight, aka our sum. We have a sequence of numbers that represent movie times, and two of these numbers could add up to our sum. We can only make one pass through the sequence since we want to have that O(n) runtime, so how can we check for a pair of candidates using only one number? Leverage some basic arithmetic!

Remember that if we have a sum and one number, we can find what the other number is by rewriting the equation as a subtraction problem. You might be familiar with the phrase “solving for x”, which is what we’ll be doing here.

If x + 75 = 100, how do we find x? We rewrite the equation as 100 - 75 = x, and our second number x is 25. We can apply this arithmetic in our loop!

We define a Set that will hold each movie time, and if the Set contains a number that’s equivalent to the difference of the flight length and current movie time, we’ve got a pair of movies that the passenger can watch for the whole flight!

public bool MoviePair(int flightLength, int[] movies)
{
    // Create a set to store the differences between the flight length and the current movie runtime
    HashSet<int> movieTimes = new HashSet<int>();

    // For each movie length in the sequence of movies
    for (int i = 0; i < movies.Length; i++)
    {    
        // Find the difference between the flight length and the current movie runtime
        var matchingMovieLength = flightLength - movies[i];

        // If that difference is in the set, we have a pair of numbers that represent
        // two movies the passenger can watch for the duration of the flight
        if (movieTimes.Contains(matchingMovieLength))
        {
            return true;
        }
        
        // If the difference isn't in the set, add the current movie runtime to the set
        // so we can check it against the other differences we calculate
        movieTimes.Add(movies[i]);
    }
    
    // Otherwise, if we loop through the whole sequence and never meet the loop's 
    // "if" condition, there's no pair. We return false as the question asks.
    return false;
}

When you know what the trick or secret is to an interview question, it can go from a headscratcher to unbelievably easy. When you need to find unique sequences, it’s best to use a Set to organize your results. It doesn’t always apply, but knowing that you need to use a Set in a particular instance can drive you a bit forward. Knowing this trick might even be the answer to a subproblem in a larger interview question.