FastPrep
Problem · Greedy

Rate-Limiting Algorithm

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Some developers at Amazon are building a prototype for a simple rate-limiting algorithm. There are n requests to be processed by the server, represented by a string requests, where the i-th character represents the region of the i-th client. Each request takes 1 unit of time to process.

There must be a minimum time gap of minGap units between any two requests from the same region.

  • The requests can be sent in any order, and there can be gaps in transmission for testing purposes.
  • Find the minimum amount of time required to process all the requests such that no request is denied.

    • Function

    getMinTime2(n: int, requests: String, minGap: int) → int

    Complete the function getMinTime in the editor.

    getMinTime has the following parameters:

    1. n: int: the number of requests
    2. requests: String: a string representing the region of each request
    3. minGap: int: the minimum time gap required between requests from the same region

    Returns

    The function should return an integer representing the minimum time required to process all requests without denial.

    Examples

    Example 1

    n = 6requests = "aaabbb"minGap = 2return = 8
    Example 1 illustration
    The requests can be sent in the order ab_ab_ab where _ represents that no request was sent in that unit time. Here, the minimum time gap between two requests from the same region is minGap = 2. The total time taken is 8 units.

    Example 2

    n = 12requests = "abacadaeafag"minGap = 2return = 16
    One optimal strategy is "ab_ad_afgae_ac_a

    Constraints

  • 1 <= length of requests <= 105
  • 0 <= minGap <= 100
  • It is guaranteed that requests contain lowercase English characters

    • More Amazon problems

    drafts saved locally
    public int getMinTime2(int n, String requests, int minGap) {
  // write your code here
}
    n6
    requests"aaabbb"
    minGap2
    expected8
    checking account