933. Message Rate Limiter

Easy1.5 points estimatedDesignHash TableData Stream4 hints
RPby Rohit Parihar

A logging service floods a console, so each distinct message text may be shown at most once every 10 seconds. Build RateLimiter with an empty constructor.

shouldPrint(timestamp, message) is called for every incoming line, in non-decreasing order of timestamp (seconds). Return true and remember the time if this message text has never been printed, or if at least 10 seconds have passed since the last time it was printed; otherwise return false. A line that is suppressed does not postpone the next allowed time. Several lines may share a timestamp. Different message texts are tracked independently, and texts must match exactly (including spaces and case).

Example 1

Input:
operations = ["RateLimiter","shouldPrint","shouldPrint","shouldPrint","shouldPrint","shouldPrint","shouldPrint"]arguments = [[],[3,"disk full"],[5,"cpu hot"],[9,"disk full"],[13,"disk full"],[14,"cpu hot"],[20,"cpu hot"]]
Output:
[null,true,true,false,true,false,true]
Explanation:

Disk full prints at 3, is blocked at 9 (only 6 later), and prints again at 13 (10 later). Cpu hot prints at 5, is blocked at 14, and prints at 20 because the last printed copy was at 5.

Example 2

Input:
operations = ["RateLimiter","shouldPrint","shouldPrint","shouldPrint","shouldPrint"]arguments = [[],[0,"boot"],[10,"boot"],[19,"boot"],[20,"boot"]]
Output:
[null,true,true,false,true]
Explanation:

The window is exactly 10: time 10 is allowed after time 0, time 19 is blocked after 10, and time 20 is allowed again.

Constraints

0 ≤ timestamp ≤ 109, non-decreasing across calls

0 ≤ message.length ≤ 30

At most 2000 calls in total

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(L) per call
Space
O(distinct messages)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.