How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Implement a sliding-window rate limiter allow()

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem Implement a **sliding-window log** rate limiter. Design a class `RateLimiter` initialized with: - `maxRequests` (e.g., 100) - `windowMillis` (e.g., 60_000) ### API Implement: - `boolean allow(String userId, long timestampMillis)` ### Behavior For each `userId` independently: - Return `true` if the number of allowed requests in the time interval `(timestampMillis - windowMillis, timestampMillis]` is **strictly less than** `maxRequests`. - If returning `true`, record this request as allowed. - Otherwise return `false` and do not record it. ### Constraints - Up to `10^5` calls. - Timestamps are non-decreasing per `userId`. - Optimize for time and memory (e.g., discard timestamps that fall out of the window).

Quick Answer: This question evaluates understanding of sliding-window rate limiting, time-windowed counting, and per-user state management for high-throughput services.

Implement a sliding-window log rate limiter. In the original design, you would create a class `RateLimiter(maxRequests, windowMillis)` with a method `allow(userId, timestampMillis)`. For this coding problem, write a function `solution(maxRequests, windowMillis, requests)` that simulates those `allow(...)` calls in order and returns the result for each call. Each request is a pair `(userId, timestampMillis)`. For each `userId` independently: - A request at time `t` is allowed if the number of previously allowed requests with timestamps in the interval `(t - windowMillis, t]` is strictly less than `maxRequests`. - If the request is allowed, record its timestamp as an allowed request. - If the request is denied, do not record it. Return a list of booleans, where each value is the result of the corresponding request. Important: the left side of the window is open, so a timestamp exactly equal to `t - windowMillis` does not count.

Constraints

1 <= maxRequests <= 10^5
1 <= windowMillis <= 10^9
0 <= len(requests) <= 10^5
For each userId separately, timestamps are non-decreasing
Only allowed requests should be stored; expired timestamps should be discarded

Examples

Input: (2, 10, [('alice', 1), ('alice', 5), ('alice', 10), ('alice', 11), ('alice', 15)])

Expected Output: [True, True, False, True, True]

Explanation: At time 10, the allowed timestamps in (0, 10] are 1 and 5, so the request is denied. At time 11, timestamp 1 falls out because the window is (1, 11], so the request is allowed. At time 15, timestamp 5 is exactly on the left boundary of (5, 15] and does not count, so it is allowed.

Input: (2, 5, [('u1', 1), ('u2', 1), ('u1', 3), ('u2', 4), ('u1', 5), ('u2', 6)])

Expected Output: [True, True, True, True, False, True]

Explanation: Each user is rate-limited independently. u1 has allowed requests at 1 and 3, so the request at 5 is denied. For u2, the request at 6 sees window (1, 6], so timestamp 1 no longer counts and the request is allowed.

Input: (3, 100, [('x', 10), ('x', 10), ('x', 10), ('x', 10)])

Expected Output: [True, True, True, False]

Explanation: All four requests happen at the same timestamp and are in the same window. The first three are allowed, and the fourth exceeds the limit.

Input: (5, 1000, [])

Expected Output: []

Explanation: No requests means no results.

Input: (1, 10, [('a', 1), ('a', 2), ('a', 11)])

Expected Output: [True, False, True]

Explanation: The first request is allowed. The second is denied because the first allowed request is still in ( -8, 2]. At time 11, the active window is (1, 11], so timestamp 1 no longer counts. The denied request at time 2 was never recorded, so the request at 11 is allowed.

Hints

Track requests separately for each user rather than mixing all users together.
Because timestamps never decrease for the same user, a queue/deque lets you remove expired allowed timestamps from the front in amortized O(1) time.

Quick Overview

This question evaluates understanding of sliding-window rate limiting, time-windowed counting, and per-user state management for high-throughput services.