Last Updated: 4 Apr, 2021
Find Servers That Handled Most Number of Requests
Hard
Asked in company
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’.
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.
Approaches
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.
- If ‘requestTime[i]’ >= ‘nTime[currServer]’
- Finally, return all the servers with maximum value in the ‘cnt’ array.
In the brute force approach, for each request, we are searching for the nearest available server iteratively. To avoid this we can use ‘set’ data structure say ‘freeServer’ that stores all the server that is free in sorted order according to their index, then for the ‘i - th’ request we just need to find lower_bound of ( i % N) in the ‘freeServer’ . If ‘freeServer’ doesn't have lower_bound of (i % N), then simply we assign this request to first element of ‘freeServer’, because the server order is cyclic i.e after ‘n - th’ server, we start checking from ‘0 - th’ server. But now the question arises: how do we insert all available servers at a given time into ‘freeServer’? For this, we can use a min - heap data structure that stores the next available time for servers that are occupied and their index. The top element of the min-heap will have the lowest next available time. So now for the ‘i - th’ request we just pop all servers whose next time is less than or equal to the incoming time of ‘i - th’ request and store them into ‘freeServer’. And then find the nearest server for this request from the set and store it in a variable say ‘currServer’ and push this ‘currServer’ back to heap with updated next available time and remove it from ‘freeServer’. Here we can see that all other servers in the ‘freeServer’ were also available for the next request as, next request must have an incoming time greater than the current request. Also, we need to use a count array to keep track of the count of accepted requests for each server.
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 accepted request for each server.
- Define a tuple that stores the next available time as a first element and the index of the server as the second element.
- Declare a set data structure say ‘freeServer’ to store all servers that are free at a particular time.
- Declare min-heap to store the occupied servers according to the next available time.
- Now we can assign up to the first ‘N’ request to ‘N’ servers as initially, they are free, So run a loop until min( N , K), where ‘K’ is the number of requests.
- Push { ‘requestTime[i]’ + ‘processTime[i]’, i } into heap.
- cnt [i] += 1.
- Now run a loop to Iterate over requests from ‘N’ to ‘K’ i.e. left over requests.
- Run a while loop until the heap is not empty and the top element of the heap has the next available time less than or equal to ‘requestTime[i]’.
- Pop an element from the heap and store the index of the popped element in ‘freeServer’.
- If ‘freeServer’ is not empty.
- Declare a variable say ‘server’ to store the available server for the current request.
- Find lower_bound of (i % k) in ‘freeServer’ and store it in ‘server’ as we need the nearest available server to ( i % k). If lower_bound doesn’t exist, then store the first element from ‘freeServer’ in ‘server’.
- Push { ‘requestTime[i]’ + ‘processTime[i]’, ‘server’ } back into heap.
- Erase ‘server’ from ‘freeServer’.
- Increase count of ‘server’, cnt[ ‘server’] += 1
- Else, we don’t have any free servers at this moment.
- Run a while loop until the heap is not empty and the top element of the heap has the next available time less than or equal to ‘requestTime[i]’.
- Finally, return all servers with maximum value in the ‘cnt’ array.