Katkat
Back

Implement a Log Rate Limiter

RobloxSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a thread-safe, time-windowed rate limiter using efficient data structures to track event timestamps.

Problem Statement

Design a rate limiter for a system that logs user actions. The system should only allow a log message if it has not been seen in the last 10 seconds. Each log message has a string content, and your implementation should handle concurrent calls.

Implement the Logger class:

  • Logger(): Initializes the object.
  • bool shouldLog(int timestamp, string message): Returns true if the message should be logged at the given timestamp, otherwise returns false. If a message is logged, it should be tracked so that subsequent attempts to log the same message within 10 seconds return false.

Constraints

  • timestamp will be in seconds and provided in non-decreasing order.
  • The number of concurrent calls is handled by the caller, but your state must remain consistent.
  • message is a non-empty string.

Examples

logger = Logger()
# Returns true, logs "foo" at t=1
logger.shouldLog(1, "foo") 
# Returns true, logs "bar" at t=2
logger.shouldLog(2, "bar") 
# Returns false, "foo" was logged at t=1 (1 < 1+10)
logger.shouldLog(3, "foo") 
# Returns false, "bar" was logged at t=2 (8 = 1+10
logger.shouldLog(11, "foo")

Hints

Hint 1

Use a Hash Map to store the mapping between a message string and the last timestamp it was successfully logged.

Hint 2

During each call to `shouldLog`, check if the message exists in the map and compare the difference between the current timestamp and the stored timestamp.

Hint 3

Consider how to prune or clean up the Hash Map if the system is expected to run indefinitely with a high cardinality of unique messages.

Follow-up questions

  • How would you modify your solution if the requirement changed to allow at most 'k' requests per 10-second window?
  • If the number of unique messages is extremely large, how would you optimize memory usage to prevent the map from growing indefinitely?
  • How would you adapt this implementation to work in a distributed system where multiple instances of the application share the same rate limit?