FastPrepFastPrep
Problem Brief

Request Redirection

OA

The hackers of Hackerland want to deploy their applications on n servers. The ith server has requests[i] requests to serve but can serve a maximum of max_req[i] requests only.

In order to balance the load, the hackers need to redirect some requests of ith server to some other server. For each request that is redirecting the request from ith server to jth server, the latency is |i-j| where |i-j| represents the absolute value of i-j. The max_latency is defined as the maximum latency induced among all the redirections.

Given the number of servers n, requests array, find the minimum possible max_latency if the requests are redirected properly. Note that each server has to serve less than the maximum requests it can serve. If there is no way to serve all the requests, report -1 as the answer.

Function Description

Complete the function getMinLatency in the editor.

getMinLatency has the following parameters:

  1. requests[n]: An array of integers
  2. max_req[n]: An array of integers

Returns

int: The minimal max_latency possible respecting the given conditions.

🌼 All credit goes to the amazing friend who helped out!

1Example 1

Input
requests = [1, 3, 2, 4], max_req = [2, 1, 5, 3]
Output
2
Explanation
We can redirect 2 requests from the second server to be the third server and 1 request from the fourth server to the third server. The max latency is equal to max(|2 - 1|, |3 - 2|) = 1. It can be shown that this is the min possible max_latency possible.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10^5
public int getMinLatency(int[] requests, int[] max_req) {
  // write your code here
}
Input

requests

[1, 3, 2, 4]

max_req

[2, 1, 5, 3]

Output

2

Sign in to submit your solution.