FastPrepImplement a Rate Limiter
Problems/Implement a Rate Limiter

Implement a Rate Limiter

Atlassian logoAtlassian● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The reported task identifies this algorithmic exercise. The callable interface, bounds, deterministic rules, and examples are the documented practice contract.

Implement a rate limiter that decides whether each incoming request should be allowed at a given timestamp.

Each request contains a string key (such as a user ID, IP address, or API name) and a non-negative integer timestamp.

Use a fixed-window policy: divide time into non-overlapping windows of exactly window seconds each, aligned to absolute time (i.e., window boundaries occur at 0, window, 2*window, 3*window, ...). A request at timestamp t falls in the window [floor(t / window) * window, floor(t / window) * window + window - 1].

For each request, allow it if the number of previously ALLOWED requests with the same key in the same window is strictly less than limit; otherwise reject it. Only ALLOWED requests count toward the limit; REJECTED requests do not.

Timestamps arrive in non-decreasing order. For each request, return ALLOW or REJECT.

Function

applyRateLimiter(window: int, limit: int, requests: String[]) → String[]

Complete the function applyRateLimiter in the editor below.

applyRateLimiter has the following parameters:

  • int window: the rate-limit window length in seconds
  • int limit: the maximum number of allowed requests per key per window
  • String[] requests: each entry has the form "timestamp key"
  • Returns String[]: one result per request, each being ALLOW or REJECT

Object-oriented follow-up: First put the bucket number and allowed-request count for one client in a small rate-limiter object with an allow(timestamp) method. Then explain how a map from client key to those objects gives each client an independent limit. Keep parsing and batch output in applyRateLimiter. The single-client object and the multiple-client wrapper use the same fixed-window rules above.

Examples

Example 1

window = 10limit = 2requests = ["1 alice", "2 alice", "3 alice", "11 alice", "12 alice", "12 bob"]return = ["ALLOW", "ALLOW", "REJECT", "ALLOW", "ALLOW", "ALLOW"]

Using fixed windows aligned to absolute time with window=10: boundaries at 0, 10, 20, ... Alice's requests at t=1 (window [0,9]: 1 ALLOWED → ALLOW), t=2 (window [0,9]: 2 ALLOWED → ALLOW), t=3 (window [0,9]: already 2 ALLOWED, limit reached → REJECT). Alice's requests at t=11 (window [10,19]: 1 ALLOWED → ALLOW), t=12 (window [10,19]: 2 ALLOWED → ALLOW). Bob's request at t=12 (window [10,19]: first for bob → ALLOW). Only ALLOWED requests count toward the limit.

Example 2

window = 5limit = 1requests = ["1 u", "1 u", "2 u", "6 u", "6 u"]return = ["ALLOW", "REJECT", "REJECT", "ALLOW", "REJECT"]

Using fixed windows aligned to absolute time with window=5: boundaries at 0, 5, 10, ... Key 'u' at t=1 (window [0,4]: 1 ALLOWED → ALLOW), t=1 (window [0,4]: already 1 ALLOWED, limit=1 reached → REJECT), t=2 (window [0,4]: still 1 ALLOWED, limit reached → REJECT), t=6 (window [5,9]: 1 ALLOWED → ALLOW), t=6 (window [5,9]: already 1 ALLOWED, limit reached → REJECT). REJECTED requests do not count toward the limit.

Constraints

  • 1 <= requests.length <= 200000
  • 1 <= window <= 1000000000
  • 1 <= limit <= 100000
  • Timestamps are non-negative integers in non-decreasing order.
  • Each request key contains no spaces.

More Atlassian problems

  • Deterministic Word Guess SolverONSITE INTERVIEW · Seen Oct 2026
  • Generate Word Guess FeedbackONSITE INTERVIEW · Seen Oct 2026
  • Bounded Word Guess SolverONSITE INTERVIEW · Seen Oct 2026
All Atlassian interview questionsSee Atlassian hiring insights
Saved
public String[] applyRateLimiter(int window, int limit, String[] requests) {
    // write your code here
}
Checking account…