FastPrepRate-Limiting Algorithm
Problems/Rate-Limiting Algorithm

Rate-Limiting Algorithm

Amazon logoAmazon● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

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: if a request from a region is processed at time t, the next request from that region can be processed at time t + minGap + 1 or later.

  • 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 getMinTime2 in the editor.

getMinTime2 has the following parameters:

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

Returns int: the minimum time required to process all requests without denial.

Examples

Example 1

n = 6requests = "aaabbb"minGap = 2return = 8

Times are 0-based, and two requests from the same region need at least 2 free units between them, so their times differ by at least 3. Send the requests as "ab_ab_ab", where _ is a unit with no request: region a is served at times 0, 3 and 6 and region b at times 1, 4 and 7, so all 6 requests finish after 8 units. Fewer is impossible: the third request of a cannot start before time 2 * 3 = 6, the same holds for b, and a and b cannot both use time 6, so one of them runs at time 7 or later. The answer is 8.

Example 2

n = 12requests = "abacadaeafag"minGap = 2return = 16

Times are 0-based, and requests from the same region need times that differ by at least 3. Region a has 6 requests, so its last one cannot start before time 5 * 3 = 15, and at least 16 units are needed. The order "ab_ad_afgae_ac_a" reaches that: region a is served at times 0, 3, 6, 9, 12 and 15, the six other requests fill times 1, 4, 7, 8, 10 and 13, and times 2, 5, 11 and 14 are empty. The answer is 16.

Constraints

  • 1 <= n <= 10^5, where n is the length of requests
  • 0 <= minGap <= 100
  • requests contains only lowercase English letters

More Amazon interview questions

  • LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Maximal SquareONSITE INTERVIEW · Seen Nov 2026
  • Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
  • Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
  • Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
  • Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
  • Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026

Similar questions at other companies

  • Maximize Palindromic WordsSquarepoint Capital · OASquarepoint Capital interview questions
  • Viral Content BalancerTikTok · OATikTok interview questions
  • Merging PalindromesOld Mission · OA
  • Largest Palindromic Number from Available DigitsMarshall Wace · OAMarshall Wace interview questions
  • Minimum Operations to Reduce a Transaction LedgerVisa · OAVisa interview questions
  • Minimum Substrings Without Repeating CharactersMicrosoft · OAMicrosoft interview questions
  • Find Length of Longest Good SubsequenceWalmart · OAWalmart interview questions
  • Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
  • Rearrange a String So No Neighbors MatchThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
  • Longest-Match Tokenizer with Unknown SymbolsAnthropic · ONSITE INTERVIEWAnthropic interview questions

Interview reports that mention this question

  • Amazon Full-Time OA Problems, Earlier Reports (Part 5 of 5)

Amazon interview experiences

  • Amazon Experienced SDE Onsite Questions: 1 Experience
  • Amazon SDE Onsite Interview Questions: 9 Experiences
  • Amazon SDE II and L5 FDE Interview Questions: 4 Experiences
  • Amazon Full-Time OA Problems, Recent Reports (Part 4 of 5)
  • Amazon New Grad OA Problems: Every Task We Have (Part 3 of 5)
See Amazon hiring insights
Saved
class Solution {
    public int getMinTime2(int n, String requests, int minGap) {
      // write your code here
    }

}
Checking account…