Find Servers That Handled Most Number of Requests

Hard
0/120
Average time to solve is 45m
2 upvotes
Asked in company
Apple

Problem statement

Coding ninja has ‘N’ dedicated servers numbered from 0 to ‘N - 1’, to handle requests parallely. A server can only handle one request at a time. You are given a strictly increasing array of size ‘K’ say ‘requestTime’ that represents the incoming time of ‘K’ requests, and an array ‘processTime’ of size ‘K’ that represents the time required to complete each request.

To work efficiently, incoming requests are handled in the following way.

1. The ‘i - th’ request comes at time ‘request[i]’.

2. The ‘i - th’ request will initially go to ‘(i % N) - th’ server if it is busy, i.e. already processing any request. Then this request will move to the next server i.e ‘( i  + 1) % N -th’ server until it finds a free server. 

3. If all servers are busy at the time ‘request[i]’, then this request will be discarded. I.e. it will not be handled by any server.

You need to find all servers that accept a maximum number of requests.

Example:

Let the number of servers be ‘3’,  ‘requestTime’ be [ 1, 2, 3, 4, 5] and ‘processTime’ be [5, 7, 1, 4, 5]

The requests will be handled in the following order -
1. Initially all servers are free, ‘0 - th’ request will come at time ‘t’ = 1 and it will initially go to ( 0%3 ) server i.e server -0. It will accept the request and complete it in time ‘t’ = 1+ 5.

2. Request - 1 will come at time ‘t’ = 2, initially it will go to (1 % 3) server i.e server - 1, as it is free, it will accept the request and complete it in time ‘t’ = 2 + 7.

3. Request - 2 will come at time ‘t’ = 3 and initially it will go to (2 % 3) server i.e. server - 2, and server - 2 will accept the request and complete it in time ‘t’ = 3 + 1

4. Request - 3 will come at time ‘t’ = 4 and initially it will go to ( 3 % 3) server i.e. server - 0. But this server is busy in Processing ‘0 - th’ request, thus request[3] will move to server - 2, server -2 is also busy in processing request[1], then request[3] will move to server - 3, As this server is free. It will accept the request and complete it in time ‘t’ = 4 + 5.

5. Request -4 will come at time ‘t’ = 5, but all servers are busy at this moment so this request will be discarded.

After all requests are completed, we see that server - 0 and server - 1 have handled 1 request each, and server - 2 has handled 2 requests. So the answer will be ‘server - 2’.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows

The first line of each test case contains two space-separated integers ‘N’ and ‘K’ representing the number of servers and number of incoming requests.

The second line of each test case contains ‘K’ space-separated integers, representing the incoming time of each request, ‘requestTime’.

The last line of the test cases contains ‘K’ space-separated integers, representing the processing time of each request, ‘processTime’.

Output format :

For each test case, print a single line containing ‘X’ space-separated integers representing the index of servers that handled a maximum number of requests, where ‘X’ is the total number of servers that handled a maximum number of requests.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, K <= 3000
1 <= requestTime[i], processTime[i] <= 10 ^ 9

Where ‘T’ is the total number of test cases, ‘N’ and ‘K’ are the number of servers and incoming requests respectively, requestTime[i] is the incoming time of ‘i - th’ request and processTime[i] is the time required to complete ‘i - th’ request.

Time limit: 1 sec.

Sample Input 1:

2
3 4
1 3 4 5
3 2 1 1
4 4
1 2 3 4 
5 5 5 5

Sample Output 1:

0
0 1 2 3

Explanation of Sample Input 1:

Test case 1:

Server -0 will handle ‘request[0]’ and ‘request[3]’, server -1 will handle request[1] and server -2 will handle request[2]. So, server -0 is the busiest server.

Test case 2:

All servers will handle 1 request each.

Sample Input 2:

1
1 5
1 2 4 5 7
5 1 10 2 12

Sample Output 2:

0

Explanation of Sample Input 2:

We have only one server, it will accept the first request. Request -1, request -2, request -3 will be discarded as server -0 is busy processing request -0, request -4 will be accepted as at time ‘t’ = 7, server -0 will available again.
Hint

Brute force will just the implementation of the question statement so do as the problem says.

Approaches (2)
Brute Force Approach

We can iterate over all requests and find the nearest server that is available to accept requests. And we will keep track of the count of accepted requests for each server, and then return the server with the maximum count. 

 

Algorithm:

 

  • Let the given arrays be ‘requestTime’ and ‘processTime’, and ‘N’ be the no. of servers.
  • Declare a count array say ‘cnt’ of size ‘N’ to keep track of the count of accepted requests for each server.
  • Declare an array say ‘nTime’ of size ‘N’ ’to keep track of the next available time for each server. Initially, all servers have 0 next time.
  • Run a loop until the size of ‘requestTime’.
    • Declare a variable say ‘currServer’ equal to ‘i % N’
    • Declare a boolean variable say ‘accepted’ and set it to false.
    • Run a loop for each server starting from ‘currServer’.
      • If ‘requestTime[i]’ >= ‘nTime[currServer]’
        • This means that the current server is available. Then increase cnt[ ‘currServer’ ] by 1, and update ‘nTime [ ‘currServer’ ]’ to ‘requestTime[i] + ‘processTime[i]’.
        • Set ‘accepted’ to true and break the loop.
      • Move ‘currServer’ to the next server. If it is the last server then move to ‘0 - th’ server.
  • Finally, return all the servers with maximum value in the ‘cnt’ array.
Time Complexity

O(K * N), where ‘K’ and ‘N’ are the number of servers and given requests in the problem respectively.

 

In the worst case, we will check all the server for each given requests, that takes O (K * N) time complexity.

Space Complexity

O(N), where ‘N’ is the number of servers given in the problem.

 

As we are using two arrays of size ‘N’  i.e. count array and array for next available time. Hence the overall space complexity will be O (N)

Code Solution
(100% EXP penalty)
Find Servers That Handled Most Number of Requests
Full screen
Console