FastPrep
Problem · Hash Table

Message Event Aggregation

Learn this problem
● MediumOpenAIFULLTIMEONSITE INTERVIEW

Problem statement

This exercise combines the first three reported parts of a message-event aggregation task.

Practice-version contract

To make the reported task executable, this version uses the interface and deterministic conventions below.

You are given a list of chat events and a list of query timestamps. Each event is encoded as a comma-separated string:

timestamp,userId,chatId,eventType

eventType is one of:

  • message: a message sent in the chat.
  • react: the user reacted in the chat, making the chat active for that user unless a later end_chat event ends it.
  • end_chat: the user ended the chat.

For each query time q, consider events in the inclusive five-minute window [q - 300, q]. Timestamps are integers measured in seconds.

For every user with at least one event in the window, compute:

  • messageCount: the number of message events for that user in the window.
  • activeChatCount: the number of distinct chats whose latest react or end_chat event in the window is react. A message event does not change a chat's active state.

Events may be given out of timestamp order. Process them by timestamp; when timestamps are equal, preserve their original input order.

Return one string for each query, in the original query order. Format a user's result as userId:messageCount:activeChatCount, sort users lexicographically by userId, and join entries with semicolons. If the window contains no events, return an empty string for that query.

Memory requirement

As the five-minute window advances, discard expired aggregation state. Apart from storage used to order the input and hold the output, retained counting and chat-state data must be proportional to the events and user-chat pairs in the current window, not to every chat seen earlier.

Function

aggregateMessageEvents(events: String[], queryTimes: int[]) → String[]

Examples

Example 1

events = ["10,u1,c1,message", "20,u1,c1,react", "80,u2,c5,message", "90,u2,c5,react", "200,u1,c1,end_chat", "260,u1,c2,react", "400,u1,c2,message"]queryTimes = [260, 500]return = ["u1:1:1;u2:1:1", "u1:1:1"]

At time 260, each user has one message in the window. Chat c2 is active for u1, while c5 is active for u2. At time 500, the window starts at 200; only u1 has events in the window, with one message and one active chat.

Example 2

events = ["300,u2,c8,end_chat", "40,u1,c1,react", "100,u1,c1,end_chat", "70,u1,c2,react", "20,u2,c8,react", "60,u1,c2,message", "110,u2,c8,message"]queryTimes = [120, 320]return = ["u1:1:1;u2:1:1", "u1:1:1;u2:1:0"]

The events are not given in timestamp order. At time 120, chat c8 is active for u2. At time 320, the later end_chat event makes it inactive. Chat c2 remains active for u1 at both query times.

Constraints

  • 0 <= events.length <= 10^5
  • 0 <= queryTimes.length <= 10^5
  • 0 <= timestamp, q <= 10^9
  • Every event has exactly four comma-separated fields and a valid eventType.
  • userId and chatId contain no commas, colons, or semicolons.

More OpenAI problems

drafts saved locally
public String[] aggregateMessageEvents(String[] events, int[] queryTimes) {
  // write your code here
}
events["10,u1,c1,message", "20,u1,c1,react", "80,u2,c5,message", "90,u2,c5,react", "200,u1,c1,end_chat", "260,u1,c2,react", "400,u1,c2,message"]
queryTimes[260, 500]
expected["u1:1:1;u2:1:1", "u1:1:1"]
checking account