Logger that drops repeats within ten seconds

Scenario

A monitoring system writes a line to the log each time something fails. One broken service can send the same message thousands of times a second and bury everything else.

Your team lead says: "Print a message only if the same message was not printed in the last 10 seconds." The log lines arrive in time order, and you decide for each line when it arrives.

Your task

Write print_decisions(times, messages).

times[i] is the time of the i-th line, in seconds, and messages[i] is its text. The times never decrease.
A line is printed when its message was never printed before, or when its message was last printed at least 10 seconds earlier. Otherwise the line is dropped.
A dropped line changes nothing. It does not start a new quiet time.
Return a list with one number for each line: 1 if it is printed, 0 if it is dropped.

Examples

Example 1 (traced)#

text2 lines

Input:  times = [1, 2, 8, 11, 12, 21], messages = ["a", "a", "b", "a", "b", "a"]
Output: [1, 0, 1, 1, 0, 1]

The trace keeps the time each message was last printed.

Step	Line	Last printed	Decision
1	`a` at 1	none	1, now `a` is at 1
2	`a` at 2	`a` at 1, 1 second ago	0
3	`b` at 8	none	1, now `b` is at 8
4	`a` at 11	`a` at 1, 10 seconds ago	1, now `a` is at 11
5	`b` at 12	`b` at 8, 4 seconds ago	0
6	`a` at 21	`a` at 11, 10 seconds ago	1

Example 2#

text2 lines

Input:  times = [5, 5], messages = ["x", "x"]
Output: [1, 0]

Two equal lines in the same second: the second one is dropped.

Example 3#

text2 lines

Input:  times = [0, 10, 19, 20], messages = ["z", "z", "z", "z"]
Output: [1, 1, 0, 1]

The line at 10 is exactly 10 seconds after the line at 0, so it prints. The line at 19 is 9 seconds after the line at 10, so it is dropped. The line at 20 prints.

Constraints

1 ≤ times.length = messages.length ≤ 100,000
0 ≤ times[i] ≤ 1,000,000,000, and the times never decrease
Each message has 1 to 12 lowercase letters.

What does n ≤ 100,000 tell you?

Scanning every printed line for each new line costs up to one comparison for each printed line. With 100,000 lines that is up to about 5 × 10^9 comparisons.

A table from message to the time it was last printed answers each line in one step.

Scenario

A monitoring system writes a line to the log each time something fails. One broken service can send the same message thousands of times a second and bury everything else.

Your team lead says: "Print a message only if the same message was not printed in the last 10 seconds." The log lines arrive in time order, and you decide for each line when it arrives.

Your task

Write print_decisions(times, messages).

times[i] is the time of the i-th line, in seconds, and messages[i] is its text. The times never decrease.
A line is printed when its message was never printed before, or when its message was last printed at least 10 seconds earlier. Otherwise the line is dropped.
A dropped line changes nothing. It does not start a new quiet time.
Return a list with one number for each line: 1 if it is printed, 0 if it is dropped.

Examples

Example 1 (traced)#

text2 lines

Input:  times = [1, 2, 8, 11, 12, 21], messages = ["a", "a", "b", "a", "b", "a"]
Output: [1, 0, 1, 1, 0, 1]

The trace keeps the time each message was last printed.

Step	Line	Last printed	Decision
1	`a` at 1	none	1, now `a` is at 1
2	`a` at 2	`a` at 1, 1 second ago	0
3	`b` at 8	none	1, now `b` is at 8
4	`a` at 11	`a` at 1, 10 seconds ago	1, now `a` is at 11
5	`b` at 12	`b` at 8, 4 seconds ago	0
6	`a` at 21	`a` at 11, 10 seconds ago	1

Example 2#

text2 lines

Input:  times = [5, 5], messages = ["x", "x"]
Output: [1, 0]

Two equal lines in the same second: the second one is dropped.

Example 3#

text2 lines

Input:  times = [0, 10, 19, 20], messages = ["z", "z", "z", "z"]
Output: [1, 1, 0, 1]

The line at 10 is exactly 10 seconds after the line at 0, so it prints. The line at 19 is 9 seconds after the line at 10, so it is dropped. The line at 20 prints.

Constraints

1 ≤ times.length = messages.length ≤ 100,000
0 ≤ times[i] ≤ 1,000,000,000, and the times never decrease
Each message has 1 to 12 lowercase letters.

What does n ≤ 100,000 tell you?

Scanning every printed line for each new line costs up to one comparison for each printed line. With 100,000 lines that is up to about 5 × 10^9 comparisons.

A table from message to the time it was last printed answers each line in one step.