How do you approach Logger Rate Limiter?

Use a hash map from message to the last timestamp at which it was printed.

What is the time complexity of Logger Rate Limiter?

Time complexity: O(1) average per operation.. Space complexity: O(m), where m is the number of distinct messages seen..

What are common mistakes on Logger Rate Limiter?

Hitting the stated complexity for one operation by making another linear. These problems grade every operation. Keeping two structures in sync but updating only one of them on the delete path. Skipping the capacity edges: insert when full, read when empty.

gitGood.dev

← Back to problems

Logger Rate Limiter

EasyObject-Oriented Design

Description

Design a logger that receives a stream of messages with timestamps and decides whether each message should be printed. A message may be printed only if it has NOT been printed in the last 10 seconds.

shouldPrint(timestamp, message) returns true if the message can be printed at the given timestamp (it was never printed before, or its last printed time is <= timestamp - 10). When it returns true, it records this timestamp as the message's last printed time. If it returns false, nothing is recorded.

Timestamps arrive in non-decreasing order.

Implement the function logger(operations) where operations is a list of [op, ...args]: ["shouldPrint", timestamp, message]. Return the list of results, one per operation (use null for operations that return nothing - though every operation here returns a boolean).

Example 1

Input: operations = [["shouldPrint",1,"foo"],["shouldPrint",2,"bar"],["shouldPrint",3,"foo"],["shouldPrint",8,"bar"],["shouldPrint",10,"foo"],["shouldPrint",11,"foo"]]

Output: [true, true, false, false, false, true]

Example 2

Input: operations = [["shouldPrint",1,"a"],["shouldPrint",11,"a"],["shouldPrint",21,"a"]]

Output: [true, true, true]

Example 3

Input: operations = [["shouldPrint",0,"hi"],["shouldPrint",9,"hi"],["shouldPrint",10,"hi"]]

Output: [true, false, true]

Constraints

0 <= timestamp <= 10^9. Timestamps are non-decreasing. message is a non-empty string. At most 10000 operations.

Logger Rate Limiter: approach, complexity and pitfalls

An easy design problem, graded against 6 test cases (3 of them hidden).

The pattern: Design

Build a working data structure to an API - LRU caches, rate limiters, and iterators.

Reach for it when you see: "Design a class supporting these operations in O(1)" - an API rather than a single function.

If you are stuck

Show the 3-step hint ladder

Use a hash map from message to the last timestamp at which it was printed.
A message is allowed if it is not in the map, or if its stored timestamp is <= timestamp - 10. Only update the map when you return true.
Watch the boundary: a message last printed at time T can be printed again exactly at time T + 10, but not at T + 9.

The optimal approach

Show the approach: The approach

Maintain a dictionary mapping each message to the last timestamp it was printed. On `shouldPrint(timestamp, message)`, allow it (return true and update the stored time) when the message is unseen or its last time is `<= timestamp - 10`; otherwise return false and leave the map unchanged. Map lookups and updates are O(1) on average.

Time: O(1) average per operation.
Space: O(m), where m is the number of distinct messages seen.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Design mistakes

These apply to the pattern as a whole, not just this problem.

Hitting the stated complexity for one operation by making another linear. These problems grade every operation.
Keeping two structures in sync but updating only one of them on the delete path.
Skipping the capacity edges: insert when full, read when empty.