FastPrepPer-Client API Rate Limiter
Problems/Per-Client API Rate Limiter

Per-Client API Rate Limiter

Docker logoDocker● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Docker asked this in the coding round of the first interview stage for a senior engineer on an AI developer tools team. The candidate shared their own screen and could use AI tools. The task was to cap how many requests get through in a short time span, separately for every client id. They talked about fixed windows, sliding-window logs, sliding-window counters and token buckets. They built a sliding-window log first. Then, when asked how to store state for a million clients, they rebuilt it as a sliding-window counter.

The report did not fix the limit rule, the window edges, how requests are passed in, or any limits. Here is what we chose. The rule is the exact sliding-window log. Each client may have at most maxRequests accepted requests in the window (t - windowSize, t]. A request exactly windowSize later no longer counts. Rejected requests are not counted. Requests come in as parallel arrays of client ids and non-decreasing integer times, and you give one true or false answer for each. Ids are 1 to 10 lowercase letters or digits. There are up to 2000 requests, a limit of up to 1000, and a window of up to 10^9. The memory follow-up, the approximate sliding-window counter, is covered in the editorial but is not tested.

Our version is about 80% the same as the reported question.

You are building an API rate limiter that stops each client from sending too many requests in a short time. Every client is identified by an id (such as an IP address or an API key), and every client has its own limit: at most maxRequests accepted requests in any window of windowSize time units.

Requests arrive in order: request i comes from client clientIds[i] at time timestamps[i]. A request at time t is accepted if the same client has fewer than maxRequests accepted requests with a time in the window (t - windowSize, t]; otherwise it is rejected. Rejected requests do not count toward later decisions.

Return an array whose i-th value is true if request i is accepted and false if it is rejected.

Function

rateLimit(maxRequests: int, windowSize: int, clientIds: String[], timestamps: int[]) → boolean[]

Examples

Example 1

maxRequests = 2windowSize = 10clientIds = ["a","a","b","a","a"]timestamps = [1,2,3,5,11]return = [true,true,true,false,true]
  • Client a is accepted at times 1 and 2. At time 5 it already has 2 accepted requests in (-5, 5], so the request is rejected.
  • Client b has its own limit, so its request at time 3 is accepted.
  • At time 11 the window is (1, 11]: the request at time 1 has left it and only the one at time 2 remains, so a is accepted again.

Example 2

maxRequests = 1windowSize = 5clientIds = ["x","x","x"]timestamps = [0,4,5]return = [true,false,true]
  • The request at time 4 is rejected because time 0 is inside (-1, 4].
  • At time 5 the window is (0, 5], which no longer contains time 0, and the rejected request at time 4 does not count, so it is accepted.

Example 3

maxRequests = 3windowSize = 100clientIds = ["k"]timestamps = [42]return = [true]
  • A single request is always accepted.

Constraints

  • 1 <= maxRequests <= 1000
  • 1 <= windowSize <= 109
  • 1 <= clientIds.length == timestamps.length <= 2000
  • Each clientIds[i] is 1 to 10 lowercase English letters or digits.
  • 0 <= timestamps[i] <= 109
  • timestamps is sorted in non-decreasing order.

Similar questions at other companies

  • Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
  • Sliding-Window Rate LimiterUber · PHONE SCREENUber interview questions
  • Recent Advertisement Click CountsAmazon · PHONE SCREEN
  • Delayed Streaming Duplicate SuppressionGoogle · PHONE SCREENGoogle interview questions
  • Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
  • Sliding-Window Rate LimiterStripe · PHONE SCREEN · ONSITE INTERVIEWStripe interview questions
  • Key-Value Store GET and PUT QPSDatabricks · PHONE SCREENDatabricks interview questions
  • Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
  • Per-Client Sliding-Window Rate LimiterGeneral Motors · OA
  • Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions

Interview reports that mention this question

  • Docker SWE Manager and Coding Rounds: 1 Experience
See Docker hiring insights
Saved
class Solution {
    public boolean[] rateLimit(int maxRequests, int windowSize, String[] clientIds, int[] timestamps) {
        // Write your code here.
    }
}
Checking account…