Amazon Interview Question
python
2 months ago
917 B
78
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