Filter Repeated Robot Status Messages
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Filter Repeated Robot Status Messages
Implement `filter_messages(events)` for a robot status stream. Each event is a pair `[timestamp, message]`. Return, in input order, only the events that should be displayed to a human operator.
Display a message if it has never been displayed before, or if **strictly more than 10 seconds** have elapsed since that same message was last displayed. Hidden occurrences do not reset the interval.
### Function Signature
```python
def filter_messages(events: list[list]) -> list[list]:
```
### Example
```text
events = [
[10, "solar panel activated"],
[13, "solar panel activated"],
[20, "solar panel activated"],
[21, "solar panel activated"]
]
output = [
[10, "solar panel activated"],
[21, "solar panel activated"]
]
```
The events at times 13 and 20 are hidden. In particular, exactly 10 seconds is not strictly more than 10 seconds.
### Constraints
- `0 <= len(events) <= 200_000`
- Timestamps are non-negative integers in nondecreasing order.
- Each message is a nonempty string.
- Treat messages as case-sensitive exact strings.
### Clarifications
- Different messages have independent display histories.
- Return copies or the original event values; object identity is not significant.
### Hints
- Decide which event types are allowed to change the state associated with a message.
- Aim for expected linear time in the number of events.
Quick Answer: Filter a timestamped robot status stream so a message reappears only when strictly more than ten seconds have passed since its last displayed occurrence. Preserve input order, track each exact case-sensitive message independently, and ensure hidden repeats do not reset the interval.
From timestamped robot messages, retain an event if its exact message has never been displayed or if strictly more than ten seconds have elapsed since that message was last displayed. Hidden occurrences do not reset the display timestamp.
Constraints
- Timestamps are nonnegative integers in nondecreasing order.
- Messages are nonempty case-sensitive strings.
- Exactly ten elapsed seconds is not enough to display again.
- Different messages have independent histories.
- The input may contain up to 200,000 events.
Examples
Input: ([],)
Expected Output: []
Explanation: An empty stream displays nothing.
Input: ([[10, "solar panel activated"], [13, "solar panel activated"], [20, "solar panel activated"], [21, "solar panel activated"]],)
Expected Output: [[10, "solar panel activated"], [21, "solar panel activated"]]
Explanation: Exactly ten seconds is suppressed, while eleven seconds is displayed.
Hints
- Map each message to its most recent displayed timestamp.
- Update the map only when an event is retained.
- Preserve input order in the output.