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're in!
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:
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:
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.
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