Rate Limiter in Rust

This is a design round. You write the classes, and the interviewer checks that they behave.

Here you build a rate limiter. It stops a user from making too many calls in a short time.

Implement the class:

• RateLimiter's new(limit, window) makes a limiter. Each user may make limit calls in any window seconds.
• allow(user, time) is a call by user at second time. It returns true if the call is allowed, and false if not.

Rust has no classes. RateLimiter is a struct, and its methods sit in an impl block. Its new function makes one. The examples write RateLimiter(2, 10) for that function.

A call looks back over a window of seconds. The window starts after second time - window and ends with second time. With a window of 10, a call at second 11 looks at seconds 2 to 11.

The call is allowed when the user made fewer than limit allowed calls in that window. An allowed call counts for the later calls. A refused call does not count.

Each user has their own count. The times never go down from one call to the next.

The calls run in order on one new limiter. The output has one line for each call, with what it returns. Booleans are written as True and False.

Example 1:

Input:
RateLimiter(2, 10)
1. allow("ana", 1)
2. allow("ana", 5)
3. allow("ana", 8)
4. allow("bob", 8)
5. allow("ana", 11)
6. allow("ana", 12)
Output:
True
True
False
True
True
False
Explanation:
Calls 1 and 2 use up ana's two calls.
So call 3 is refused.
Bob has his own count, so call 4 is allowed.
At second 11, the window is seconds 2 to 11.
The call at second 1 has left it, so call 5 is allowed.
Call 6 is refused. The calls at 5 and 11 are still in its window.

Example 2:

Input:
RateLimiter(1, 3)
1. allow("max", 0)
2. allow("max", 2)
3. allow("max", 3)
4. allow("max", 3)
Output:
True
False
True
False
Explanation:
The window is 3 seconds long.
Call 2 is refused, and a refused call does not count.
At second 3, the window is seconds 1 to 3.
The call at second 0 is out, so call 3 is allowed.

Example 3:

Input:
RateLimiter(3, 100)
1. allow("kim", 50)
2. allow("kim", 50)
3. allow("kim", 50)
4. allow("kim", 50)
5. allow("lee", 50)
6. allow("kim", 149)
7. allow("kim", 150)
Output:
True
True
True
False
True
False
True
Explanation:
Calls at the same second all count.
Kim uses up her three calls at second 50, so call 4 is refused.
Lee has her own count, so call 5 is allowed.
At second 149, the calls at 50 are still in the window.
At second 150, the window is seconds 51 to 150, so call 7 is allowed.

Constraints:

• limit is a whole number from 1 to 100,000.
• window is a whole number from 1 to 1,000,000,000.
• time is a whole number from 0 to 1,000,000,000.
• A user name has 1 to 10 lowercase letters.
• At most 100,000 calls are made on one limiter.