Design a Logger Rate Limiter
Design a logger system that receives a stream of messages along with their timestamps. Only print each message if it is not printed in the last 10 seconds. Use a Hash Set and Hash Map.
Why Interviewers Ask This
Meta asks this to evaluate your ability to optimize space-time trade-offs in high-throughput systems. They specifically test if you can select the right data structures—Hash Maps for O(1) lookups and Hash Sets for deduplication—to solve rate-limiting constraints efficiently without blocking the main thread or consuming excessive memory.
How to Answer This Question
1. Clarify Requirements: Confirm the time window (10 seconds), input format (message, timestamp), and behavior for duplicate messages arriving exactly at the boundary.
2. Propose Data Structures: Suggest a HashMap where keys are messages and values are their last printed timestamps. Mention that while a HashSet is requested, a Map is more efficient here as it stores necessary temporal data directly.
3. Design Logic: Explain the algorithm: check if the message exists; if not, print and store timestamp. If yes, compare current time with stored time; if difference >= 10, update timestamp and print.
4. Analyze Complexity: Discuss O(1) average time complexity for both insertion and lookup, and O(N) space complexity where N is unique messages.
5. Edge Cases: Address clock skew, handling of very large message streams, and potential memory cleanup strategies like LRU eviction if the stream is infinite.
Key Points to Cover
- Explicitly choosing a HashMap over a HashSet because timestamp retrieval is required for the logic
- Demonstrating O(1) time complexity analysis for both read and write operations
- Clearly defining the condition for 'valid' printing (current_time - last_time >= 10)
- Addressing the memory management strategy for infinite streams of unique messages
- Handling edge cases like messages arriving exactly at the 10-second boundary
Sample Answer
To design this logger, I would first clarify that we need to prevent printing a specific message within a 10-second sliding window. For Meta's scale, efficiency is critical, so I propose using a HashMap rather than just…
Common Mistakes to Avoid
- Using a HashSet alone which forces inefficient storage of timestamps outside the primary structure
- Failing to handle the case where a message appears multiple times within the 10-second window
- Ignoring the possibility of an infinite stream leading to unbounded memory consumption
- Not discussing the time complexity implications of linear scans instead of hash-based lookups
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.