Basics
The concepts this component is built on. With these in mind, every line of the solution has a reason.
1.1Key concepts
One idea per card, in the order the solution uses them.
Capping how often something may happen, for example at most one refresh call per second.
A bucket holds tokens; each call spends one; tokens refill at a steady rate up to a maximum. A full bucket allows a short burst.
A clock that only moves forward and ignores changes to the device time. Elapsed-time maths must use it.
A limiter can make callers wait for a token or refuse them at once. User actions usually wait; background work can be dropped.
Question
What exactly you are asked to build, what must be true when you are done, and what to ask before you start.
2.1Prompt
The question as the interviewer asks it, and the requirements to check your solution against.
A bug made the app call /refresh in a tight loop on a million devices. Add a client-side limiter: allow small bursts, then at most one call per second, and make callers wait instead of failing.
Requirements
- Burst up to a capacity
- Steady refill rate
- Know how long to wait
- Shared safely across callers
- Testable with a fake clock
2.2Clarify first
Questions worth asking, and the answers this interviewer gives.
| You ask | Interviewer answers |
|---|---|
| Per endpoint or global? | Per endpoint group; create one limiter each. |
| Wait or fail? | User-initiated calls wait; background calls can drop. |
Detailed answer
The design decisions, the complete Kotlin solution, and a walk through it one block at a time.
3.1Design decisions
Settle these before writing code; each one shows up in the solution.
No timers: compute tokens from elapsed time whenever someone asks.
TimeSource.Monotonic ignores changes to the device time; tests pass a TestTimeSource and move it by hand.
The bucket is simple and easy to test; RateLimiter shares one behind a Mutex and sleeps outside the lock.
3.2Solution
Complete, compiling Kotlin with coroutines, built with warnings as errors and covered by tests/mobile/MobileTests.kt. The Java and TypeScript tabs do the same job with each language's own tools: Java compiled and run in our tests, TypeScript run in our tests.
1import kotlin.time.Duration2import kotlin.time.Duration.Companion.seconds3import kotlin.time.DurationUnit4import kotlin.time.TimeSource5import kotlinx.coroutines.delay6import kotlinx.coroutines.sync.Mutex7import kotlinx.coroutines.sync.withLock8 9/**10 * Token bucket: allows short bursts up to [capacity], then a steady [refillPerSecond].11 * Protects your own API from your own app (pull-to-refresh spam, retry storms).12 * Not thread-safe on its own: share it through [RateLimiter].13 */14class TokenBucket(15 val capacity: Double,16 val refillPerSecond: Double,17 private val clock: TimeSource.WithComparableMarks = TimeSource.Monotonic,18) {19 private var tokens = capacity20 private var lastRefill = clock.markNow()21 22 fun tryConsume(cost: Double = 1.0): Boolean {23 refill()24 if (tokens < cost) return false25 tokens -= cost26 return true27 }28 29 /** How long until [cost] tokens will be available. */30 fun waitTime(cost: Double = 1.0): Duration {31 refill()32 val missing = maxOf(0.0, cost - tokens)33 return (missing / refillPerSecond).seconds34 }35 36 private fun refill() {37 val now = clock.markNow()38 val elapsed = (now - lastRefill).toDouble(DurationUnit.SECONDS).coerceAtLeast(0.0)39 tokens = minOf(capacity, tokens + elapsed * refillPerSecond)40 lastRefill = now41 }42}43 44/** Shared limiter for every caller in the app: callers wait their turn instead of failing. */45class RateLimiter(capacity: Double, refillPerSecond: Double) {46 private val bucket = TokenBucket(capacity, refillPerSecond)47 private val lock = Mutex()48 49 suspend fun acquire(cost: Double = 1.0) {50 require(cost <= bucket.capacity) { "cost can never be satisfied" }51 while (true) {52 val wait = lock.withLock {53 if (bucket.tryConsume(cost)) return54 bucket.waitTime(cost)55 }56 delay(wait) // sleep outside the lock57 }58 }59}1import java.util.concurrent.TimeUnit;2import java.util.function.LongSupplier;3 4/** Shared limiter for every caller in the app: callers wait their turn instead of failing. */5public final class RateLimiter {6 /**7 * Token bucket: allows short bursts up to [capacity], then a steady [refillPerSecond].8 * Protects your own API from your own app (pull-to-refresh spam, retry storms).9 * Not thread-safe on its own: share it through RateLimiter.10 */11 public static final class TokenBucket {12 final double capacity;13 final double refillPerSecond;14 private final LongSupplier nanoClock;15 private double tokens;16 private long lastRefill;17 18 public TokenBucket(double capacity, double refillPerSecond, LongSupplier nanoClock) {19 this.capacity = capacity;20 this.refillPerSecond = refillPerSecond;21 this.nanoClock = nanoClock;22 this.tokens = capacity;23 this.lastRefill = nanoClock.getAsLong();24 }25 26 public boolean tryConsume(double cost) {27 refill();28 if (tokens < cost) return false;29 tokens -= cost;30 return true;31 }32 33 /** Nanoseconds until [cost] tokens will be available. */34 public long waitNanos(double cost) {35 refill();36 double missing = Math.max(0.0, cost - tokens);37 return (long) (missing / refillPerSecond * 1e9);38 }39 40 private void refill() {41 long now = nanoClock.getAsLong();42 double elapsed = Math.max(0L, now - lastRefill) / 1e9;43 tokens = Math.min(capacity, tokens + elapsed * refillPerSecond);44 lastRefill = now;45 }46 }47 48 @FunctionalInterface49 public interface Sleeper {50 void sleepNanos(long nanos) throws InterruptedException;51 }52 53 private final TokenBucket bucket;54 private final Sleeper sleeper;55 56 public RateLimiter(double capacity, double refillPerSecond) {57 this(capacity, refillPerSecond, System::nanoTime, nanos -> TimeUnit.NANOSECONDS.sleep(nanos));58 }59 60 public RateLimiter(double capacity, double refillPerSecond, LongSupplier nanoClock, Sleeper sleeper) {61 this.bucket = new TokenBucket(capacity, refillPerSecond, nanoClock);62 this.sleeper = sleeper;63 }64 65 public void acquire(double cost) throws InterruptedException {66 if (cost > bucket.capacity) throw new IllegalArgumentException("cost can never be satisfied");67 while (true) {68 long wait;69 synchronized (bucket) {70 if (bucket.tryConsume(cost)) return;71 wait = bucket.waitNanos(cost);72 }73 sleeper.sleepNanos(wait); // sleep outside the lock74 }75 }76}1/**2 * Token bucket: allows short bursts up to [capacity], then a steady [refillPerSecond].3 * Protects your own API from your own app (pull-to-refresh spam, retry storms).4 */5export class TokenBucket {6 readonly capacity: number;7 readonly refillPerSecond: number;8 private now: () => number;9 private tokens: number;10 private lastRefill: number;11 12 constructor(capacity: number, refillPerSecond: number, now: () => number = () => performance.now()) {13 this.capacity = capacity;14 this.refillPerSecond = refillPerSecond;15 this.now = now;16 this.tokens = capacity;17 this.lastRefill = now();18 }19 20 tryConsume(cost = 1): boolean {21 this.refill();22 if (this.tokens < cost) return false;23 this.tokens -= cost;24 return true;25 }26 27 /** Milliseconds until [cost] tokens will be available. */28 waitTime(cost = 1): number {29 this.refill();30 const missing = Math.max(0, cost - this.tokens);31 return (missing / this.refillPerSecond) * 1000;32 }33 34 private refill(): void {35 const now = this.now();36 const elapsedSeconds = Math.max(0, now - this.lastRefill) / 1000;37 this.tokens = Math.min(this.capacity, this.tokens + elapsedSeconds * this.refillPerSecond);38 this.lastRefill = now;39 }40}41 42/** Shared limiter for every caller in the app: callers wait their turn instead of failing. */43export class RateLimiter {44 private bucket: TokenBucket;45 private sleep: (ms: number) => Promise<void>;46 47 constructor(capacity: number, refillPerSecond: number, now?: () => number, sleep: (ms: number) => Promise<void> = (ms) => new Promise((r) => setTimeout(r, ms))) {48 this.bucket = new TokenBucket(capacity, refillPerSecond, now);49 this.sleep = sleep;50 }51 52 async acquire(cost = 1): Promise<void> {53 if (cost > this.bucket.capacity) throw new Error("cost can never be satisfied");54 for (;;) {55 if (this.bucket.tryConsume(cost)) return; // check and take happen in one step: no lock needed56 await this.sleep(this.bucket.waitTime(cost));57 }58 }59}3.3Line-by-line walkthrough
The same code in the order you would explain it in the room. The line numbers follow the Kotlin file; the Java and TypeScript tabs above have the same steps in the same order.
Start full
Tokens start at capacity, which allows an initial burst.
19 private var tokens = capacity20 private var lastRefill = clock.markNow()Consume if available
Refill first, then take tokens or refuse.
22 fun tryConsume(cost: Double = 1.0): Boolean {23 refill()24 if (tokens < cost) return false25 tokens -= cost26 return true27 }How long to wait
Missing tokens divided by the refill rate, as a Duration.
30 fun waitTime(cost: Double = 1.0): Duration {31 refill()32 val missing = maxOf(0.0, cost - tokens)33 return (missing / refillPerSecond).seconds34 }Lazy refill
Add elapsed × rate, capped at capacity. A monotonic clock avoids time-change bugs.
36 private fun refill() {37 val now = clock.markNow()38 val elapsed = (now - lastRefill).toDouble(DurationUnit.SECONDS).coerceAtLeast(0.0)39 tokens = minOf(capacity, tokens + elapsed * refillPerSecond)40 lastRefill = now41 }Callers wait their turn
Check under the lock; if tokens run short, delay exactly as long as needed outside the lock, then try again.
49 suspend fun acquire(cost: Double = 1.0) {50 require(cost <= bucket.capacity) { "cost can never be satisfied" }51 while (true) {52 val wait = lock.withLock {53 if (bucket.tryConsume(cost)) return54 bucket.waitTime(cost)55 }56 delay(wait) // sleep outside the lock57 }58 }Complexity: O(1) per call, no background timers
Q&A
The questions interviewers ask after the code works. Answer out loud, then open.
4.1Follow-up questions
Leaky bucket vs token bucket?
Server-side too?
Extra depth
The cases that break naive solutions, how the same design looks on iOS, and what to practise next.
5.1Edge cases
Say these before the interviewer does.
Show detailsHide details
- Cost bigger than capacity never succeeds (rejected up front)
- Clock going backwards (clamped to zero)
- Many waiters wake together (they retry and most wait again)
5.2On iOS
The same design in Swift and Apple's frameworks.
Show detailsHide details
| Approach | Swift / iOS |
|---|---|
| Swift | The same bucket as a struct (value type, easy to test) shared through an actor. |
| Clock | ContinuousClock, which is monotonic and injectable for tests. |