Enforce Per-User Request Limits in a Sliding Window
Company: PayPal
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
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
- Look at the requests from a single user and mark which earlier attempts can affect the current decision.