← Box Interview Insights

Box·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Two-hour coding round at Box for a software engineering role, focused entirely on building a leaky bucket rate limiter from scratch. The interviewer gave a class template to start from, but writing tests was on me, which I didn't fully expect.

Questions Asked (2)

Q1

Implement a leaky bucket rate limiter from scratch, starting with a basic single-threaded version.

Algorithms & Data StructuresSystem Design
Author's notes

They gave a class skeleton which helped a bit, but I still had to figure out the core logic myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: what does the leaky bucket control (requests per second), what happens when the bucket is full (reject or queue), and the bucket capacity and leak rate. Then implement a class with a method that checks and updates the water level based on elapsed time, using a simple timestamp and counter. Finally, test with edge cases like burst traffic and idle periods.

Pro tip: Use a monotonic clock (e.g., time.monotonic() in Python) to avoid issues with system clock adjustments, and mention that this single-threaded version is not thread-safe, hinting at the need for locks in a concurrent scenario.

1. Clarify requirements and constraints

Ask about the desired rate limit, bucket capacity, behavior when full (reject vs. queue), and whether it's per-user or global. Confirm the interface expected (e.g., allow_request() returning bool).

2. Design the data structure

Use a class with attributes: capacity (max tokens), leak_rate (tokens per second), current_tokens (or water level), and last_update timestamp. Explain that tokens represent water in the bucket.

3. Implement the leak logic

On each request, compute elapsed time since last_update, subtract leaked tokens (elapsed * leak_rate) from current_tokens, ensuring it doesn't go below zero. Update last_update to now.

4. Handle the request

If current_tokens + 1 <= capacity, increment current_tokens and allow the request; otherwise, reject (or queue, if specified). Return the decision.

5. Test and discuss edge cases

Test with bursts, idle periods, and exact capacity boundaries. Discuss potential improvements like thread safety, distributed implementation, and alternative algorithms (e.g., token bucket).

Key Points to Mention

  • Leaky bucket vs. token bucket: leaky bucket enforces a smooth output rate, while token bucket allows bursts up to capacity.
  • Time-based leak calculation: use elapsed time to compute how many tokens have leaked, avoiding a background thread.
  • Bucket capacity and leak rate parameters: these define the burst tolerance and average rate.
  • Behavior when bucket is full: typically reject or queue; clarify with interviewer.
  • Thread safety: single-threaded version is not safe; mention need for locks or atomic operations in concurrent scenarios.
  • Monotonic clock: use time.monotonic() to avoid issues with system time changes.

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

Q2

Extend your leaky bucket implementation to be thread-safe and support concurrent access.

System DesignTechnical Trade-offs
Author's notes

This is where I felt the pressure.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by identifying the shared mutable state in the leaky bucket (e.g., token count, last refill timestamp) and explain how you'll protect it using synchronization primitives like mutexes or atomics. Then discuss trade-offs between coarse-grained and fine-grained locking, and how to handle concurrent refill and consumption operations without introducing race conditions or deadlocks.

Pro tip: Mention that you'd use a lock-free approach with atomic operations for the token count and timestamp if performance is critical, but only after profiling shows contention; otherwise, a simple mutex is often sufficient and easier to maintain.

1. Identify shared mutable state

List all variables that are accessed and modified by multiple threads, such as the current token count and the last refill time. Explain why these need protection.

2. Choose synchronization primitives

Select appropriate primitives (e.g., mutex, read-write lock, atomic variables) based on the access patterns. Justify your choice by discussing contention and performance.

3. Design thread-safe operations

Describe how each operation (e.g., tryConsume, refill) will acquire and release locks or use atomics. Ensure that compound actions like check-and-decrement are atomic.

4. Handle refill and consumption atomically

Explain how to combine refill logic with consumption in a single critical section or using atomic compare-and-swap to avoid race conditions between refill and consumption.

5. Discuss trade-offs and alternatives

Compare coarse-grained locking (simple but may bottleneck) vs. fine-grained or lock-free approaches (complex but scalable). Mention potential issues like deadlocks, priority inversion, and fairness.

Key Points to Mention

  • Use of mutex or atomic operations to protect shared state
  • Atomicity of compound operations like check-and-decrement
  • Trade-offs between coarse-grained and fine-grained locking
  • Potential for lock contention and performance implications
  • Handling of refill and consumption concurrently without race conditions
  • Consideration of lock-free or wait-free algorithms for high concurrency

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