Katkat
Back

Implement a sliding-window rate limiter

RobloxSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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:

  1. A per-user limiter: max Nu requests per user per W ms.
  2. 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.