How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Atlassian.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Atlassian during technical interviews.

Implement sliding-window rate limiter with dual thresholds

Quick Overview

This question evaluates a candidate's skill in implementing efficient online sliding-window rate limiting, covering stream processing, time-based window management, per-key state maintenance, algorithmic complexity analysis, and formal correctness reasoning.

Company: Atlassian

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Implement getRequestStatus(urls: List[str]) -> List[str]. The i-th entry in urls represents a single incoming request at timestamp t = i seconds (t starts at 0); the value is the URL being requested. For each request, return '200' if it can be served, else '429' if serving it would violate either limit for that same URL: at most 2 successful requests in any sliding 5-second window [t-4, t], and at most 5 successful requests in any sliding 30-second window [t-29, t]. Important: rejected requests must NOT be recorded as successful and therefore must NOT count toward future windows; successful requests do count. Process the stream online in arrival order. Constraints: 0 ≤ n ≤ 2e5; URLs are arbitrary strings; target O(1) amortized time per event and O(U) memory, where U is the number of distinct URLs seen in the past 30 seconds only. Use only built-in data structures; avoid third-party rate-limiting libraries. Provide: 1) A correct, production-friendly implementation that uses per-URL deques (or equivalent) to maintain only the timestamps still inside the respective windows; 2) Proof of correctness with respect to the two sliding-window constraints and the reject-does-not-count semantics; 3) Tight time and space complexity analysis; 4) Unit tests that cover edge cases such as empty input, alternating URLs, bursts exactly at boundaries (t=4/5 and t=29/30), rapid sequences that flip between '200' and '429', and very long runs where old timestamps must be evicted efficiently.

Quick Answer: This question evaluates a candidate's skill in implementing efficient online sliding-window rate limiting, covering stream processing, time-based window management, per-key state maintenance, algorithmic complexity analysis, and formal correctness reasoning.

For each request at second i, return 200 unless serving it would exceed two successes in [t-4,t] or five successes in [t-29,t]. Rejected requests do not count.

Constraints

Timestamp equals request index in seconds

Examples

Input: ([],)

Expected Output: []

Explanation: No requests.

Input: (['a', 'a', 'a'],)

Expected Output: ['200', '200', '429']

Explanation: Third request in five seconds rejected.

Input: (['a', 'b', 'a', 'b', 'a'],)

Expected Output: ['200', '200', '200', '200', '429']

Explanation: Limits are per URL.

Input: (['a', 'a', 'x', 'x', 'x', 'a', 'a'],)

Expected Output: ['200', '200', '200', '200', '429', '200', '200']

Explanation: Boundary at t=5 evicts t=0 from the five-second window.

Input: (['u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u', 'u'],)

Expected Output: ['200', '200', '429', '429', '429', '200', '200', '429', '429', '429', '200', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '429', '200', '200', '429', '429', '429']

Explanation: Long run only records successful requests.

Hints

Keep successful timestamps only; evict entries older than 29 seconds.

Quick Overview