Live coding puzzles question 174 of 180 senior
Implement a rate limiter that allows N operations per second.
- A
synchronizedcounter reset by a sleeping thread - Correct: A token bucket: refill permits on a schedule and acquire one per operation, or compute the next allowed instant from the last, under a lock
Thread.sleep(1000 / n)in every caller- A fixed thread pool of size N
The simplest correct version is a Semaphore with N permits and a scheduled refill:
Semaphore permits = new Semaphore(n);
scheduler.scheduleAtFixedRate(
() -> permits.release(n - permits.availablePermits()), 1, 1, SECONDS);
void call() throws InterruptedException {
permits.acquire();
doWork();
}
Be ready for the critique: this is a fixed window, so 2N calls can land across a window boundary in a moment. A token bucket with fractional refill (tokens accumulate at n per second up to a burst capacity) smooths that out, and a leaky bucket removes bursts entirely.
Points for mentioning fairness (new Semaphore(n, true) so a caller is not starved), a timeout on
tryAcquire so callers are not blocked forever, and that in real systems the limiter belongs where
the resource is, not per JVM.