Implement a rate limiter at scale

Q: Implement a rate limiter at scale

This is a Coding & Algorithms interview question from Microsoft for Software Engineer roles. View the full question and solution on PracHub.

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

Loading...

Problem

Design and implement a rate limiter that enforces request limits per key (e.g., per user ID or API key).

Requirements

Implement allow(key, timestamp) → returns true if the request is allowed, else false .
Support a policy like: at most N requests per sliding window of W seconds (you may choose fixed-window vs sliding-window, but state it clearly).
Handle many distinct keys.

Follow-up (scale)

How would you adapt the design/implementation if the service must handle 100K QPS? Discuss:

Data structures and time/space complexity
Concurrency/thread safety
Distributed deployment (multiple instances) and correctness trade-offs
Hot-key mitigation and storage choices

Constraints (assumptions you may make explicit)

Timestamps are in milliseconds or seconds (choose one).
Keys are strings.
Memory is limited; old state should expire.

Implement a rate limiter at scale

Problem

Requirements

Follow-up (scale)

Constraints (assumptions you may make explicit)

Comments (0)