Out-of-Order Logger Rate Limiter
GoogleFULLTIMEONSITE INTERVIEWProblem statement
A logger receives messages whose integer event timestamps may arrive out of order. Process the paired arrays timestamps and messages in input order.
For an event with timestamp t and message m, print it exactly when no earlier accepted event for m has an event timestamp in the inclusive interval [t - 9, t]. An earlier-processed event whose timestamp is greater than t does not block this event. A rejected event does not update the accepted history, and decisions are never revised retroactively.
Examples
Example 1
timestamps = [10,15,5,20]messages = ["foo","foo","foo","foo"]return = [true,false,true,true]The event at 10 prints, so the one at 15 is suppressed. Timestamp 5 then prints because the already processed timestamp 10 is later than its query interval. Timestamp 20 is ten seconds after the accepted event at 10, so it also prints.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 1 more worked example, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.