Quick Overview

Implement a per-user sliding-window rate limiter with ordered timestamps, accepted-request queues, precise expiry boundaries, and amortized linear work.

Enforce Per-User Request Limits in a Sliding Window

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Requests arrive as parallel arrays `users` and sorted nondecreasing `times`. Return a 0/1 result for each request indicating whether it is allowed. Each user may have at most k allowed requests in any rolling window of t seconds. ### Constraints & Assumptions Use the explicit interval `(now-t, now]`: a request exactly t seconds old has expired. Only allowed requests consume capacity. Assume t is positive and k is nonnegative. These boundary and accounting choices should be confirmed with the interviewer. ### Clarifying Questions to Ask - Does a rejected request count toward later limits? - Is the left endpoint inclusive, and can several requests share one timestamp? ```hint Separate users' histories For a new request, only that user's recent allowed timestamps determine whether capacity remains. ``` ### What a Strong Answer Covers - A timestamp queue per user and expiry before the admission decision. - Recording accepted requests only under the stated policy. - Correct equal-timestamp and exactly-expired behavior. - Amortized complexity and the effect of inactive users on memory. ### Follow-up Questions - What changes if requests can arrive out of timestamp order? - How would concurrent servers enforce one shared per-user limit?

Overview: Implement a per-user sliding-window rate limiter with ordered timestamps, accepted-request queues, precise expiry boundaries, and amortized linear work.

Read the full PayPal Software Engineer interview experience this question came from

Requests arrive in input order. Request `i` comes from `users[i]` at timestamp `times[i]`. Each user may have at most `k` allowed requests in the window `(now - t, now]`, where `now` is the timestamp of the current request. Allow a request if that user has fewer than `k` previously allowed requests in the window. An allowed request counts toward later requests, and a rejected request does not. A request exactly `t` seconds old has expired. Process requests with equal timestamps in input order. Return an array containing `1` for each allowed request and `0` for each rejected request, in the original request order.

Constraints

  • users and times have equal length, from 0 through 2^31 - 1.
  • User IDs are well-formed Unicode strings compared by exact equality.
  • times is nondecreasing. Its entries are integers from -(2^53 - 1) to 2^53 - 1, inclusive.
  • 0 <= k <= 2^53 - 1 and 1 <= t <= 2^53 - 1. Both are integers.

Examples

Input: (["a", "a", "b", "a", "a", "b"], [1, 2, 2, 3, 4, 5], 2, 3)

Expected Output: [1, 1, 1, 0, 1, 1]

Explanation: User a reaches the limit at time 3. At time 4, a's request at time 1 has expired. User b uses a separate limit.

Input: (["fox", "fox", "fox", "fox", "fox", "fox"], [0, 0, 3, 4, 4, 8], 1, 4)

Expected Output: [1, 0, 0, 1, 0, 1]

Explanation: A second request at the same time is rejected. Times 4 and 8 each expire the preceding accepted request.

Hints

  1. Look at the requests from a single user and mark which earlier attempts can affect the current decision.

Enforce Per-User Request Limits in a Sliding Window

easyPayPalSoftware Engineer

Requests arrive in input order. Request i comes from users[i] at timestamp times[i]. Each user may have at most k allowed requests in the window (now - t, now], where now is the timestamp of the current request.

Allow a request if that user has fewer than k previously allowed requests in the window. An allowed request counts toward later requests, and a rejected request does not. A request exactly t seconds old has expired. Process requests with equal timestamps in input order. Return an array containing 1 for each allowed request and 0 for each rejected request, in the original request order.

Examples

Example 1
Input
(["a", "a", "b", "a", "a", "b"], [1, 2, 2, 3, 4, 5], 2, 3)
Output
[1, 1, 1, 0, 1, 1]
Notes
User a reaches the limit at time 3. At time 4, a's request at time 1 has expired. User b uses a separate limit.
Example 2
Input
(["fox", "fox", "fox", "fox", "fox", "fox"], [0, 0, 3, 4, 4, 8], 1, 4)
Output
[1, 0, 0, 1, 0, 1]
Notes
A second request at the same time is rejected. Times 4 and 8 each expire the preceding accepted request.

Constraints

  • •users and times have equal length, from 0 through 2^31 - 1.
  • •User IDs are well-formed Unicode strings compared by exact equality.
  • •times is nondecreasing. Its entries are integers from -(2^53 - 1) to 2^53 - 1, inclusive.
  • •0 <= k <= 2^53 - 1 and 1 <= t <= 2^53 - 1. Both are integers.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def rate_limit_requests(users: list[str], times: list[int], k: int, t: int) -> list[int]:
Sample call
rate_limit_requests(["a", "a", "b", "a", "a", "b"], [1, 2, 2, 3, 4, 5], 2, 3)
Language
Case 1
Input
(["a", "a", "b", "a", "a", "b"], [1, 2, 2, 3, 4, 5], 2, 3)
Expected
[1, 1, 1, 0, 1, 1]
Case 2
Input
(["fox", "fox", "fox", "fox", "fox", "fox"], [0, 0, 3, 4, 4, 8], 1, 4)
Expected
[1, 0, 0, 1, 0, 1]

Browse More Questions

Show the approach

Approach

Keep a FIFO queue of accepted timestamps for each user. On each request, remove that user's timestamps whose age is at least t. Chronological processing puts expired timestamps at the front. Allow the request if the remaining queue holds fewer than k timestamps, and append only an allowed timestamp.

After expiration, the queue contains exactly the user's previously allowed requests inside the active window. Appending the current timestamp restores the history for the next request, including requests at the same time. Users have independent queues, so stale entries for another user cannot affect the decision.

Each accepted timestamp is appended once and removed at most once. Signed 64-bit subtraction holds any timestamp difference in the input range. JavaScript represents every difference through the maximum t exactly, and any larger positive difference still compares greater than or equal to t.

Time complexity:
O(n) average total for n requests using hash-based user lookup.
Space complexity:
O(u + a) auxiliary space for u users and a retained accepted timestamps, plus O(n) for the result.