#
# Ladder Interview (60 minutes)
#

Welcome to the Ladder Interview! The goal of this interview is to implement two
functions described below. You can use whichever programming language you are
most comfortable with or whichever one you think is the best fit for these
problems. After you finish or when you reach 60 minutes attach the source code
files to the email thread. Any late solutions will not be considered.

#
# Function 1. is_match (difficulty 1)
#

Lets implement a function called `is_match`.

`is_match(pattern, input)`
"pattern" is a string where each character is a token.
"input" is a string where each word is a token (space delimited).
return value: boolean which represents whether these two strings match

Here are some python examples / test cases:
assert is_match("aba", "red blue red") == True
assert is_match("aaa", "red blue red") == False
assert is_match("aba", "red red red") == False

Implement `is_match` with linear runtime O(n + m) where n is the length of
pattern and m is the length of input. You can use any language you want. If you
finish with enough time left then see if you can make your implementation as
clean and concise as possible.

#
# Function 2. find_combos (difficulty 2)
#

Lets implement a function called `find_combos`.

`find_combos(num_desired, available_pack_sizes)`
"num_desired" is an integer and represents the number of sodas that you want.
"available_pack_sizes" is a list of integers and reprents the available pack
sizes a store has.
return value: a list of lists where each entry is a valid combination

If you ran find_combos at the python REPL you'd want to see exactly this output:
>>> find_combos(7, [1, 6, 12])
[[1, 1, 1, 1, 1, 1, 1,], [1, 6]]
>>> find_combos(7, [6])
[]
>>> find_combos(4, [1, 3])
[[1, 1, 1, 1], [1, 3]]

Implement `find_combos` in the simplest way you can. There are no points for
efficiency or runtime in this question. Just focus on solving it in the
cleanest way possible.  You can use any language you want. If you finish
everything else with enough time left then see if you can write some type of
upper bound on the runtime (asymptotic runtime complexity).

#
# Function 3. is_match_2 (difficulty 3)
#
# This is a BONUS QUESTION. I don't expect you'll be able to get to this
# question and solve it in time.
#

Lets implement a function called `is_match_2`.

`is_match(pattern, input)`
"pattern" is a string where each character is a token.
"input" is a string.
return value: boolean which represents whether there exists any solution.

Here are some python examples / test cases:
assert is_match("ab", "xy") == True
assert is_match("ab", "xxy") == True
assert is_match("ab", "xyy") == True
assert is_match("ab", "xx") == False
assert is_match("aa", "xy") == False

Implement `is_match_2` in the simplest way possible. You can use any language
you want. If you finish with enough time left then see if you can make your
implementation as clean and concise as possible.