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 method 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 method:
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 method 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?
A hash set!
So we could throw all of our movieLengths into a hash set first, in time. Then we could loop through our possible firstMovieLengths and replace our inner loop with a simple check in our hash set. 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 a hash set to access our movies by length, in time.
Using hash-based data structures, like hash maps 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 a hash map?"
Powered by qualified.io