Waabi OA 面试真题解析：Message Delivery System 消息限流判断

Waabi Message Delivery System

Given the integer k, a list of messages as an array of strings, messages, and a sorted integer array timestamps representing the time at which each message arrived, report "true" for each message if it is delivered and "false" otherwise.

A message is dropped if the same message was already delivered in the last k seconds. Even if a message is dropped, it still counts as having arrived at the delivery service.

Function Description

Complete the function getMessageStatus in the editor below.

getMessageStatus takes the following arguments:

• INTEGER_ARRAY timestamps: the time at which messages arrive
• STRING_ARRAY messages: the messages to be delivered
• INTEGER k: the minimum gap between the same messages

Return

• STRING_ARRAY: the status of the messages

Example

Suppose n = 6, timestamps = [1, 4, 7, 10, 11, 14], messages = ["hello", "bye", "bye", "hello", "bye", "hello"], and k = 5.

["true", "true", "false", "true", "false", "false"]

Explanation

• At time 1, "hello" is delivered.
• At time 4, "bye" is delivered.
• At time 7, the previous "bye" arrived at time 4, so 7 - 4 < 5 and it is dropped.
• At time 10, the previous "hello" arrived at time 1, so 10 - 1 >= 5 and it is delivered.
• At time 11, the previous "bye" arrived at time 7, so 11 - 7 < 5 and it is dropped.
• At time 14, the previous "hello" arrived at time 10, so 14 - 10 < 5 and it is dropped.

这道 Waabi OA 题本质上是“按消息内容做限流判断”：对每条消息，用哈希表记录该消息上一次到达的时间，如果当前时间与上次到达时间的差值小于 k，就输出 false；否则输出 true，并把当前时间更新为新的 last seen。由于 timestamps 已排序，整题只需一次线性扫描，时间复杂度 O(n)，空间复杂度 O(消息种类数)。样例中同名消息在 k 秒内重复到达时会被丢弃，因此输出数组能直接反映每条请求是否被送达。