Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Interviewing with LinkedIn will be a true test of your skills as a software engineer, but with the right strategy, you’ll be ready to knock the socks off your interviewers. Our program is a step-by-step guide to coding interview preparation.
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 flight_length (in minutes) and a list of integers movie_lengths (in minutes) and returns a boolean indicating whether there are two numbers in movie_lengths whose sum equals flight_length.
When building your function:
We can do this in O(n)O(n) time, where nn is the length of movie_lengths.
Remember: your users shouldn’t watch the same movie twice. Are you sure your function won’t give a false positive if the list has one element that is half flight_length?
How would we solve this by hand? We know our two movie lengths need to sum to flight_length. So for a given first_movie_length, we need a second_movie_length that equals flight_length – first_movie_length.
To do this by hand we might go through movie_lengths from beginning to end, treating each item as first_movie_length, and for each of those check if there’s a second_movie_length equal to flight_length – first_movie_length.
How would we implement this in code? We could nest two loops (the outer choosing first_movie_length, the inner choosing second_movie_length). That’d give us a runtime of O(n^2)O(n2). 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 second_movie_length) with something faster.
We could sort the movie_lengths first—then we could use binary search ↴ to find second_movie_length in O(\lg{n})O(lgn) time instead of O(n)O(n) time. But sorting would cost O(nlg(n))O(nlg(n)), and we can do even better than that.
Could we check for the existence of our second_movie_length in constant time?
What data structure gives us convenient constant-time lookups?
A set!
So we could throw all of our movie_lengths into a set first, in O(n)O(n) time. Then we could loop through our possible first_movie_lengths and replace our inner loop with a simple check in our set. This’ll give us O(n)O(n) 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 movie_lengths, treating each item as the first_movie_length. At each iteration, we:
def can_two_movies_fill_flight(movie_lengths, flight_length): # Movie lengths we've seen so far
movie_lengths_seen = set()
for first_movie_length in movie_lengths:
matching_second_movie_length = flight_length - first_movie_length
if matching_second_movie_length in movie_lengths_seen:
return True
movie_lengths_seen.add(first_movie_length)
# We never found a match, so return False
return False
We know users won’t watch the same movie twice because we check movie_lengths_seen for matching_second_movie_length before we’ve put first_movie_length in it!
O(n)O(n) time, and O(n)O(n) space. Note while optimizing runtime we added a bit of space cost.
The trick was to use a set to access our movies by length, in O(1)O(1) time.
Using hash-based data structures, like dictionaries or 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 dictionary?”
In our experience, we suggest you solve this Practice Questions for the LinkedIn Interview and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Practice Questions for the LinkedIn Interview
I hope this Practice Questions for the LinkedIn Interview would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>