FastPrep
Problem · Segment Tree

Get Server ID

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

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 servers with ids from 0 through requests[i]. 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.

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

Function

findRequestTarget(num_servers: int, requests: int[]) → int[]

Complete the function findRequestTarget in the editor below.

findRequestTarget takes the following arguments:

  1. int num_servers: the number of servers
  2. int requests[n]: the sizes of the requests

Returns

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

Input Format For Custom Testing

The first line contains an integer, num_servers.

The next line contains an integer, n, the number of elements in requests.

Each of the next n lines contains an integer, requests[i].

Note: The function description and input format were updated on June 26, 2026, backed by the official source found. 🦦

Duplicate note, June 26, 2026: I found that Get Server IDs is a duplicate of this problem. This version has the official source-backed updates, so I recommend practicing here. Going forward, I will only track updates on this version.

Super duper thanks to a super duper special old friend for the help. 💖

Examples

Example 1

num_servers = 5requests = [3, 2, 3, 2, 4]return = [0, 1, 2, 0, 3]

The requests are processed as follows:

Request
IP Hash		 Server Request
Allocation		 Assigned
to		 Remarks
3 [0, 0, 0, 0, 0] 0 The request must be assigned to the server with the minimum number of requests amongst the first 3 servers. Since all the first three servers have 0 requests assigned, it is assigned to the one with the minimum id, i.e. the server with id 0.
2 [1, 0, 0, 0, 0] 1 The request must be assigned to the server with the minimum number of requests amongst the first 2 servers. Since server 1 has 0 requests assigned which is less than server 0 with 1 request, it is assigned to server 1.
3 [1, 1, 0, 0, 0] 2 Amongst the first 3 servers, the one with the minimum requests is server 2.
2 [1, 1, 1, 0, 0] 0 Both of the first two servers have the same number of requests assigned. Hence the request is assigned to server 0 as it has the minimum id.
4 [2, 1, 1, 0, 0] 3 The request must be assigned to the server with the minimum number of requests amongst the first 4 servers. The server with minimum requests is server 3.

Hence the answer is [0, 1, 2, 0, 3].

Note: This example explanation was updated on June 26, 2026, backed by the official source found. 🐳

Example 2

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

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].

Note: This example output and explanation were updated on June 26, 2026, backed by the official source found. 🦭

Example 3

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

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

Note: This example output was updated on June 26, 2026, backed by the official source found. 🐧

Constraints

  • 1 ≤ num_servers ≤ 10^5
  • 0 ≤ requests[i] < num_servers

More Amazon problems

drafts saved locally
public int[] findRequestTarget(int num_servers, int[] requests) {
  // write your code here
}
num_servers5
requests[3, 2, 3, 2, 4]
expected[0, 1, 2, 0, 3]
checking account