Implement a sliding-window rate limiter

Q: Implement a sliding-window rate limiter

Evaluates the candidate's ability to design and implement an in-memory sliding-window rate limiter enforcing per-user and per-game constraints, focusing on correct request-acceptance semantics and efficient timestamp eviction; Category/domain: Coding & Algorithms; Level of abstraction: component-level algorithm and data-structure implementation.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement an in-memory sliding-window rate limiter.

You are given a stream of requests, each with a timestamp in milliseconds.

Part 1: Per-user limit

Design a data structure with an API like:

bool allow(userId, timestampMs)

Each user has their own limiter: allow at most N requests per user in the last W milliseconds (a sliding window ending at timestampMs, inclusive). Return true if the request is allowed and should be recorded; otherwise return false.

Part 2: User limit + game limit

Extend it to handle requests that include a gameId:

bool allow(userId, gameId, timestampMs)

Now there are two independent sliding-window limiters:

A per-user limiter: max Nu requests per user per W ms.
A per-game limiter: max Ng requests per game per W ms.

A request (userId, gameId, timestampMs) is allowed only if both the user limiter and the game limiter would allow it. If either limiter rejects, the request is rejected.

Specify the approach and implement it efficiently for many users/games. Discuss time/space complexity and how you evict old timestamps.

Implement a sliding-window rate limiter

Quick Overview

Part 1: Per-user limit

Part 2: User limit + game limit

Comments (0)