Katkat
Back

Implement a rate limiter and a pub/sub API

GrammarlySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem evaluates your ability to implement a thread-safe rate limiter using the token bucket algorithm and design a lightweight, in-memory publisher-subscriber system.

Part 1: Rate Limiter

Implement a class RateLimiter that restricts the number of requests a user can make within a specified time window. Use the Token Bucket algorithm: each user has a bucket that starts with max_tokens. Tokens are added at a rate of refill_rate per second, up to the max_tokens capacity. If a token is available, the request proceeds; otherwise, it is rejected.

class RateLimiter:
    def __init__(self, max_tokens: int, refill_rate: float):
        # max_tokens: bucket capacity
        # refill_rate: tokens added per second
        pass

    def allow_request(self, user_id: str) -> bool:
        # Return True if request is allowed, False otherwise
        pass

Part 2: Pub/Sub API

Design a simple PubSub system that allows publishers to broadcast messages to subscribers interested in specific topics.

class PubSub:
    def subscribe(self, topic: str, callback: callable):
        """Registers a function to be called when a message is published to topic."""
        pass

    def publish(self, topic: str, message: str):
        """Sends message to all subscribers of the topic."""
        pass

Constraints & Considerations

  • The system must be thread-safe.
  • RateLimiter should handle multiple users independently.
  • Consider how the PubSub handles errors in subscriber callbacks.

Example

# Rate Limiter Example
limiter = RateLimiter(max_tokens=1, refill_rate=0.5) # 1 token, fills every 2s
limiter.allow_request("user_1") # Returns True
limiter.allow_request("user_1") # Returns False

Hints

Hint 1

For the rate limiter, track the last refill timestamp and current token count for each user in a thread-safe dictionary.

Hint 2

For the pub/sub, use a dictionary mapping topics to a list of subscriber callbacks; protect this structure with a Reentrant Lock (RLock).

Hint 3

When publishing, ensure that a slow or crashing subscriber callback does not block the entire publish operation or other subscribers.

Follow-up questions

  • How would you modify the rate limiter to persist data across application restarts using Redis?
  • If you had thousands of subscribers per topic, how would you optimize the publish operation?
  • How would you handle a scenario where the system needs to support 'at-least-once' delivery guarantees for the Pub/Sub system?