Amazon Interview Question

mail@pastecode.io avatar
unknown
python
a year ago
917 B
85
Indexable
Never
import heapq

def minimum_filters(factories):
    if not factories:
        return 0
    # keep track of the amount of pollution we reduce
    reduction = 0
    # number of filters we install
    filters = 0
    total = sum(factories)
    target = total / 2
    # inverse numbers to turn min heap module into max heap
    heap = [-1*num for num in factories]
    heapq.heapify(heap)
    # if we haven't reduced pollution by target amount yet, 
    # we need to add more filters
    while reduction < target:
        # grab largest factory polluter from max heap
        worst_polluter = heapq.heappop(heap) * -1
        after_filter = worst_polluter / 2
        # increase reduction by half of pollution
        # push what's left (the other half) onto the heap 
        reduction += after_filter
        heapq.heappush(heap, after_filter * -1)
        # increment filters
        filters += 1
 
  
    return filters