Implement sliding-window rate limiter function
Company: Atlassian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are implementing a per-user rate limiter. Time is discretized into **integer time buckets** (e.g., each bucket is 1 second).
You are given two parameters:
- `x`: window size in buckets
- `y`: maximum allowed requests within any trailing window of `x` buckets
Implement:
```text
boolean shouldPass(int timeBucket)
```
Each call represents an incoming request attempt at the given `timeBucket`. The function returns:
- `true` if the request is allowed
- `false` if the request should be rate-limited
### Rate-limit rule
A request at time `t` should be allowed **iff** the number of request attempts whose bucket is in:
`[t - x + 1, t]` (inclusive)
is **< y** (i.e., the current request would not make it exceed `y`).
**Assumption:** Even rejected attempts still count toward the limit (they are still request attempts).
### Notes / Constraints
- `timeBucket` values are non-decreasing across calls.
- Aim for efficient time and space usage as the number of requests grows.
- Provide a few test cases (including edge cases such as repeated calls in the same bucket, large gaps between buckets, and bursts).
Quick Answer: This question evaluates proficiency with streaming algorithms and sliding-window data structures, focusing on time-based rate limiting, efficient counting, and space/time complexity management.
Given events [timestamp, key], return whether each is allowed. Every attempt, including rejected attempts, remains in the per-key window.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([[1, 'u'], [2, 'u'], [3, 'u'], [6, 'u']], 2, 5)
Expected Output: [True, True, False, False]
Explanation: Rejected attempts count.
Input: ([[1, 'a'], [1, 'b'], [2, 'a'], [7, 'a']], 2, 5)
Expected Output: [True, True, True, True]
Explanation: Separate keys.
Input: ([[10, 'u']], 0, 5)
Expected Output: [False]
Explanation: Zero limit.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.