Interview Cake

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.

You've built an inflight entertainment system with on-demand movie streaming.

Users on longer flights like to start a second movie right when their first one ends, but they complain that the plane usually lands before they can see the ending. So you're building a feature for choosing two movies whose total runtimes will equal the exact flight length.

Write a function that takes an integer $flightLength (in minutes) and an array of integers $movieLengths (in minutes) and returns a boolean indicating whether there are two numbers in $movieLengths whose sum equals $flightLength.

When building your function:

  • Assume your users will watch exactly two movies
  • Don't make your users watch the same movie twice
  • Optimize for runtime over memory

We can do this in time, where n is the length of $movieLengths.

Remember: your users shouldn't watch the same movie twice. Are you sure your function won’t give a false positive if the array has one element that is half $flightLength?

How would we solve this by hand? We know our two movie lengths need to sum to $flightLength. So for a given $firstMovieLength, we need a $secondMovieLength that equals $flightLength - $firstMovieLength.

To do this by hand we might go through $movieLengths from beginning to end, treating each item as $firstMovieLength, and for each of those check if there's a $secondMovieLength equal to $flightLength - $firstMovieLength.

How would we implement this in code? We could nest two loops (the outer choosing $firstMovieLength, the inner choosing $secondMovieLength). That’d give us a runtime of . We can do better.

To bring our runtime down we'll probably need to replace that inner loop (the one that looks for a matching $secondMovieLength) with something faster.

We could sort the $movieLengths first—then we could use binary search to find $secondMovieLength in time instead of time. But sorting would cost , and we can do even better than that.

Could we check for the existence of our $secondMovieLength in constant time?

What data structure gives us convenient constant-time lookups?

An array!

So we could throw all of our $movieLengths into an array first, in time. Then we could loop through our possible $firstMovieLengths and replace our inner loop with a simple check in our array. This'll give us runtime overall!

Of course, we need to add some logic to make sure we're not showing users the same movie twice...

But first, we can tighten this up a bit. Instead of two sequential loops, can we do it all in one loop? (Done carefully, this will give us protection from showing the same movie twice as well.)

We make one pass through $movieLengths, treating each item as the $firstMovieLength. At each iteration, we:

  1. See if there's a $matchingSecondMovieLength we've seen already (stored in our $movieLengthsSeen array) that is equal to $flightLength - $firstMovieLength. If there is, we short-circuit and return true.
  2. Keep our $movieLengthsSeen array up to date by throwing in the current $firstMovieLength.
function canTwoMoviesFillFlight($movieLengths, $flightLength) { // movie lengths we've seen so far $movieLengthsSeen = []; for ($i = 0; $i < count($movieLengths); $i++) { $firstMovieLength = $movieLengths[$i]; $matchingSecondMovieLength = $flightLength - $firstMovieLength; if (isset($movieLengthsSeen[$matchingSecondMovieLength])) { return true; } $movieLengthsSeen[$firstMovieLength] = true; } // we never found a match, so return false return false; }

We know users won't watch the same movie twice because we check $movieLengthsSeen for $matchingSecondMovieLength before we've put $firstMovieLength in it!

time, and space. Note while optimizing runtime we added a bit of space cost.

  1. What if we wanted the movie lengths to sum to something close to the flight length (say, within 20 minutes)?
  2. What if we wanted to fill the flight length as nicely as possible with any number of movies (not just 2)?
  3. What if we knew that $movieLengths was sorted? Could we save some space and/or time?

The trick was to use an array to access our movies by length, in time.

Using hash-based data structures, like hash tables or hash sets, is so common in coding challenge solutions, it should always be your first thought. Always ask yourself, right from the start: "Can I save time by using an array?"

Reset editor

Powered by qualified.io

. . .