Rate Limiting for API Abuse | Dataford Interview Questions

Implement a rate-limiter class that can be used to protect an API endpoint from abuse at Twitch.

Use a sliding-window policy independently for each client. Given requests in nondecreasing timestamp order, return whether each request is allowed. A request is allowed when fewer than limit requests from that client occurred within the previous window seconds, excluding expired timestamps at timestamp - window.

Input requests contain [client_id, timestamp]; output is a Boolean list.

Constraints

1 <= len(requests) <= 1000
1 <= limit <= 1000
1 <= window <= 10^9
Each request is [client_id, timestamp].
client_id is a non-empty string.
0 <= timestamp <= 10^9
Timestamps for each client appear in nondecreasing order.
At least one request is present.

Function Signature

def rate_limiter(requests, limit, window):

Your question is Rate Limiting for API Abuse. 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

Implement a rate-limiter class that can be used to protect an API endpoint from abuse at Twitch.

Input requests contain [client_id, timestamp]; output is a Boolean list.

Constraints

1 <= len(requests) <= 1000
1 <= limit <= 1000
1 <= window <= 10^9
Each request is [client_id, timestamp].
client_id is a non-empty string.
0 <= timestamp <= 10^9
Timestamps for each client appear in nondecreasing order.
At least one request is present.

Function Signature

def rate_limiter(requests, limit, window):

Your question is Rate Limiting for API Abuse. 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.