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
▶
Class Trace
Step 1/3
TokenBucket abstract class

TokenBucket is abstract because it holds mutable state (capacity, tokens) and synchronized methods to ensure thread safety.

🎯 Tests whether candidate understands abstract class is needed to hold shared mutable state and synchronized methods for atomic token consumption and refill.
public abstract class TokenBucket {
    protected final int capacity;
    protected volatile int tokens;
    public synchronized boolean tryConsume(int tokens) {
        if (this.tokens < tokens) return false;
        this.tokens -= tokens;
        return true;
    }
    public abstract synchronized void refill();
}
RefillStrategy interface and FixedIntervalRefillStrategy realization

RefillStrategy is an interface to allow different refill algorithms, supporting OCP. FixedIntervalRefillStrategy implements it with synchronized refill method.

🎯 Tests if candidate knows interface cannot hold state but enables strategy pattern for refill behavior extensibility.
public interface RefillStrategy {
    void refill(TokenBucket bucket);
}
public class FixedIntervalRefillStrategy implements RefillStrategy {
    private final long intervalMillis;
    private final int tokensPerInterval;
    private long lastRefillTimestamp;
    public synchronized void refill(TokenBucket bucket) {
        long now = System.currentTimeMillis();
        if (now - lastRefillTimestamp >= intervalMillis) {
            bucket.tokens = Math.min(bucket.capacity, bucket.tokens + tokensPerInterval);
            lastRefillTimestamp = now;
        }
    }
}
RateLimiter composition with TokenBucket and RefillStrategy

RateLimiter composes TokenBucket and RefillStrategy, owning their lifecycle. It delegates tryAcquire to TokenBucket and triggers refill via strategy.

🎯 Tests if candidate understands composition lifecycle ownership and delegation of concurrency control to TokenBucket synchronized methods.
public class RateLimiter {
    private final TokenBucket bucket;
    private final RefillStrategy refillStrategy;
    public RateLimiter(TokenBucket bucket, RefillStrategy refillStrategy) {
        this.bucket = bucket;
        this.refillStrategy = refillStrategy;
    }
    public boolean tryAcquire() {
        return bucket.tryConsume(1);
    }
    public void refill() {
        refillStrategy.refill(bucket);
    }
}
📐
Class Diagram
Class Diagram
       +----------------------+
       |   <<Abstract>>       |
       |    TokenBucket       |
       +----------------------+
       | - capacity: int      |
       | - tokens: volatile int|
       +----------------------+
       | + synchronized boolean|
       |   tryConsume(int)    |
       | + synchronized void  |
       |   refill()           |
       +----------------------+
               │ extends
       +-----------------------------+
       | <<Interface>>               |
       |      RefillStrategy         |
       +-----------------------------+
       | + void refill(TokenBucket)  |
       +-----------------------------+
               ▲ realization
       +-----------------------------+
       | FixedIntervalRefillStrategy |
       +-----------------------------+
       | - intervalMillis: long      |
       | - tokensPerInterval: int    |
       | - lastRefillTimestamp: long|
       +-----------------------------+
       | + synchronized void refill()|
       +-----------------------------+
               │ composition
       +----------------------+
       |     RateLimiter      |
       +----------------------+
       | - bucket: TokenBucket|
       | - refillStrategy:    |
       |   RefillStrategy     |
       +----------------------+
       | + boolean tryAcquire()|
       +----------------------+
Design Rationale

This class diagram illustrates key Java OOP design decisions for a thread-safe Token Bucket rate limiter. TokenBucket is an abstract class because it holds mutable state (capacity and tokens) and synchronized methods to ensure atomic token consumption and refill, which interfaces cannot provide. The RefillStrategy interface enables the Strategy pattern, allowing different refill algorithms without modifying TokenBucket, enforcing the Open-Closed Principle. FixedIntervalRefillStrategy realizes this interface and uses synchronized refill to safely update tokens. RateLimiter composes TokenBucket and RefillStrategy, owning their lifecycle and delegating concurrency-sensitive operations to TokenBucket's synchronized methods. This design cleanly separates stateful token management from refill behavior, ensuring extensibility and thread safety.

Primary Focus

✓ Abstract class state vs interface + Strategy pattern OCP + Composition lifecycle + synchronized methods

Practice

(1/5)
1. In a messaging system design, the Conversation class has a private constructor and a static synchronized getInstance() method that returns the single instance per conversation ID. Which design pattern is applied here and why is this the correct use case?
easy
A. Factory pattern, because it creates Conversation objects on demand.
B. Prototype pattern, to clone existing Conversation instances for new conversations.
C. Builder pattern, to incrementally construct Conversation objects with optional parameters.
D. Singleton pattern, ensuring only one Conversation instance per conversation ID exists.

Solution

  1. Step 1: Identify the pattern from constructor and method

    The private constructor and static synchronized getInstance() method indicate Singleton pattern usage, controlling instance creation.

  2. Step 2: Understand why Singleton fits this use case

    Singleton ensures only one Conversation instance per conversation ID, preventing duplicate conversation objects and maintaining consistent state.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Private constructor + synchronized getInstance() -> Singleton pattern [check]
Hint: Private constructor + static getInstance() -> Singleton [check]
Common Mistakes:
2. A plugin system uses a PluginRegistry class that holds a private static instance and exposes a synchronized getInstance() method. Which design pattern is applied here, and why is this the correct choice for the registry?
easy
A. Factory pattern, because it creates plugin instances on demand.
B. Singleton pattern, ensuring only one registry instance manages all plugins globally.
C. Prototype pattern, to clone plugin instances efficiently.
D. Builder pattern, to construct complex plugin configurations step-by-step.

Solution

  1. Step 1: Identify the pattern from private static instance and synchronized getInstance()

    This is the Singleton pattern, which restricts instantiation to a single object and provides a global access point.

  2. Step 2: Explain why Singleton fits the PluginRegistry

    PluginRegistry must be unique to avoid inconsistent plugin state or duplicate registrations; Singleton ensures this global uniqueness.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Singleton ensures one global registry instance managing plugins [check]
Hint: Singleton = one global instance with synchronized access [check]
Common Mistakes:
3. In a plugin loader, the loadPlugin() method checks if a plugin is already loaded before loading it. Without synchronizing this method, what exact thread interleaving causes the same plugin to be loaded twice?
medium
A. Thread 1 checks isLoaded() -> false, context switch; Thread 2 checks isLoaded() -> false; both proceed to load the plugin.
B. Thread 1 and Thread 2 both wait on a lock, causing deadlock.
C. Thread 1 loads plugin, but Thread 2 never sees the updated loaded state due to caching.
D. Thread 1 and Thread 2 both call loadPlugin() simultaneously and both throw exceptions.

Solution

  1. Step 1: Trace the check-then-act sequence without synchronization

    Thread 1 calls isLoaded() and sees false, then context switches before loading.

  2. Step 2: Thread 2 also calls isLoaded() and sees false, both threads proceed to load plugin concurrently, causing duplicate loading.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Unsynchronized check-then-act allows double loading due to race [check]
Hint: Check-then-act without sync -> double load race condition [check]
Common Mistakes:
4. ElectricCar requires ChargingSpots in the Amazon Locker Service design. What is the minimum change to support this without modifying existing classes?
hard
A. Add ELECTRIC_CAR to VehicleType enum, CHARGING to SpotType enum, create ElectricCar subclass, and update SpotCompatibility map externally.
B. Modify Vehicle and Spot classes to add electric-specific fields and methods for charging compatibility.
C. Create a new ElectricCarChargingManager class that extends LockerManager and handles charging spots separately.
D. Add a boolean isElectric field to Vehicle and Spot classes and update existing logic to handle charging.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Enums VehicleType and SpotType can be extended with new constants without changing existing class logic. Creating ElectricCar subclass extends Vehicle cleanly.

  2. Step 2: Update SpotCompatibility map externally

    Maintaining compatibility mapping outside existing classes avoids modifying them, preserving OCP and avoiding class explosion.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Extend enums + subclass + external compatibility map -> minimal change [check]
Hint: Extend enums + subclass + external map -> no existing class change [check]
Common Mistakes:
5. ElectricCar requires ChargingSpots in the parking lot system. What is the minimum change to support this without modifying existing classes?
hard
A. Add ELECTRIC_CAR to VehicleType, CHARGING to SpotType, create ElectricCar extending Vehicle, and update SpotCompatibility.COMPATIBILITY_MAP accordingly.
B. Modify Vehicle class to include a chargingRequired flag and update all spot checks.
C. Create a new ChargingSpot class and modify ParkingLot to handle it specially.
D. Add a new interface Chargeable and make ElectricCar implement it, changing existing spot logic.

Solution

  1. Step 1: Identify extensibility without modifying existing classes

    Adding new enum values and a subclass extends functionality without changing existing class code, respecting OCP.

  2. Step 2: Evaluate options

    Modify Vehicle class to include a chargingRequired flag and update all spot checks. modifies Vehicle, violating OCP. Create a new ChargingSpot class and modify ParkingLot to handle it specially. requires modifying ParkingLot, violating minimal change. Add a new interface Chargeable and make ElectricCar implement it, changing existing spot logic. adds interface but requires changing spot logic, violating minimal change.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    New enums + subclass + compatibility map update -> minimal change [check]
Hint: Add enums + subclass + compatibility map, no existing class change [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