# The Velvet Rope

> Some users get in. Others wait outside until the window resets.

Canonical URL: <https://datadriven.io/problems/the_velvet_rope>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Implement per-user sliding-window rate limiting. Test harness input: ['label', max_requests, window_seconds, [[user_id, timestamp], ...]]. For each call, return True if the user has strictly fewer than max_requests allowed calls in the half-open window (timestamp - window_seconds, timestamp], else False. Each allowed call is recorded against that user.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **per-user rate limiting** with a **sliding time window** and deterministic timestamps. It probes class design, per-user state isolation, and the deque-based window expiration pattern.

---

### Break down the requirements

#### Step 1: Track timestamps per user in separate deques

Each user has an independent sliding window. Use a dict mapping user IDs to deques.

#### Step 2: Expire old timestamps before each decision

Remove entries older than `timestamp - window_size` from the front of the deque.

#### Step 3: Allow or deny based on remaining count

If fewer than `max_calls` remain in the window, allow and record; otherwise deny.

---

### The solution

**Per-user deque with sliding window expiry**

```python
from collections import deque
class RateLimiter:
    def __init__(self, max_calls: int, window_seconds: float):
        self.max_calls = max_calls
        self.window = window_seconds
        self.users = {}
    def is_allowed(self, user_id: str, timestamp: float) -> bool:
        if user_id not in self.users:
            self.users[user_id] = deque()
        dq = self.users[user_id]
        cutoff = timestamp - self.window
        while dq and dq[0] <= cutoff:
            dq.popleft()
        if len(dq) < self.max_calls:
            dq.append(timestamp)
            return True
        return False
```

> **Time and Space Complexity**
>
> **Time:** Amortized O(1) per call. Each timestamp is appended once and popped once.
> 
> **Space:** O(u * m) where u is the number of users and m is `max_calls`.

> **Interviewers Watch For**
>
> Using explicit timestamps instead of `time.time()` makes the class deterministically testable. This is a design signal that shows awareness of testing concerns.

> **Common Pitfall**
>
> Using a list instead of a deque. List `pop(0)` is O(n), making the expiration step O(m) per call instead of O(1).

---

## Common follow-up questions

- How would you add burst allowance (e.g., allow 5 extra on the first window)? _(Tests parameterizing initial tokens or a warm-up period.)_
- How would you implement this in a distributed system? _(Tests Redis sorted sets with `ZADD` and `ZRANGEBYSCORE`.)_
- What is the difference between sliding window and token bucket? _(Tests that token bucket refills at a fixed rate and allows bursts, while sliding window counts within a moving interval.)_
- How would you clean up stale user entries? _(Tests periodic garbage collection based on last-activity timestamps.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_velvet_rope)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.