Test the Sliding-Window Rate Limiter
Hard About 30 min Free, no account needed
You're given a correct sliding-window rate limiter. Write the call sequences that prove the window slides and the limit holds.
The brief
A rate limiter allows only so many requests within a moving time window. The limiter here is already written and correct. Your job is to write the tests that prove it, which means designing the call sequences that fill the window, slide it, and probe its edges.
Here is the code under test:
public class RateLimiter
{
public RateLimiter(int maxRequests, int windowSize) { ... }
// True if a request at `timestamp` is allowed: fewer than maxRequests have occurred within the
// last windowSize time units. Timestamps are non-decreasing. An allowed request is recorded;
// a rejected one is not.
public bool Allow(int timestamp) { ... }
}Write a Tests class. Each public, parameterless method is one test: it passes if it runs
without throwing and fails when an assertion throws. Build a limiter, drive a sequence of calls,
then assert. A tiny assertion library is in scope (no using needed):
Assert.True(condition); Assert.False(condition);
Assert.Equal(expected, actual); Assert.NotEqual(a, b);
Assert.Null(x); Assert.NotNull(x);
Assert.Throws<SomeException>(() => ...);
var limiter = new RateLimiter(2, 10);
Assert.True(limiter.Allow(0));Your suite is run twice over:
- Against the correct
RateLimiterabove, every one of your tests must pass. - Against a set of planted-bug "mutants", broken limiters you never see. A mutant is caught when at least one of your tests fails against it.
You pass when your suite is green on the correct code and catches at least 5 of the 6 mutants. The mutants allow one too many, never slide the window, record rejected requests, get the window edge off by one, or never enforce the limit at all. A single Allow call catches none of them. Design sequences that fill the window and then slide it. Stuck? Reveal the model suite to see what thorough looks like.
Starter code
// Write tests for the `RateLimiter` class. Each public, parameterless method is one test; it passes
// if it doesn't throw. Make your suite pass on the correct code AND catch the hidden buggy versions.
// A single request proves nothing. The behavior is in the limit, and in the window sliding over time.
public class Tests
{
public void A_first_request_is_allowed()
{
var limiter = new RateLimiter(2, 10);
Assert.True(limiter.Allow(0));
}
// TODO: drive sequences that hit the limit, slide the window, and check a rejected request is not recorded.
}How it is graded
You write the tests. A suite passes only when it stays green on correct code and turns enough faulty implementations red.
Related guides
What it practices
- Stateful testing
- Drive call sequences and state-machine transitions, not just single calls.
- Boundary value testing
- Pin behavior exactly at, just below and just above every boundary.
- Mutation testing
- Write tests strong enough to catch planted bugs, not just to pass.
Related katas
- Test Fenced Lease Ownership Hard Free Exercise expiry, renewal, ownership transfer, and stale-token rejection in a lease that must never reuse authority.
- Test the Progressive Tax Hard Free You're given a correct marginal income-tax calculator. Write the tests that prove each band is taxed marginally, not flatly.
- Test the Interval Merger Hard Free You're given a correct interval merger. Write the tests that pin overlap, touching, containment, and sorting.
- Test the LRU Cache Hard Free You're given a correct LRU cache. Write the call sequences that prove it evicts the least-recently-used entry.