Stripe Coding Interview: API Request Throttle: Fixed Windows

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Stripe. We'll work through one coding problem together, and I'd like you to think out loud as you code. If you need to step out or take a break, you can pause any time with the Pause button at the top right.

The problem is about throttling API requests, which is the kind of rate limiting a payments API relies on. It's in the Problem tab on the right, so please read it through, and ask me anything before you start.

The problem

An API gateway must throttle a single API key's stream of requests.

• timestamps: request times in whole seconds, non-decreasing (equal values allowed).
• limit: the maximum number of requests allowed per window.

Time is split into fixed 60-second windows aligned to multiples of 60: [0, 60), [60, 120), and so on. Process requests in order. A request is allowed if fewer than limit requests have already been allowed in its window. Rejected requests do not count toward the limit. Return a list of booleans, one per request, saying whether each was allowed.

Example: timestamps = [0, 10, 59, 60, 61], limit = 2 → [true, true, false, true, true]

Constraints: 0 ≤ len(timestamps) ≤ 10^5, 1 ≤ limit ≤ 10^5.