Rate Limiter Dropped Requests (Coding) - Snowflake

Problem overview

You are given a list of integer arrival timestamps (seconds) in arrival order. For each request, you must decide if the request is processed or dropped by a rate limiter that enforces two hard limits: at most 3 requests per second and at most 20 requests per 10 seconds. Windows are inclusive: the per-second window is [t, t] and the ten-second window is [t-9, t] for a request at time t.

What you'll be asked to do

Simulate the rate limiter and return the timestamps of requests that are dropped, in the same order they appear. The interviewer will expect you to handle multiple requests at the same second, contiguous bursts, and sparse arrivals. You'll typically be guided through an approach, asked to optimize for time/space, and to discuss edge cases and complexity.

How to think about it (high level)

• Model the problem as a simulation using sliding-window counting rather than per-request heavy recomputation.
• Use a queue/deque or two-pointer technique to efficiently count requests inside the relevant windows (current second and last 10 seconds) as you iterate.
• Maintain counters for the current second and a structure (deque or indexed counts) for the 10-second window; drop a request if either limit would be exceeded.

Skill signals

You should demonstrate: simulation of constraints, sliding-window or two-pointer counting, appropriate data structures (deque, arrays, hash maps), correctness on edge cases (many equal timestamps), and time/space complexity analysis (aim for O(n) time, O(k) extra space).