Problem framing
Design allowRequest(clientId) → boolean that enforces N requests per time window. Tests algorithm knowledge, per-client state, and thread-safety framing without building a distributed system.
| Algorithm | Behavior | Trade-off |
|---|---|---|
| Fixed window | Count per clock bucket | Burst at window boundaries (2× spike) |
| Sliding window | Count in rolling interval | More accurate, more memory/state |
| Token bucket | Refill tokens at rate R, burst B | Smooth traffic, allows controlled bursts |
| Leaky bucket | Queue/process at fixed rate | Shapes output rate, can drop or delay |
Class design
RateLimiter (interface)
└── TokenBucketLimiter
ClientState { tokens, lastRefillTime } // per clientId in Map
RateLimiterService { allowRequest(id), Map<String, ClientState> }Extract algorithm behind interface for OCP — interviewer may ask to swap fixed window for token bucket without rewriting callers.
Thread-safety and distribution
Single-threaded: plain HashMap. Multi-threaded: ConcurrentHashMap + synchronized block per client or Atomic token updates. Distributed (out of scope but mention): centralized Redis counter, race on read-modify-write — "I'd use Lua script or compare-and-swap in production."
Senior-level signal
Pick token bucket, explain refill math: tokens = min(capacity, tokens + (now - lastRefill) * rate). State boundary burst explicitly. Don't implement distributed consensus on the whiteboard — acknowledge and defer.
Testing hook
Expose package-private refill(now) or inject a Clock interface so unit tests advance time without Thread.sleep. Small design choice that signals production maturity.
Where this goes next
LRU Cache is the DSA/LLD crossover — HashMap + doubly-linked list with an eviction policy interface.
Further Reading
Practice Tasks (Optional)
Design or implement locally in any language — no autograding. Focus on class structure, extensibility, and being able to explain trade-offs out loud.
- Implement token-bucket rate limiter45m
Class RateLimiter with allowRequest(clientId) -> bool. Token bucket: refill rate + burst capacity. Single-threaded first; note what you'd add for thread-safety. ~50 lines in any language.