Frontend School

Prioritized Notification Dispatcher

DSA
hard

Prioritized Notification Dispatcher

Hard
Heap
Priority Queue
Design

Overview

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.

What you need to do / Task

Implement the NotificationDispatcher class with the following methods:

  1. constructor(): Initializes the notification dispatcher.

  2. 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.

  3. 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:

    • Higher priority comes first.
    • Among notifications with the same highest priority, the one with the earliest expirationTime comes first.
    • Among notifications with the same priority and expirationTime, the one with the earliest timestamp comes first.

    If no active notifications are available, return null.

Input & output

Class Name: NotificationDispatcher

constructor():

  • No parameters.
  • Initializes the internal data structures.
  • Returns 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.
  • Returns 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.
  • Returns string | null - The id of the most urgent active notification, or null if none exist.

Clarifications

  • Uniqueness: All ids provided to addNotification will be unique.
  • Time Units: timestamp, expirationTime, and currentTime are all in the same arbitrary time unit (e.g., milliseconds since epoch).
  • Empty System: If dispatchNotification is called when no active notifications are present, it should return null.

Examples

1

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:

  1. NotificationDispatcher(): Initializes the system.
  2. addNotification("N1", 5, 1000, 5000): Adds N1.
  3. 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.
  4. dispatchNotification(2000):
    • Peek N1 (P:5, E:5000, T:1000). 5000 > 2000 is true. N1 is active. Dispatch N1.
    • Returns "N1". Remaining active: N2 (P:3, E:6000, T:1100).
  5. 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.
  6. dispatchNotification(3000):
    • Peek N3 (P:10, E:3000, T:2500). 3000 > 3000 is false. N3 is expired. Remove N3 from heap.
    • Peek N2 (P:3, E:6000, T:1100). 6000 > 3000 is true. N2 is active. Dispatch N2.
    • Returns "N2". Remaining active: None.
  7. dispatchNotification(5500): Heap is empty. Returns null.
  8. dispatchNotification(6000): Heap is empty. Returns null.
2

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:

  1. NotificationDispatcher(): Initializes the system.
  2. addNotification("A", 5, 100, 1000): Adds A.
  3. addNotification("B", 5, 120, 900): Adds B.
  4. addNotification("C", 5, 110, 900): Adds C. Notifications in heap (priority order, based on P, E, T):
    • C (P:5, E:900, T:110) - most urgent: P=5 (highest), E=900 (earliest among P=5, E=900), T=110 (earliest among P=5, E=900, T=...)
    • B (P:5, E:900, T:120) - next: P=5, E=900, T=120
    • A (P:5, E:1000, T:100) - last: P=5, E=1000
  5. dispatchNotification(500):
    • Peek C (P:5, E:900, T:110). 900 > 500 is true. C is active. Dispatch C.
    • Returns "C".
  6. dispatchNotification(500):
    • Peek B (P:5, E:900, T:120). 900 > 500 is true. B is active. Dispatch B.
    • Returns "B".
  7. dispatchNotification(500):
    • Peek A (P:5, E:1000, T:100). 1000 > 500 is true. A is active. Dispatch A.
    • Returns "A".

Constraints

Constraints & assumptions

  • id length: 1 <= id.length <= 50
  • priority: 1 <= priority <= 100
  • timestamp, expirationTime, currentTime: 0 <= time <= 10^12 (Large enough for Unix epoch milliseconds)
  • expirationTime >= timestamp for all added notifications.
  • Total number of addNotification calls (N): 1 <= N <= 10^5
  • Total number of dispatchNotification calls (M): 1 <= M <= 10^5
  • The system should be efficient enough to handle N + M operations within typical time limits (e.g., a few seconds for 10^5 operations).

Out of scope

  • Handling notification updates or cancellations (e.g., changing a notification's priority or removing it by ID).
  • Persistence of notifications across system restarts.
  • Distributed system considerations or concurrent access.

What interviewers evaluate

  • Correctness: The solution must correctly implement the priority and expiration logic for all edge cases.
  • Efficiency: Optimal use of data structures (e.g., priority queue) to achieve O(log N) or O(N log N) amortized complexity for operations where N is the number of active notifications.
  • Clarity & Readability: Clean, well-structured code with appropriate comments where necessary.
  • Problem Decomposition: Ability to break down the problem into core components and select the right tools.

Loading editor...