Prioritized Notification Dispatcher
Airbnb's operations rely on efficient communication and timely response to critical events, ranging from urgent guest support requests to system health alerts. As a STAFF engineer, you're tasked with designing a central NotificationDispatcher system. This system must prioritize and dispatch notifications based on multiple criteria, ensuring that the most urgent and relevant messages are handled first, while also gracefully discarding notifications that have become stale.
This problem challenges your ability to design a system using priority queues to manage dynamic, time-sensitive data, a common pattern in high-throughput, real-time systems at Airbnb.
Implement the NotificationDispatcher class with the following methods:
constructor(): Initializes the notification dispatcher.
addNotification(id: string, priority: number, timestamp: number, expirationTime: number): void: Adds a new notification to the system. Each notification has a unique id, a priority level, the timestamp when it was created/received, and an expirationTime after which it is no longer relevant.
dispatchNotification(currentTime: number): string | null: Retrieves and removes the most urgent active notification from the system. An active notification is one whose expirationTime is strictly greater than the provided currentTime. If multiple notifications are equally urgent, the tie-breaking rules are:
priority comes first.priority, the one with the earliest expirationTime comes first.priority and expirationTime, the one with the earliest timestamp comes first.If no active notifications are available, return null.
Class Name: NotificationDispatcher
constructor():
void (implicitly null in test cases).addNotification(id: string, priority: number, timestamp: number, expirationTime: number):
id: string - A unique identifier for the notification.priority: number - An integer representing the urgency (higher value = higher urgency, e.g., 100 is more urgent than 1).timestamp: number - The time (e.g., Unix epoch milliseconds) when the notification was created/received.expirationTime: number - The time (e.g., Unix epoch milliseconds) after which the notification is no longer valid. Must be >= timestamp.void (implicitly null in test cases).dispatchNotification(currentTime: number):
currentTime: number - The current time (e.g., Unix epoch milliseconds) at which the dispatch request is made.string | null - The id of the most urgent active notification, or null if none exist.ids provided to addNotification will be unique.timestamp, expirationTime, and currentTime are all in the same arbitrary time unit (e.g., milliseconds since epoch).dispatchNotification is called when no active notifications are present, it should return null.Examples
Example 1
Input:
operations = ["NotificationDispatcher","addNotification","addNotification","dispatchNotification","addNotification","dispatchNotification","dispatchNotification","dispatchNotification"], params = [[],["N1",5,1000,5000],["N2",3,1100,6000],[2000],["N3",10,2500,3000],[3000],[5500],[6000]]
Output:
[null,null,null,"N1",null,"N2",null,null]
Note:
NotificationDispatcher(): Initializes the system.addNotification("N1", 5, 1000, 5000): Adds N1.addNotification("N2", 3, 1100, 6000): Adds N2.
Current notifications in heap (conceptual order): N1 (P:5, E:5000, T:1000) is more urgent than N2 (P:3, E:6000, T:1100) due to higher priority.dispatchNotification(2000):
5000 > 2000 is true. N1 is active. Dispatch N1.addNotification("N3", 10, 2500, 3000): Adds N3.
Current notifications in heap: N3 (P:10, E:3000, T:2500) is more urgent than N2 (P:3, E:6000, T:1100) due to higher priority.dispatchNotification(3000):
3000 > 3000 is false. N3 is expired. Remove N3 from heap.6000 > 3000 is true. N2 is active. Dispatch N2.dispatchNotification(5500): Heap is empty. Returns null.dispatchNotification(6000): Heap is empty. Returns null.Example 2
Input:
operations = ["NotificationDispatcher","addNotification","addNotification","addNotification","dispatchNotification","dispatchNotification","dispatchNotification"], params = [[],["A",5,100,1000],["B",5,120,900],["C",5,110,900],[500],[500],[500]]
Output:
[null,null,null,null,"C","B","A"]
Note:
NotificationDispatcher(): Initializes the system.addNotification("A", 5, 100, 1000): Adds A.addNotification("B", 5, 120, 900): Adds B.addNotification("C", 5, 110, 900): Adds C.
Notifications in heap (priority order, based on P, E, T):
dispatchNotification(500):
900 > 500 is true. C is active. Dispatch C.dispatchNotification(500):
900 > 500 is true. B is active. Dispatch B.dispatchNotification(500):
1000 > 500 is true. A is active. Dispatch A.Constraints
id length: 1 <= id.length <= 50priority: 1 <= priority <= 100timestamp, expirationTime, currentTime: 0 <= time <= 10^12 (Large enough for Unix epoch milliseconds)expirationTime >= timestamp for all added notifications.addNotification calls (N): 1 <= N <= 10^5dispatchNotification calls (M): 1 <= M <= 10^5N + M operations within typical time limits (e.g., a few seconds for 10^5 operations).O(log N) or O(N log N) amortized complexity for operations where N is the number of active notifications.Loading editor...