Atlassian·Data Scientist·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Atlassian Data Scientist interview with a pretty involved coding problem around rate limiting. The question was more algorithmic than I expected for a DS role, and the constraints they added mid-explanation kept piling up.

Questions Asked (1)

Implement a function that takes a list of URLs (one per second, starting at t=0) and returns '200' or '429' for each request, enforcing two sliding-window rate limits per URL: at most 2 successful requests in any 5-second window and at most 5 in any 30-second window. Rejected requests must not count toward future windows. Aim for O(1) amortized time per request and O(U) space where U is distinct URLs seen in the last 30 seconds.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

My first instinct was to reach for a counter dict and i got partway through before realizing rejected requests not counting completely breaks a naive counter approach.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose a solution using a per-URL deque of timestamps for successful requests, with two sliding windows (5s and 30s). Explain how to enforce both limits in O(1) amortized time by pruning expired timestamps and checking the deque lengths, and discuss space complexity and potential optimizations.

Pro tip: Emphasize that rejected requests are not recorded, which simplifies the state and ensures fairness; also mention that the 30-second window inherently bounds the deque size, making space O(U) where U is distinct URLs in the last 30 seconds.

1. Clarify requirements and constraints

Ask clarifying questions about input format, timing precision, and whether the function is called in real-time or with timestamps. Confirm that rejected requests do not count and that limits are per URL.

2. Design data structures

Propose a hash map from URL to a deque (or two deques) storing timestamps of successful requests. Explain that deques allow O(1) append and popleft for pruning expired entries.

3. Define the rate-limiting logic

For each request at time t, prune timestamps older than t-5 and t-30 from the respective deques. Check if the number of timestamps in the last 5 seconds is <2 and in the last 30 seconds is <5; if both, accept and record t; else reject.

4. Analyze complexity and edge cases

Show that each request is processed in amortized O(1) time because each timestamp is added and removed at most once. Discuss space O(U) where U is distinct URLs with successful requests in the last 30 seconds. Handle edge cases like multiple requests at the same timestamp.

5. Discuss trade-offs and optimizations

Mention alternative approaches like token buckets or fixed windows, and explain why sliding windows are more accurate. Suggest possible optimizations like using a single deque with two pointers or a circular buffer if needed.

Key Points to Mention

Sliding window vs fixed window: sliding windows prevent burstiness at boundaries and are more precise.
Use of deque (double-ended queue) for O(1) append and popleft operations.
Amortized O(1) time per request because each timestamp is inserted and removed at most once.
Space complexity O(U) where U is distinct URLs seen in the last 30 seconds, as older entries are pruned.
Rejected requests are not recorded, so they do not affect future windows.
Handling of simultaneous requests: if multiple requests arrive at the same timestamp, process them sequentially and enforce limits correctly.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.