FastPrep
Problem · Heap

Load Balancer

Learn this problem
● MediumTiktokINTERNOA
See Tiktok hiring insights

Problem statement

Implement a prototype of a round-robin load-balancing algorithm.

There are n servers indexed from 1 to n, and m requests to be processed. The ith request arrives at time arrival[i] and takes burstTime[i] time to execute. The load balancer assigns the ith request to the server with the minimum index. A server that is assigned the ith request is unavailable from arrival[i] to arrival[i] + burstTime[i]. At arrival[i] + burstTime[i], the server is available to serve a new request.

Given n, arrival, and burstTime for each request, find the index of the server that executes it. If no server is available at the time, the request is dropped, and -1 is reported. If multiple requests arrive at the same time, the one with the smaller index is assigned first.

Function

getServerIndex(n: int, arrival: int[], burstTime: int[]) → int[]

Complete the function getServerIndex in the editor.

getServerIndex has the following parameter(s):

  1. int n: the number of servers
  2. int arrival[m]: the arrival time of requests
  3. int burstTime[m]: the burst time of requests

Returns

int[m]: the Index of the servers the requests are assigned to, or -1 if no server is available

Examples

Example 1

n = 3arrival = [2, 4, 1, 8, 9]burstTime = [7, 9, 2, 4, 5]return = [1, 2, 1, 3, 2]
Example 1 illustration
Look carefully at the explaination image shown above 👆. Answer is [1, 2, 1, 3, 2].

Constraints

  • 1 ≤ n ≤ 105
  • 1 ≤ m ≤ 105
  • 1 ≤ arrival[i] ≤ 109
  • 1 ≤ burstTime[i] ≤ 109

    • More Tiktok problems

    drafts saved locally
    public int[] getServerIndex(int n, int[] arrival, int[] burstTime) {
    // write your code here
}
    n3
    arrival[2, 4, 1, 8, 9]
    burstTime[7, 9, 2, 4, 5]
    expected[1, 2, 1, 3, 2]
    checking account