Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save abloomston/9135042f1352513e162595c33777165c to your computer and use it in GitHub Desktop.
Save abloomston/9135042f1352513e162595c33777165c to your computer and use it in GitHub Desktop.
pramp question 14: adam
"""
question 14
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:
Assume your users will watch exactly two movies
Don't make your users watch the same movie twice
Optimize for runtime over memory
start: <2018-05-03 Thu 09:09>
end: <2018-05-03 Thu 09:20>
post-mortem:
* Could have done this with only one pass through movie_lengths--think about big O *and* actual time to run (2*n >> n)
"""
def is_two_movies_with_exact_length(flight_length, movie_lengths):
"""
Two numbers (not same index, but values may be equal) in movie_lengths whose sum equals flight_length.
Optimize for runtime over memory.
runtime: O(n)
space: O(n)
"""
# construct a map for relevant movie lengths
# runtime: O(n)
# space: O(n)
relevant_movie_lengths_to_count = {}
for movie_length in movie_lengths:
assert movie_length > 0 # assumes no movies are 0 length
if movie_length < flight_length:
relevant_movie_lengths_to_count[movie_length] = relevant_movie_lengths_to_count.get(movie_length, 0) + 1
# iterate over each relevant movie length and see if its "compliment" exists
# runime: O(n) (iterate through up to all movies, complement is O(1) for hash lookup
# space: O(1)
for first_movie_length in relevant_movie_lengths_to_count.keys():
second_movie_length = flight_length - first_movie_length
count = relevant_movie_lengths_to_count.get(second_movie_length, 0)
if first_movie_length == second_movie_length:
count -= 1 # already used one!
if count > 0:
return True
return False
flight_length = 10
movie_lengths = ()
expected = False
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
flight_length = 10
movie_lengths = (5,)
expected = False
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
flight_length = 10
movie_lengths = (5, 5)
expected = True
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
flight_length = 10
movie_lengths = (1, 2, 3, 7)
expected = True
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
flight_length = 11
movie_lengths = (1, 2, 3, 7)
expected = False
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
flight_length = 3
movie_lengths = (1, 2, 3, 7)
expected = True
actual = is_two_movies_with_exact_length(flight_length, movie_lengths)
print(actual)
assert expected == actual
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment