Amazon OA Question - 2 Pointer Sorting New grad Supply chain

Round 1

Questions: Given the array parcel weights, find the maximum possible efficiency of the warehouse.

Example:

• n = 6
• parcel weights = [4, 4, 8, 5, 3, 2]
• Answer: 17

Solution (pseudo code):

import heapq

def max_efficiency(parcel_weights):
    l = 0
    r = len(parcel_weights) - 1
    min_heap = []

    # Push max of each pair to the heap
    while l < r:
        max_val = max(parcel_weights[l], parcel_weights[r])
        min_val = min(parcel_weights[l], parcel_weights[r])
        
        # Push the max of the two values (negative for max-heap simulation)
        heapq.heappush(min_heap, max_val)
        
        # Replace if the smaller value is less than the current largest in the heap
        if min_heap[0] < min_val:
            heapq.heappop(min_heap)   # Remove the largest element
            heapq.heappush(min_heap, min_val)
        
        l += 1
        r -= 1

    # Calculate the answer by summing the heap (inverted back to positive values)
    answer = 0
    if len(parcel_weights) % 2 == 1: heapq.heappush(min_heap, parcel_weights[len(parcel_weights)//2])
    print("Popped values contributing to efficiency:")
    while min_heap:
        value = heapq.heappop(min_heap)  # Invert back to positive
        print(value)  # Print each value being popped
        answer += value

    return answer

# Test the function
parcel_weights = [4, 4, 8, 1, 5, 3, 2]
print("Maximum Efficiency:", max_efficiency(parcel_weights))  # Expected output: 17