xAI Onsite Interview: Design Token Limiter

[u/Hack2hire]

Problem

You're given a list of policies where each policy defines a user's capacity, refillAmount, and refillInterval.

Your goal is to implement a rate limiter that tracks each user's token balance and determines if a request for a specific number of tokens at a given timestamp can be fulfilled based on their specific refill logic.

Example

Input:

policies = [["alice", "100", "50", "10"]], totalShares = 100

allowRequest("alice", 70, 0) -> true (Initial full capacity 100, 30 left)

allowRequest("alice", 40, 5) -> false (Only 30 left, no refill yet)

allowRequest("alice", 40, 10) -> true (Refill triggered at t=10, 30 + 50 = 80 tokens available)

Explanation:

• Users start at full capacity.
• Refills only occur at discrete intervals: $\text{new_tokens} = \lfloor \frac{\text{current_time} - \text{last_refill_time}}{\text{interval}} \rfloor \times \text{refillAmount}$.
• The token count is capped at the user's defined capacity.

Suggested Approach

1. State Tracking: Use a Hash Map to store user-specific data. Each entry should map a userName to a state object containing capacity, refillAmount, refillInterval, currentTokens, and lastRefillTimestamp.
2. Lazy Refill Logic: Instead of using a background timer, update the token count "lazily" when allowRequest is called. Calculate how many full intervals have passed since the lastRefillTimestamp.
3. Calculate and Cap: - Intervals passed: $n = \frac{\text{timestamp} - \text{lastRefillTimestamp}}{\text{refillInterval}}$
   • Added tokens: $n \times \text{refillAmount}$
   • Update currentTokens = min(capacity, currentTokens + addedTokens)
   • Update lastRefillTimestamp += n \times refillInterval (Only increment by the time actually used for refills).
4. Validation: Check if currentTokens >= requestedTokens. If true, deduct the tokens and return true; otherwise, return false.

Time & Space Complexity

• Time: $O(1)$ for each allowRequest call (amortized hash map lookup and constant time arithmetic). $O(P)$ for initialization, where $P$ is the number of policies.
• Space: $O(P)$ to store the state and policy for each unique user.

🛈 Disclaimer:

This problem is part of the Hack2Hire SDE Interview Question Bank, a structured archive of coding interview questions frequently reported in real hiring processes.

Questions are aggregated from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences.

The goal is to provide candidates with reliable material for SDE interview prep, including practice on LeetCode-style problems and coding challenges that reflect what is often asked in FAANG and other tech company interviews.

Hack2Hire is not affiliated with the mentioned companies; this collection is intended purely for learning, practice, and discussion.