CS Fun Interview Questions

minimum_waste.py

# What is time and space complexity of algorithm?
# Unsure how to only keep track of one integer value instead of saving an array of minimum waste values.
def minimum_waste(bottles, potion):
    # sort from greatest to least
    bottles.sort(reverse = True)
    w = []

    recurse_minimum_waste(w, bottles, potion, bottles[0])
    return min(w)

def recurse_minimum_waste(w, bottles, potion, current_bottle):

    # base case
    if potion <= current_bottle:
        w.append(current_bottle - potion)
        return

    # recurse case
    else:
        for i in range(len(bottles)):

            recurse_minimum_waste(w, bottles[i:], potion - bottles[i], bottles[i])


print(minimum_waste([30, 20, 70, 100], 175))