API Gateway Rate Limiting Design | Dataford Interview Questions

How would you design a rate-limiting algorithm for an API gateway?

Implement a per-client sliding-window limiter that processes requests in nondecreasing timestamp order. Allow a request when fewer than limit previously allowed requests from that client occurred within the inclusive window [timestamp - window + 1, timestamp]; rejected requests do not consume capacity.

Use def rate_limit(requests, limit, window):, where requests is a list of [client_id, timestamp] pairs and the output is a Boolean list matching request order.

Example: [["a", 1], ["a", 2], ["a", 3]], limit = 2, window = 3 returns [true, true, false].

Constraints

1 <= len(requests) <= 1000
1 <= limit <= 10^6
1 <= window <= 10^9
Each request is [client_id, timestamp]
1 <= len(client_id) <= 64
0 <= timestamp <= 10^9
Requests are sorted by nondecreasing timestamp

Function Signature

def rate_limit(requests, limit, window):

Your question is API Gateway Rate Limiting Design. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem