Waabi OA Interview Question: 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.

This problem is a simple rate-limiting simulation by message name. Scan the messages in order, keep a hash map of the most recent timestamp for each distinct message, and compare the current timestamp with the previous one. If the gap is at least k, mark the message as delivered and update the map; otherwise mark it as false. The solution runs in O(n) time with hash-map space proportional to the number of unique messages.