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.
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.
Extend it to handle requests that include a gameId:
bool allow(userId, gameId, timestampMs)
Now there are two independent sliding-window limiters:
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.