Maximum Quality Sum
Updated
Problem statement
Amazon's AWS provides fast and efficient server solutions. The developers want to stress-test the quality of the servers' channels. They must ensure the following:
- Each of the packets must be sent via a single channel.
- Each of the channels must transfer at least one packet.
The quality of the transfer for a channel is defined by the median of the sizes of all the data packets sent through that channel.
Note: The median of an array is the middle element if the array is sorted in non-decreasing order. If the number of elements in the array is even, the median is the average of the two middle elements.
Find the maximum possible sum of the qualities of all channels. If the answer is a floating-point value, round it to the next higher integer.
Function
maximumQualitySum(packets: int[], channels: int) → intExamples
Example 1
packets = [1, 2, 3, 4, 5]channels = 2return = 8
At least one packet has to go through each of the 2 channels. One maximal solution is to transfer packets {1, 2, 3, 4) through channel 1 and packet {5} through channel 2. The quality of transfer for channel 1 is (2 + 3)/2 = 2.5 and that of channel 2 is 5. Their sum is 2.5 + 5 = 7.5 which rounds up to 8.
Example 2
packets = [2, 2, 1, 5, 3]channels = 2return = 7One solution is to send packet {5} through one channel and {2, 2, 1, 3} through the other. The sum of quality is 5 + (2 + 2)/2 = 7
Example 3
packets = [89, 48, 14]channels = 3return = 151There are 3 channels for 3 packets. Each channel carries one, so the overall sum of quality is 89 + 48 + 14 = 151
Constraints
- 1 ≤ len(packets) ≤ 5×10^5
- 1 ≤ packets[i] ≤ 10^9
- 1 ≤ channels ≤ len(packets)
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Initial Public OfferingPoint72 · OAPoint72 interview questions
- Minimum Time to Publish Comic BooksNutanix · OANutanix interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Task SchedulingJP Morgan Chase · OAJP Morgan Chase interview questions
- Rearrange Songs by AuthorZomato / Eternal · OAZomato / Eternal interview questions
- IPOThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- IPOTekion · PHONE SCREENTekion interview questions
- Minimum Refueling StopsUber · ONSITE INTERVIEWUber interview questions
- IPOInMobi · PHONE SCREENInMobi interview questions
- Lexicographically Smallest Array with K-Limited Right MovesGoogle · PHONE SCREENGoogle interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences