Skip to content

Instantly share code, notes, and snippets.

@sachin-handiekar

sachin-handiekar/gist:3a5eb326d8f8120fc50fdcab76a42c34

Created March 11, 2026 06:48
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sachin-handiekar/3a5eb326d8f8120fc50fdcab76a42c34 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sachin-handiekar/3a5eb326d8f8120fc50fdcab76a42c34 to your computer and use it in GitHub Desktop.
Download ZIP
Rate Limiter — Interview Question
Raw
gistfile1.txt
# Rate Limiter — Interview Question
**Difficulty:** Medium
**Topic:** Sliding Window · Queue · Data Structures
**Time:** 45–60 minutes
---
## Problem Statement
You are building an API gateway. To prevent abuse, implement a **Rate Limiter** that controls how many requests a user can make within a rolling time window.
Given a stream of request timestamps (in seconds) and two configuration values — `maxRequests` and `windowSeconds` — your rate limiter must decide, for **each incoming request**, whether it should be **ALLOWED** or **DENIED**.
A request at time `T` is **allowed** if the number of previously allowed requests in the range `(T - windowSeconds, T]` is **less than** `maxRequests`. Otherwise it is **denied**.
---
## Method Signature
```java
boolean allowRequest(int timestamp)
```
You may use a constructor to initialise the limiter with its configuration:
```java
RateLimiter(int maxRequests, int windowSeconds)
```
---
## Constraints
| Parameter | Value |
|---|---|
| `maxRequests` | 1 ≤ maxRequests ≤ 100 |
| `windowSeconds` | 1 ≤ windowSeconds ≤ 60 |
| Timestamps | Always non-decreasing (requests arrive in order) |
| Total requests | Up to 10,000 |
---
## Test Cases
### Test Case 1 — Basic (Happy Path)
**Config:** `maxRequests = 3`, `windowSeconds = 5`
**Input timestamps:** `[1, 2, 3, 4, 5]`
| Timestamp | Decision | Window Contents After |
|---|---|---|
| 1 | ✅ ALLOW | [1] |
| 2 | ✅ ALLOW | [1, 2] |
| 3 | ✅ ALLOW | [1, 2, 3] |
| 4 | ❌ DENY | [1, 2, 3] — window full |
| 5 | ❌ DENY | [2, 3] — t=1 evicted but still 2 < 3, wait... |
**Expected output:** `[true, true, true, false, false]`
**Explanation:**
- At `t=4`: window `(4-5, 4] = (-1, 4]` contains timestamps `[1, 2, 3]` → 3 requests = limit hit → DENY
- At `t=5`: window `(0, 5]` contains `[1, 2, 3]` → still 3 → DENY
---
### Test Case 2 — Window Slides Forward
**Config:** `maxRequests = 3`, `windowSeconds = 5`
**Input timestamps:** `[1, 2, 3, 7, 8]`
| Timestamp | Decision | Active Window | Window Contents |
|---|---|---|---|
| 1 | ✅ ALLOW | (−4, 1] | [1] |
| 2 | ✅ ALLOW | (−3, 2] | [1, 2] |
| 3 | ✅ ALLOW | (−2, 3] | [1, 2, 3] |
| 7 | ✅ ALLOW | (2, 7] | [3, 7] — t=1,t=2 evicted |
| 8 | ✅ ALLOW | (3, 8] | [7, 8] — t=3 evicted |
**Expected output:** `[true, true, true, true, true]`
**Explanation:**
By the time `t=7` arrives, timestamps `1` and `2` have fallen outside the 5-second window. The window resets naturally — this is the "sliding" behaviour.
---
### Test Case 3 — Burst then Recovery
**Config:** `maxRequests = 2`, `windowSeconds = 3`
**Input timestamps:** `[1, 1, 1, 4, 4]`
| Timestamp | Decision | Explanation |
|---|---|---|
| 1 | ✅ ALLOW | 1st request at t=1 |
| 1 | ✅ ALLOW | 2nd request at t=1 — limit reached |
| 1 | ❌ DENY | 3rd request at t=1 — window `(-2,1]` has 2 |
| 4 | ✅ ALLOW | Window `(1,4]` — both t=1 entries evicted |
| 4 | ✅ ALLOW | Window `(1,4]` — has 1 entry so far |
**Expected output:** `[true, true, false, true, true]`
**Explanation:**
Multiple requests can arrive at the **same timestamp**. The eviction condition is `timestamp - stored >= windowSeconds`, meaning `4 - 1 = 3` which equals `windowSeconds`, so t=1 entries fall **outside** the window `(1, 4]`.
---
### Test Case 4 — Edge: maxRequests = 1
**Config:** `maxRequests = 1`, `windowSeconds = 5`
**Input timestamps:** `[1, 2, 6, 7]`
| Timestamp | Decision | Explanation |
|---|---|---|
| 1 | ✅ ALLOW | First ever request |
| 2 | ❌ DENY | t=1 still in window `(-3, 2]` |
| 6 | ✅ ALLOW | t=1 evicted (`6 - 1 = 5`), window clear |
| 7 | ❌ DENY | t=6 still in window `(2, 7]` |
**Expected output:** `[true, false, true, false]`
---
### Test Case 5 — Edge: Large Gap Between Requests
**Config:** `maxRequests = 3`, `windowSeconds = 5`
**Input timestamps:** `[1, 2, 3, 100, 101]`
**Expected output:** `[true, true, true, true, true]`
**Explanation:**
A gap of 97 seconds between `t=3` and `t=100` means all earlier entries are long expired. The limiter must handle large time jumps without accumulating stale state.
---
## Hints
> *(Share these one at a time only if the candidate is stuck)*
1. **Hint 1:** Think about what data structure lets you efficiently add to one end and remove from the other end.
2. **Hint 2:** You only need to store timestamps of *allowed* requests — denied requests don't count against the limit.
3. **Hint 3:** Before checking the count, clean out all timestamps that have "expired" from the window.
4. **Hint 4:** The eviction condition is `currentTimestamp - storedTimestamp >= windowSeconds`.
---
## What a Strong Solution Looks Like
```java
import java.util.ArrayDeque;
import java.util.Deque;
public class RateLimiter {
private final int maxRequests;
private final int windowSeconds;
private final Deque<Integer> window = new ArrayDeque<>();
public RateLimiter(int maxRequests, int windowSeconds) {
this.maxRequests = maxRequests;
this.windowSeconds = windowSeconds;
}
public boolean allowRequest(int timestamp) {
// Evict timestamps outside the sliding window
while (!window.isEmpty() && timestamp - window.peekFirst() >= windowSeconds) {
window.pollFirst();
}
if (window.size() < maxRequests) {
window.addLast(timestamp);
return true;
}
return false;
}
}
```
**Time Complexity:** O(N) amortised — each timestamp is added and removed at most once
**Space Complexity:** O(maxRequests) — the window holds at most `maxRequests` timestamps at any time
---
## Evaluation Rubric
| Area | What to Look For |
|---|---|
| **Algorithm choice** | Picks sliding window log over fixed window |
| **Eviction logic** | Correct boundary condition (`>=` vs `>`) |
| **Data structure** | Uses `Deque` / `Queue` appropriately |
| **Edge cases** | Handles same-timestamp bursts, large gaps, maxRequests=1 |
| **Code quality** | Clean, readable, no unnecessary complexity |
| **Follow-up** | Can discuss thread-safety or distributed extension |
---
## Follow-Up Questions (Senior Candidates)
1. **Thread safety** — *"How would you make this safe for concurrent access across multiple threads?"*
2. **Memory leak** — *"What happens if you have millions of users who send one request and never return?"*
3. **Distributed system** — *"How would you implement this across 10 servers?"* *(Expected: Redis + atomic operations)*
4. **Algorithm trade-off** — *"How does Token Bucket differ from Sliding Window Log? When would you pick one over the other?"*
5. **Testability** — *"How would you unit test this without calling `Thread.sleep()`?"* *(Expected: inject a `Clock` abstraction)*
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment