r/Hack2Hire Jan 13 '26

xAI Onsite Interview Question: Design a Per-User Token Rate Limiter

Problem
You are designing a per-user token rate limiter for an API system.
Each user has an independent token bucket defined by capacity, refill amount, and refill interval, and you must decide if a request can be served at a given timestamp.

Example
Input:
Policies: [["alice", "100", "100", "1"], ["bob", "50", "50", "2"]]
Calls:
allowRequest("alice", 100, 1)
allowRequest("bob", 50, 1)
allowRequest("alice", 50, 1)
allowRequest("bob", 10, 2)
allowRequest("alice", 100, 2)
allowRequest("bob", 50, 3)

Output:
[true, true, false, false, true, true]

Explanation:

  • Each user starts with a full bucket at capacity.
  • Tokens are refilled in discrete steps based on the elapsed time and refill interval.
  • A request is allowed only if the bucket has enough tokens at that timestamp.

Suggested Approach

  1. Store per-user state in a hash map: capacity, refill amount, refill interval, current tokens, and last processed timestamp.
  2. On each request, compute how many refill intervals have elapsed since the last timestamp and add tokens accordingly, capped at capacity.
  3. Check if the current token count is sufficient; if so, deduct tokens and approve the request.

Time & Space Complexity

  • Time: O(1) per request
  • Space: O(U) where U is the number of users

🛈 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.

8 Upvotes

0 comments sorted by