FastPrepAssign Partitions to the Least-Loaded Servers
Problem · Array

Assign Partitions to the Least-Loaded Servers

Learn this problem
● MediumAmazon logoAmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You operate several servers. Server i begins with load serverLoads[i]. A sequence of incoming partitions arrives in order, and partitionLoads[j] is the load added by partition j.

Assign each incoming partition to the server with the smallest current load. If several servers have the same smallest load, choose the server with the smallest index. Immediately add the partition's load to the chosen server before assigning the next partition.

Return an array where result j is the zero-based index of the server chosen for partition j.

Function

assignPartitions(serverLoads: long[], partitionLoads: int[]) → int[]

Examples

Example 1

serverLoads = [8,3,5]partitionLoads = [4,2,7]return = [1,2,1]

The first partition goes to server 1, producing loads [8,7,5]. The second goes to server 2, producing [8,7,7]. Servers 1 and 2 then tie, so the final partition goes to server 1.

Example 2

serverLoads = [0,0]partitionLoads = [1,1,1]return = [0,1,0]

The smaller server index breaks both load ties. After the first two assignments the loads are equal again, so the third partition returns to server 0.

Example 3

serverLoads = [2]partitionLoads = [5,3]return = [0,0]

With one server, every partition is assigned to index 0.

Constraints

  • 1 <= serverLoads.length <= 2 * 10^5.
  • 0 <= partitionLoads.length <= 2 * 10^5.
  • 0 <= serverLoads[i] <= 10^15.
  • 0 <= partitionLoads[j] <= 10^9.
  • The final load of every server fits in a signed 64-bit integer.

More Amazon problems

drafts saved locally
public int[] assignPartitions(long[] serverLoads, int[] partitionLoads) {
  // Write your code here
}
serverLoads[8,3,5]
partitionLoads[4,2,7]
expected[1,2,1]
checking account