Implement queue-based rate limiter with multi-key limits

Q: Implement queue-based rate limiter with multi-key limits

This question evaluates implementation and design skills around rate limiting, including rolling-window counters, multi-key constraints, and atomic updates, and falls under the Coding & Algorithms domain focused on practical application of algorithms and data structures.

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 a rate limiter with method allow(timestamp) that returns true if a request is allowed under a limit of K requests per rolling window W milliseconds, otherwise false. Assume timestamps are nondecreasing integers. Then extend the API to allow(userId, experience, timestamp) that enforces independent limits: at most Ku requests per W per userId and at most Ke requests per W per experience value. The call should succeed only if both limits are satisfied and it must update both counters atomically. Discuss time and space complexity and how you would garbage-collect stale keys.

Implement queue-based rate limiter with multi-key limits

Overview

Comments (0)