Bird
Raised Fist0

Design a Rate Limiter Class - Token Bucket OOP Implementation with Thread Safety

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Rate Limiter Class - Token Bucket OOP Implementation with Thread Safety
Thread-safe Token Bucket rate limiter using synchronized methods and volatile state for concurrency control
hardInfrastructure and Utility SystemsFreq: medium
Prerequisites:Token Bucket algorithmThread Safety in JavaJava concurrency primitives (synchronized, volatile, AtomicLong)
⚙️
Functional Requirements
  • Allow multiple concurrent threads to request tokens safely
  • Refill tokens at a configured rate up to a maximum capacity
  • Provide atomic token acquisition to prevent over-consumption
  • Support dynamic configuration of refill rate and bucket capacity
  • Expose current token count for monitoring
  • Reject requests immediately if insufficient tokens are available
  • Ensure minimal latency for token acquisition under concurrency
👤
Use Cases
  • ClientThread requests permission to proceed if tokens are available
  • RateLimiter refills tokens periodically or on demand
  • RateLimiterAdmin configures rate limits and bucket capacity
  • MonitoringService queries current token count and usage statistics
  • ClientThread handles token acquisition failure gracefully
🧑‍💻
Actors
  • ClientThread
  • RateLimiterAdmin
  • MonitoringService
❓
Clarifying Questions to Ask
  • How many concurrent threads will access the rate limiter? (Single or multiple gates?)
  • Is the refill rate fixed or dynamically adjustable at runtime?
  • Should token acquisition block or return immediately if tokens unavailable?
  • Are tokens refilled periodically via a scheduled task or on-demand?
  • What is the expected maximum bucket capacity and token request size?
  • Is there a need for priority or weighted token requests?
  • How should the system behave under burst traffic exceeding capacity?
Out of Scope
✗ Distributed rate limiting across multiple nodes
✗ Persistence of token bucket state across restarts
✗ Complex pricing or billing strategies based on token usage
🔢
Enumerations
enum RefillStrategyType
FIXED_INTERVAL | ON_DEMAND
Defines refill strategies explicitly to prevent typo bugs and enable exhaustive switch statements for refill logic.
enum TokenAcquisitionResult
SUCCESS | FAILURE_INSUFFICIENT_TOKENS
Encapsulates token acquisition outcomes to avoid ambiguous boolean returns and support future extension.
📦
TokenBucket
6 fields
private final long capacityprivate volatile long currentTokensprivate final long refillTokensPerIntervalprivate final long refillIntervalMillisprivate volatile long lastRefillTimestampprivate final RefillStrategy refillStrategy
Maintain token count, enforce capacity, refill tokens according to strategy, and provide thread-safe token acquisition.
Why thisUses synchronized methods and volatile variables to ensure thread safety and visibility in Java concurrency without external libraries.
Why notAvoids complex lock-free or external concurrency libraries to keep implementation simple and maintainable.
Key Methods
public synchronized TokenAcquisitionResult tryConsume(long tokens)Atomically attempts to consume the requested number of tokens if available; returns success or failure.
public synchronized void refill()Refills tokens based on elapsed time and refill strategy, ensuring capacity is not exceeded.
public synchronized long getCurrentTokens()Returns the current number of tokens available in a thread-safe manner.
public synchronized void setRefillStrategy(RefillStrategy strategy)Allows dynamic replacement of the refill strategy at runtime.
📦
RefillStrategy
0 fields
Defines the contract for token refill behavior; implemented by concrete strategies.
Why thisStrategy pattern enables flexible refill logic without modifying TokenBucket, supporting Open/Closed principle.
Why notAvoids hardcoding refill logic inside TokenBucket, which would reduce extensibility and increase coupling.
Key Methods
public long refillTokens(long currentTokens, long capacity, long lastRefillTimestamp)Calculates the number of tokens to add based on current state and returns the new token count.
📦
FixedIntervalRefillStrategy
2 fields
private final long refillTokensprivate final long refillIntervalMillis
Implements token refill logic that adds tokens at fixed time intervals.
Why thisSuitable for predictable, periodic token refills common in rate limiting scenarios.
Why notOther strategies like on-demand do not suit fixed periodic refill requirements.
Key Methods
public long refillTokens(long currentTokens, long capacity, long lastRefillTimestamp)Calculates tokens to add based on elapsed intervals since last refill.
📦
OnDemandRefillStrategy
1 fields
private final long refillTokens
Implements token refill logic that refills tokens only when explicitly triggered.
Why thisAllows manual or event-driven token refills, useful for bursty or irregular traffic patterns.
Why notFixed interval refill unsuitable for on-demand refill scenarios.
Key Methods
public long refillTokens(long currentTokens, long capacity, long lastRefillTimestamp)Returns currentTokens unchanged; refill triggered externally.
📦
RateLimiter
1 fields
private final TokenBucket tokenBucket
Facade class exposing rate limiting API to clients, delegating token management to TokenBucket.
Why thisProvides a simple interface for clients while encapsulating concurrency and refill logic inside TokenBucket.
Why notDirect client interaction with TokenBucket would expose internal concurrency details and increase coupling.
Key Methods
public boolean tryAcquire(long tokens)Attempts to acquire tokens from the underlying TokenBucket; returns true if successful.
public long getAvailableTokens()Returns the current number of tokens available.
public void setRefillStrategy(RefillStrategy strategy)Allows changing the refill strategy dynamically.
🔗
Relationships
RateLimiter◆──►TokenBucket[1 to 1]
compositionTokenBucket lifecycle bound to RateLimiter; destroyed together
TokenBucket◇──►RefillStrategy[1 to 1]
aggregationRefillStrategy can exist independently and be replaced at runtime
FixedIntervalRefillStrategy──►RefillStrategy[1 to 1]
inheritanceFixedIntervalRefillStrategy is a subtype of RefillStrategy
OnDemandRefillStrategy──►RefillStrategy[1 to 1]
inheritanceOnDemandRefillStrategy is a subtype of RefillStrategy

Practice

(1/5)
1. A class CarBuilder constructs a Car object step-by-step using methods like setEngine(), setWheels(), and finally build(). The Car constructor is private. Which design pattern is applied here and why is it the correct choice?
easy
A. Builder pattern, because it separates complex object construction from its representation, allowing stepwise creation.
B. Factory Method pattern, because it creates objects through inheritance and subclasses.
C. Prototype pattern, because it clones existing objects to create new ones efficiently.
D. Singleton pattern, because it ensures only one instance of Car exists.

Solution

  1. Step 1: Identify the construction process

    The class uses multiple setter methods to configure parts of the object before finalizing with build(), indicating stepwise construction.

  2. Step 2: Match pattern intent

    Builder pattern separates construction from representation, ideal for complex objects with many optional parts. Factory Method uses inheritance, Prototype clones objects, Singleton restricts instance count.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stepwise object creation with private constructor -> Builder pattern [check]
Hint: Stepwise construction with private constructor -> Builder pattern [check]
Common Mistakes:
2. In implementing a chain of handlers in Java, should the Handler interface be an abstract class or an interface, and why?
easy
A. Interface, because handlers only define a contract without shared state, enabling flexible implementations.
B. Interface, because it enforces inheritance and prevents multiple implementations.
C. Abstract class, because Java interfaces cannot have default method implementations.
D. Abstract class, because it allows sharing common state and behavior among handlers.

Solution

  1. Step 1: Understand Handler role

    Handlers define a contract to process or pass requests; they typically do not share mutable state.

  2. Step 2: Evaluate Java features

    Interfaces allow multiple inheritance and default methods (since Java 8), promoting flexibility; abstract classes share state but restrict inheritance.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Interface defines contract without forcing shared state [check]
Hint: Interface for contract, abstract class for shared state [check]
Common Mistakes:
3. In designing a notification channel abstraction, should NotificationChannel be an abstract class or an interface? Consider that each channel has state like connection status and common methods like connect() and send(). Why?
easy
A. Abstract class, because it can hold shared state and provide default method implementations.
B. Abstract class, because interfaces cannot define method signatures.
C. Interface, because Java interfaces can now have default methods with state variables.
D. Interface, because it allows multiple inheritance and all methods are stateless contracts.

Solution

  1. Step 1: Analyze state and behavior requirements

    NotificationChannel needs to hold connection status (state) and provide common method implementations.

  2. Step 2: Choose between interface and abstract class

    Interfaces cannot hold instance state; abstract classes can hold state and provide default behavior, making abstract class the correct choice.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Abstract class supports shared state and default methods [check]
Hint: Stateful base -> abstract class; stateless contract -> interface [check]
Common Mistakes:
4. In designing the Workflow Engine, should the Condition component be an abstract class or an interface, and why?
easy
A. Interface, because Conditions only define a contract for evaluation without shared state, allowing multiple implementations.
B. Abstract class, because Java interfaces cannot have default methods for condition evaluation logic.
C. Abstract class, because Conditions share common state and behavior that subclasses must inherit.
D. Interface, because it allows Conditions to hold mutable state safely across threads.

Solution

  1. Step 1: Analyze Condition's role

    Conditions define evaluation logic without requiring shared state; they represent a contract for boolean checks.

  2. Step 2: Interface vs Abstract class

    Interface suits stateless behavior contracts and allows multiple inheritance; abstract class implies shared state, which is not needed and limits flexibility.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Condition defines behavior only -> interface [check]
Hint: Stateless behavior contracts -> interface, not abstract class [check]
Common Mistakes:
5. To support ElectricCar and ChargingSpot in the existing parking system using Chain of Responsibility, what is the minimum change that respects extensibility and avoids modifying existing classes?
hard
A. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility.COMPATIBILITY_MAP accordingly.
B. Modify Vehicle and Spot classes to add boolean isElectric and isChargingSpot flags, then update existing handlers to check these flags.
C. Create a new ElectricCarHandler in the chain that handles electric cars and charging spots, modifying the chain setup to include it.
D. Add a new method in Vehicle interface for charging compatibility and implement it in ElectricCar, modifying existing handlers to call it.

Solution

  1. Step 1: Identify extensibility requirements

    Adding ElectricCar and ChargingSpot should not require modifying existing classes to avoid breaking OCP.

  2. Step 2: Evaluate options

    Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility.COMPATIBILITY_MAP accordingly. modifies enums and compatibility map, changing existing code; Modify Vehicle and Spot classes to add boolean isElectric and isChargingSpot flags, then update existing handlers to check these flags. adds flags and updates handlers without changing existing class hierarchies; Create a new ElectricCarHandler in the chain that handles electric cars and charging spots, modifying the chain setup to include it. modifies chain setup, which is acceptable but may require modifying chain initialization; Add a new method in Vehicle interface for charging compatibility and implement it in ElectricCar, modifying existing handlers to call it. modifies Vehicle interface, breaking existing implementations.

  3. Step 3: Choose minimal invasive approach

    Modify Vehicle and Spot classes to add boolean isElectric and isChargingSpot flags, then update existing handlers to check these flags. adds minimal changes with flags and updates handlers, avoiding class explosion or interface changes.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Flags added, existing classes unchanged, handlers updated [check]
Hint: Add flags and update handlers, avoid modifying classes [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard