Dropbox·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Apr 2026

Summary

Dropbox system design round, one question the whole time: implement a thread-safe token bucket rate limiter. More depth expected than I anticipated, they really wanted to dig into the concurrency angle.

Questions Asked (1)

Design and implement a thread-safe Token Bucket rate limiter that supports concurrent access from multiple clients. Walk through the API, how tokens refill lazily over time, and the trade-offs versus other rate limiting approaches.

System DesignTechnical Trade-offsAlgorithms & Data Structures

Author's notes

I started with the basic struct and got the lazy refill math right pretty quickly (elapsed time times rate, capped at capacity).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., rate limit, burst capacity, thread safety, distributed vs. single-node) and then present a clean API with methods like tryAcquire() and acquire(). Explain the lazy refill mechanism using timestamps and atomic operations, then discuss trade-offs with other algorithms like leaky bucket and fixed window.

Pro tip: Emphasize that lazy refill avoids background threads and is more efficient; also mention that using a lock-free approach with atomic compare-and-swap can improve concurrency, but a mutex is simpler and often sufficient.

1. Clarify Requirements and Scope

Ask about expected throughput, burst tolerance, single-node vs. distributed, and whether blocking or non-blocking acquisition is needed. This shows you think about real-world constraints.

2. Define the API and Data Model

Propose methods like tryAcquire(tokens) and acquire(tokens, timeout). Define internal state: current tokens, last refill timestamp, capacity, and refill rate.

3. Explain Lazy Token Refill

Describe how tokens are replenished on each acquisition request by calculating elapsed time since last refill and adding tokens accordingly, capped at capacity. This avoids a background thread.

4. Ensure Thread Safety

Discuss using a mutex or atomic operations (e.g., compare-and-swap) to protect the state. Highlight the trade-off between simplicity (mutex) and scalability (lock-free).

5. Compare with Other Rate Limiting Approaches

Contrast token bucket with leaky bucket, fixed window, and sliding window. Mention pros/cons: token bucket allows bursts, is memory efficient, but can be tricky with distributed systems.

Key Points to Mention

Token bucket allows bursts up to capacity, making it suitable for APIs with variable traffic.
Lazy refill computes tokens based on elapsed time, avoiding periodic background tasks.
Thread safety can be achieved with a mutex or lock-free atomics; consider contention and performance.
Trade-offs: token bucket vs. leaky bucket (burst vs. smooth), fixed window (boundary spikes), sliding window (memory overhead).
Distributed rate limiting requires a shared store (e.g., Redis) and introduces synchronization challenges.
API design should include non-blocking tryAcquire and blocking acquire with timeout for flexibility.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.