FastPrep
Problem · Segment Tree

Get Server ID

● MediumAmazonOA
See Amazon hiring insights

The developers of Amazon are working on a prototype for a simple load-balancing algorithm. There are num_servers servers numbered from 0 to num_servers - 1 and the initial number of requests assigned to each server is 0.

In the i-th second, a request comes from IP hash of requests[i], and it must be assigned to the server with the minimum number of requests amongst the first requests[i] servers. For example, if requests[i] = 4, the request must be assigned to the server with the minimum number of requests amongst the servers with id [0, 1, 2, 3]. If there are multiple servers with the same minimum number of requests, choose the one with the minimum id. When a request is assigned to a server, its number of requests increases by 1.

If requests[i] = 0, the candidate set of the first requests[i] servers is empty; in this case the request is assigned to server 0. Assigning the request still increases that server's number of requests by 1.

Given num_servers and the array requests, for each request, find the id of the server it is assigned to.

Function Description

Complete the function getServerIds in the editor.

getServerIds takes the following arguments:

  • int num_servers: the number of servers
  • int requests[n]: the sizes of the requests

Returns

int[n]: the ids of the servers each request is assigned to

Examples
01 · Example 1
num_servers = 5
requests = [3, 2, 3, 2, 4]
return = [0, 1, 2, 0, 3]
Example 1 illustration

The requests are processed as follows: Hence the answer is [0, 1, 2, 0, 3].

02 · Example 2
num_servers = 5
requests = [4, 0, 2, 2]
return = [0, 0, 1, 1]

After the first request, the number of requests is [1, 0, 0, 0, 0]. After the second request, the number of requests is [2, 0, 0, 0, 0]. After the third request, the number of requests is [2, 1, 0, 0, 0]. After the fourth request, the number of requests is [2, 1, 1, 0, 0].

03 · Example 3
num_servers = 5
requests = [0, 1, 2, 3]
return = [0, 0, 1, 2]

Each request is assigned to the first index with the number of requests equal to 0.

Constraints
  • 1 <= num_servers <= 105
  • 1 <= n <= 105, where n is the length of requests
  • 0 <= requests[i] < num_servers
More Amazon problems
drafts saved locally
public int[] getServerIds(int num_servers, int[] requests) {
  // write your code here
}
num_servers5
requests[3, 2, 3, 2, 4]
expected[0, 1, 2, 0, 3]
sign in to submit