Solutions sit behind the flaps. Read the pattern, think, then open one step. If you already tried the problem, open everything.

The login box that sent twenty OTPs

A consumer app in Noida put "max 5 OTP requests per phone per hour" in the controller as a static Map<String, Integer>. It worked on one box. Testers were happy. Finance was not looking at the SMS bill yet.

They went to four API nodes behind a load balancer. Attackers hit all four. Each node allowed five. That is twenty OTPs in an hour, and Airtel still delivered every one. The map was not a policy so much as a local counter pretending to be a company rule.

I have seen the same lie with a "one login per second" check that lived in a singleton, and with a search cap that reset every time Kubernetes killed a pod. The engineer who wrote it was not careless. He wrote the check a single process can keep, and he forgot the load balancer does not care about his HashMap.

Design a rate limiter is the object design of a budget. Algorithm is a strategy, key is identity, allow is the API. The distributed version, Redis or a gateway, is the HLD sibling in Interview Problems. Do not mix the two exams unless they ask.

You give up an if in a controller. You gain a class you can test, and a sentence you can say when they add three more nodes: this object is the policy, and the state has to be shared.

Why Should You Care?

This is day 32. They often start with "write a RateLimiter class" and then zoom out to four nodes. The grade is whether you know which hat you are wearing. Candidates who start coding Redis in minute five never finish the bucket.

At work this is login, OTP, search, and initiate-payment. PhonePe and Razorpay put hard limits on those routes at the edge. A HashMap inside one JVM is a demo, and I want you to say that out loud even while you write the demo.

If you only memorise token-bucket maths, you will still put the counter in the controller and copy-paste it onto the next route. If you only say "Redis," you will have nothing on the board when they want a class. I want you to leave this page able to refill five tokens, deny the sixth at t=0.1, and then say why four nodes turn that five into twenty.

The Interview

Phase 1: Clarify and scope (Minutes 0-8)

Ask what you are counting, and where the count lives.

Question	Assume this if they leave it to you
Per what?	Per key: user id, IP, or phone
Algorithm?	Token bucket in v1
Return type?	`allow(key)` returns boolean. Fast deny
Thread-safe?	Yes. Lock the bucket, not the whole map
Multi-node?	Out of v1. Name Redis or the gateway
Blocking wait?	Out. That is a queue, not this class
Different limits per route?	Later. A factory of buckets

Then say what you are leaving out, and why. I am not implementing Redis, because that is shared state and a network, which is HLD. I am not writing a sliding window in v1, because token bucket already shows burst and refill. I am not blocking the caller until a token appears, because that API is a queue and we already have a pools lesson for that kind of wait.

Saying "out of scope" without the reason is a dodge. Saying "one process, token bucket, fast deny, and I will name Redis when you add nodes" is scope control.

Phase 2: Requirements (Minutes 8-12)

Functional requirements, as verbs:

Allow a request for a key if the budget has at least one token.
Deny immediately when the budget is empty.
Refill tokens over time, up to a capacity that is the burst.
Support many keys, each with its own bucket.
Swap the algorithm later without changing allow.

Non-functional requirements:

Two threads on the same key, one token left, must not both allow.
Unrelated keys must not wait on each other if we can avoid it.
allow is fail-fast. It does not sleep.
Multi-node is named, not coded. Local maps lie behind a load balancer.
Fail-open versus fail-closed, when the shared store is down, is a product sentence you say even in LLD.

The functional list is the demo. The non-functional list is why the maths lives on a strategy and the lock lives on one bucket. If you skip this list you will write a static map and then freeze when they say "four nodes."

Phase 3: Entities and class model (Minutes 12-22)

The limiter is a facade. The algorithm is a strategy. A key is a string.

💡 Swipe sideways, or tapClick or tap the diagram to pan & zoom

RateLimiter

buckets: MapKey to LimitAlgorithm |
capacity: intBurst size for new buckets |
refillPerSec: intSteady rate |

Method	Signature	What it does
`allow`	`boolean allow(String key, long nowMs)`	Get or create the bucket, then tryConsume

LimitAlgorithm

tryConsume: methodRefill, then spend one token, or return false |

TokenBucket

tokensMilli: longTokens in thousandths, so we do not use double |
lastMs: longLast refill time |
capacityMilli: longBurst, in thousandths |
refillPerSec: intTokens added per second |

Method	Signature	What it does
`tryConsume`	`boolean tryConsume(long nowMs)`	Refill, deny if below one token, else spend

In plain words: do not store tokens as double. Small refills drift. A bucket that should read 5.0 reads 4.999999999997, and == never says full. Store thousandths in a long. Full and empty are exact.

FixedWindow

count: intHits in the current window |
windowStartMs: longWhen this window opened |
limit: intMax hits per window |

I put FixedWindow on the board even if I only code TokenBucket, because they will ask about the edge burst. Five at 10:59 and five at 11:00 is ten in two seconds against a "five per second" sign. Token bucket spends the burst and then waits for refill. That sentence is the design.

The limiter does not embed bucket maths in allow. If they later want a sliding window on search and a token bucket on OTP, allow stays. A factory picks the algorithm for the route.

Phase 4: Code the spine (Minutes 22-40)

Write tryConsume and allow. If you only get one method, write the bucket, because that is where refill and the race meet.

Walk five tokens at t=0. Capacity is 5, refill is 1 per second. Five requests at t=0 all allow. The sixth at t=100 ms sees about 0.1 token and denies. At t=1000 ms you have about one token again. A fixed one-second window would have allowed five more at t=1000 even if you had just burst at t=900. Say that while you type.

import java.util.concurrent.ConcurrentHashMap;

interface LimitAlgorithm {
    boolean tryConsume(long nowMs);
}

final class TokenBucket implements LimitAlgorithm {
    private static final long UNIT = 1000L;
    private final long capacityMilli;
    private final int refillPerSec;
    private long tokensMilli;
    private long lastMs;

    TokenBucket(int capacity, int refillPerSec, long nowMs) {
        if (capacity < 1 || refillPerSec < 0) {
            throw new IllegalArgumentException("capacity or refill");
        }
        this.capacityMilli = capacity * UNIT;
        this.refillPerSec = refillPerSec;
        this.tokensMilli = this.capacityMilli;
        this.lastMs = nowMs;
    }

    @Override
    public synchronized boolean tryConsume(long nowMs) {
        refill(nowMs);
        if (tokensMilli < UNIT) {
            return false;
        }
        tokensMilli -= UNIT;
        return true;
    }

    private void refill(long nowMs) {
        if (nowMs < lastMs) {
            return;
        }
        long elapsed = nowMs - lastMs;
        tokensMilli = Math.min(capacityMilli, tokensMilli + elapsed * refillPerSec);
        lastMs = nowMs;
    }
}

final class FixedWindow implements LimitAlgorithm {
    private final int limit;
    private final long windowMs;
    private int count;
    private long windowStartMs;

    FixedWindow(int limit, long windowMs, long nowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
        this.windowStartMs = nowMs;
    }

    @Override
    public synchronized boolean tryConsume(long nowMs) {
        if (nowMs - windowStartMs >= windowMs) {
            count = 0;
            windowStartMs = nowMs;
        }
        if (count >= limit) {
            return false;
        }
        count += 1;
        return true;
    }
}

final class RateLimiter {
    private final int capacity;
    private final int refillPerSec;
    private final ConcurrentHashMap<String, LimitAlgorithm> buckets = new ConcurrentHashMap<>();

    RateLimiter(int capacity, int refillPerSec) {
        this.capacity = capacity;
        this.refillPerSec = refillPerSec;
    }

    boolean allow(String key, long nowMs) {
        if (key == null || key.isEmpty()) {
            throw new IllegalArgumentException("key");
        }
        LimitAlgorithm bucket = buckets.computeIfAbsent(
            key,
            k -> new TokenBucket(capacity, refillPerSec, nowMs)
        );
        return bucket.tryConsume(nowMs);
    }
}

Tokens live as thousandths, so a 100 ms wait adds 100 * refillPerSec thousandths and we never compare doubles. One request costs 1000. I refill before I spend, and I cap at capacity, so a quiet user does not bank a week of tokens.

tryConsume is synchronized on the bucket. Two threads with one token left cannot both pass the tokensMilli < UNIT check. allow does not lock the whole map. Unrelated phones do not wait on each other. computeIfAbsent creates one bucket per key without a second cook.

I still write FixedWindow so they can see the edge burst in code, and I do not use it in allow unless they ask to swap the strategy. The extra class is cheaper than a confused silence when they say "what about the window edge."

.NET (C#)

using System;
using System.Collections.Concurrent;

interface ILimitAlgorithm { bool TryConsume(long nowMs); }

sealed class TokenBucket : ILimitAlgorithm
{
    private const long Unit = 1000;
    private readonly long _cap;
    private readonly int _refill;
    private long _tokens;
    private long _last;
    private readonly object _gate = new();
    public TokenBucket(int capacity, int refillPerSec, long nowMs)
    {
        _cap = capacity * Unit;
        _refill = refillPerSec;
        _tokens = _cap;
        _last = nowMs;
    }
    public bool TryConsume(long nowMs)
    {
        lock (_gate)
        {
            if (nowMs >= _last)
            {
                _tokens = Math.Min(_cap, _tokens + (nowMs - _last) * _refill);
                _last = nowMs;
            }
            if (_tokens < Unit) return false;
            _tokens -= Unit;
            return true;
        }
    }
}

sealed class RateLimiter
{
    private readonly ConcurrentDictionary<string, ILimitAlgorithm> _buckets = new();
    private readonly int _cap, _refill;
    public RateLimiter(int cap, int refill) { _cap = cap; _refill = refill; }
    public bool Allow(string key, long nowMs) =>
        _buckets.GetOrAdd(key, _ => new TokenBucket(_cap, _refill, nowMs)).TryConsume(nowMs);
}

Node / TypeScript

// One process, one event loop. Two handlers still interleave on await.
// Keep tryConsume synchronous so the check and the spend do not yield.

interface LimitAlgorithm {
  tryConsume(nowMs: number): boolean;
}

class TokenBucket implements LimitAlgorithm {
  private tokensMilli: number;
  private lastMs: number;
  constructor(private capacity: number, private refillPerSec: number, nowMs: number) {
    this.tokensMilli = capacity * 1000;
    this.lastMs = nowMs;
  }
  tryConsume(nowMs: number): boolean {
    if (nowMs >= this.lastMs) {
      this.tokensMilli = Math.min(
        this.capacity * 1000,
        this.tokensMilli + (nowMs - this.lastMs) * this.refillPerSec,
      );
      this.lastMs = nowMs;
    }
    if (this.tokensMilli < 1000) return false;
    this.tokensMilli -= 1000;
    return true;
  }
}

class RateLimiter {
  private buckets = new Map<string, LimitAlgorithm>();
  constructor(private capacity: number, private refillPerSec: number) {}
  allow(key: string, nowMs: number): boolean {
    let b = this.buckets.get(key);
    if (!b) {
      b = new TokenBucket(this.capacity, this.refillPerSec, nowMs);
      this.buckets.set(key, b);
    }
    return b.tryConsume(nowMs);
  }
}

Python

import threading

class TokenBucket:
    def __init__(self, capacity: int, refill_per_sec: int, now_ms: int) -> None:
        self.capacity_milli = capacity * 1000
        self.refill_per_sec = refill_per_sec
        self.tokens_milli = self.capacity_milli
        self.last_ms = now_ms
        self._gate = threading.Lock()

    def try_consume(self, now_ms: int) -> bool:
        with self._gate:
            if now_ms >= self.last_ms:
                elapsed = now_ms - self.last_ms
                self.tokens_milli = min(
                    self.capacity_milli,
                    self.tokens_milli + elapsed * self.refill_per_sec,
                )
                self.last_ms = now_ms
            if self.tokens_milli < 1000:
                return False
            self.tokens_milli -= 1000
            return True

class RateLimiter:
    def __init__(self, capacity: int, refill_per_sec: int) -> None:
        self.capacity = capacity
        self.refill_per_sec = refill_per_sec
        self.buckets: dict[str, TokenBucket] = {}
        self._map_gate = threading.Lock()

    def allow(self, key: str, now_ms: int) -> bool:
        with self._map_gate:
            bucket = self.buckets.get(key)
            if bucket is None:
                bucket = TokenBucket(self.capacity, self.refill_per_sec, now_ms)
                self.buckets[key] = bucket
        return bucket.try_consume(now_ms)

The Python map lock is only around create. The spend lock is on the bucket. That is the same split as Java's computeIfAbsent plus synchronized on the instance. Node has no second thread, so the rule is: do not await inside tryConsume.

Walk one allowed OTP request and the retry that gets denied, start to finish. Everything above is mechanism. It clicks only when real numbers move through it.

Say the OTP route runs capacity 5, refill 1 per second, keyed by phone. Phone 9822011234 already burned four of its five OTPs in the last few hundred milliseconds, chasing a login that kept failing. Before this trace starts, its bucket already sits in buckets from that first request, with tokensMilli = 1000 (exactly one token left) and lastMs = 400.

The fifth OTP request calls allow("9822011234", 430).
buckets.computeIfAbsent("9822011234", ...) finds the bucket already in the map from earlier this hour, so no new TokenBucket gets built.
tryConsume(430) takes the bucket's lock and calls refill(430) first. elapsed = 430 - 400 = 30, so tokensMilli = min(5000, 1000 + 30 * 1) = 1030, and lastMs becomes 430.
tokensMilli is 1030, which is at least UNIT (1000), so the check passes. tokensMilli -= 1000 leaves 30, and tryConsume returns true.
allow returns true. The fifth OTP goes out over Airtel.

State right after: the bucket for 9822011234 holds tokensMilli = 30, about three hundredths of a token, and lastMs = 430.

An automated retry fires the very next request twenty milliseconds later.

allow("9822011234", 450) runs.
computeIfAbsent finds the same bucket instance again. Still no new bucket.
tryConsume(450) refills first: elapsed = 450 - 430 = 20, so tokensMilli = min(5000, 30 + 20 * 1) = 50.
tokensMilli is 50, which is below UNIT (1000), so tryConsume returns false without touching the token count further.
allow returns false. The controller answers with a 429, and the sixth OTP never reaches the SMS gateway.

The entire state for one phone number is two numbers, tokensMilli and lastMs. You can say whether the next request passes or gets a 429 without pulling out a stopwatch.

Phase 5: Concurrency and edge cases (Minutes 40-52)

Two threads, same phone, one token. Both read 1000 milli, both spend, both send an OTP. That is the tatkal story again. The lock is on the bucket. I do not lock every user to protect one key.

💡 Swipe sideways, or tapClick or tap the diagram to pan & zoom

Edge	Handling
Sixth request at t=100 ms after a burst of 5	Deny. About 0.1 token is not a request
Clock goes backwards	Do not refill. Avoid a jump in tokens
Empty key	Throw. A blank identity is not "everyone"
New key	Full burst. A new phone is not punished
Four nodes, local maps	Effective limit times four. Name shared state
Redis down, OTP route	Fail closed. Extra SMS is worse than a loud 429
Redis down, marketing page	Fail open. Availability over a perfect cap

The four-node row is the one they came for. I write the class, then I say the class is the policy. On four pods the budget must live in Redis or at the gateway, or you have four times the OTPs. I do not code the INCR. I draw the box, because drawing it is how you switch exams without pretending a HashMap became global.

Phase 6: Extend and wrap (Minutes 52-60)

Different limits per route is a factory. OTP gets capacity 5 per hour. Search gets a looser bucket. allow still takes a key. The factory picks which algorithm and which numbers.

Sliding window is more code and a smoother graph. I name it when they hate the fixed-window edge. I do not implement it unless they ask, because the hour is gone.

Multi-region is HLD. This object does not grow a region field. The edge in each region either shares a store or you accept a per-region budget.

The tradeoff you close on is extra types for one algorithm, against the day they want token bucket on pay and a fixed window on search. You also close on fail-closed versus fail-open, which is not a data-structure question. OTP fails closed. A public read can fail open. Say which, and why.

If you only have 30 minutes

Draw RateLimiter and TokenBucket, then write tryConsume with refill and a lock on the bucket. Walk five tokens at t=0 and a deny at t=100 ms. Name the fixed-window edge burst. Say four nodes need shared state, and OTP fails closed if that store is down.

The Decision Matrix

Situation	Choice	Why
Smooth average, allow a short burst	Token bucket	Burst is capacity, rate is refill
Simple hourly cap	Fixed window	Cheap, and you must say the edge burst
Need one budget across nodes	Shared counter or gateway	Local map is a lie
Money or OTP, store down	Fail closed	Extra SMS or extra debit is worse
Public read, store down	Fail open	A dead limiter should not hide the homepage
Same key, two threads	Lock the bucket	One token, one allow

Follow-ups they will ask

They will ask for the sixth request at t=0.1 after a burst of five. I deny. Tokens refill with time. A new second has not handed out a new burst.

They will ask why fixed window is not the same. Five at the end of one window and five at the start of the next is almost twice the sign on the door.

They will add four nodes. I put the HLD hat on. This object stays the policy. The count lives in Redis or at the gateway. A static map is still one process.

They will ask fail-open or fail-closed when Redis is down. OTP and pin-verify fail closed. A marketing page can fail open. I ask who gets the angry tweet, and I pick.

They will ask for 1000 QPS per user across 20 pods, each with capacity 1000. Effective cap is about 20,000. Shared state has to hold the real budget.

Common Mistakes

These are the ones that turn a five-OTP rule into a twenty-OTP bill.

People store counts in the controller, then they cannot test the policy, and they copy-paste it onto the next route.

People treat fixed window as token bucket, and they miss the edge burst.

People handle multi-node with a static map. Static is still one process.

People use double tokens and compare with ==. See Phase 3. Store thousandths in a long.

People make allow wait until a token exists. That is a queue. Default is fast deny.

People lock the whole limiter so one hot phone stalls every other user.

Key Takeaways

Limiter is the facade. Algorithm is the strategy. allow does not do maths.
Key is identity. Phone, IP, user, route. Say which.
v1 is one process. Multi-node is shared state, named not coded.
Lock the bucket. Not the world.
Fail-open versus fail-closed is a product call. OTP stays closed when the store is down.
Burst is capacity and rate is refill. Walk a sixth request at t=0.1 so they see the deny.

Design a Rate Limiter (LLD)