pramp question 14: adam

gistfile1.txt

"""
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