Skip to content

Instantly share code, notes, and snippets.

  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save AdrienLemaire/9e9c99336d2b2e2d8ce9779153d2ead2 to your computer and use it in GitHub Desktop.
apollo ag test
# def change(array_of_denominations, amount): ==> Number of ways you can make change
# """
# change([1, 5], 6) => 2
# change([1, 5], 10) => 3
# """
def change(array_input, amount):
if amount == 0:
return 1
elif amount < 0 or len(array_input) == 0:
return 0
reduced_amount = amount - array_input[0]
yield change(array_input, reduced_amount)
yield change(array_input[1:], reduced_amount)
yield change(array_input[1:], amount)
# https://en.wikipedia.org/wiki/Bipartite_graph
[[2, 1], [1, 3], [5, 6]]
1 --> 2
--> 3
set_u = set()
set_v = set()
def is_bipartite(connections):
if {a, b}.issubset(set_u):
return 0
elif {a, b}.issubset(set_v):
return 0
elif a in set_u:
set_v.add(b)
elif a in set_v:
set_u.add(b)
elif b in set_u:
set_v.add(a)
else:
set_u.add(a)
return is_bipartite(connections[1:])
print(is_bipartite([[1, 4], [1, 5], [2, 4], [3, 6])]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment