Frontend School

Dynamic Critical Alert System

DSA
hard

Dynamic Critical Alert System

Hard
Heap
Priority Queue
Hash Map
Data Structure Design

Overview

In a fast-paced environment, real-time decision-making often hinges on prioritizing critical information. Imagine a system designed to manage and display the most urgent alerts from a continuous stream. These alerts have varying priorities and impact scores, which can dynamically change. Your task is to design and implement a CriticalAlertSystem that efficiently tracks and retrieves the top K most critical alerts at any given moment, even as new alerts arrive, existing alerts' impact changes, or alerts are dismissed.

What you need to do / Task

Implement the CriticalAlertSystem class with the following methods:

  1. constructor(k: number): Initializes the system to track up to k most critical alerts.
  2. addAlert(alertId: string, priority: number, impactScore: number): Adds a new alert to the system. The alert's criticality is defined as priority + impactScore. If an alert with the given alertId already exists, this operation should fail.
  3. updateImpact(alertId: string, newImpactScore: number): Updates the impactScore of an existing alert. The alert's priority remains unchanged. This will recalculate its criticality.
  4. dismissAlert(alertId: string): Removes an existing alert from the system.
  5. getTopKAlerts(): Returns a list of alertIds representing the k most critical active alerts currently in the system. The alerts should be ordered by criticality in descending order. If two alerts have the same criticality, they should be ordered by alertId in ascending alphabetical order. If fewer than k active alerts exist, return all of them.

Input & output

Class: CriticalAlertSystem

constructor(k: number)

  • k: number - The maximum number of top critical alerts to track. (k >= 1)
  • Returns: void (implicitly null in test cases).

addAlert(alertId: string, priority: number, impactScore: number)

  • alertId: string - A unique identifier for the alert.
  • priority: number - The base priority of the alert (non-negative integer).
  • impactScore: number - The initial impact score of the alert (non-negative integer).
  • Returns: boolean - true if the alert was successfully added, false if an alert with alertId already exists.

updateImpact(alertId: string, newImpactScore: number)

  • alertId: string - The identifier of the alert to update.
  • newImpactScore: number - The new impact score for the alert (non-negative integer).
  • Returns: boolean - true if the alert's impact was successfully updated, false if alertId does not exist or has been dismissed.

dismissAlert(alertId: string)

  • alertId: string - The identifier of the alert to dismiss.
  • Returns: boolean - true if the alert was successfully dismissed, false if alertId does not exist or has already been dismissed.

getTopKAlerts()

  • Returns: string[] - A list of alertIds of the top k most critical alerts, sorted as specified in the task description.

Clarifications

  • Criticality Calculation: An alert's criticality is priority + impactScore.
  • Tie-breaking for getTopKAlerts: When two alerts have the same criticality, the one with the lexicographically smaller alertId should come first.
  • Fewer than K alerts: If the system has fewer than k active alerts, getTopKAlerts should return all currently active alerts, sorted by criticality and alertId as specified.
  • Non-existent alertId: If updateImpact or dismissAlert is called with an alertId that does not exist or has already been dismissed, it should return false.
  • addAlert with existing alertId: If addAlert is called with an alertId that already exists (and is active), it should return false.

Examples

1

Example 1

Input:

operations = ["CriticalAlertSystem","addAlert","addAlert","addAlert","getTopKAlerts","updateImpact","getTopKAlerts","dismissAlert","getTopKAlerts"] params = [[2],["A1",10,5],["A2",8,8],["A3",12,1],[],["A1",10],[],["A2"],[]]

Output:

[null,true,true,true,["A2","A1"],true,["A1","A3"],true,["A1","A3"]]

Note:

  1. Init system with K=2.
  2. Add A1 (priority 10, impact 5) -> criticality 15. System: {A1:15}
  3. Add A2 (priority 8, impact 8) -> criticality 16. System: {A1:15, A2:16}
  4. Add A3 (priority 12, impact 1) -> criticality 13. A3 is less critical than A1 and A2, so it's not in top 2. System: {A1:15, A2:16}
  5. getTopKAlerts() -> A2 (16), A1 (15). Output: ["A2", "A1"]
  6. updateImpact A1, new impact 10 -> A1 criticality becomes 10+10=20. System: {A1:20, A2:16, A3:13}. Top 2 are now A1 (20) and A2 (16).
  7. getTopKAlerts() -> A1 (20), A2 (16). Output: ["A1", "A2"]
  8. dismissAlert A2. System: {A1:20, A3:13}. Top 2 are now A1 (20) and A3 (13).
  9. getTopKAlerts() -> A1 (20), A3 (13). Output: ["A1", "A3"]
2

Example 2

Input:

operations = ["CriticalAlertSystem","addAlert","addAlert","addAlert","dismissAlert","addAlert","getTopKAlerts"] params = [[1],["X1",5,5],["X2",10,10],["X3",15,15],["X2"],["X4",20,20],[]]

Output:

[null,true,true,true,true,true,["X4"]]

Note:

  1. Init system with K=1.
  2. Add X1 (crit 10). Top 1: {X1:10}
  3. Add X2 (crit 20). X2 replaces X1. Top 1: {X2:20}
  4. Add X3 (crit 30). X3 replaces X2. Top 1: {X3:30}
  5. dismissAlert X2. This alert is not in top 1, so no change to top 1. Top 1: {X3:30}
  6. Add X4 (crit 40). X4 replaces X3. Top 1: {X4:40}
  7. getTopKAlerts() -> X4 (40). Output: ["X4"]
3

Example 3

Input:

operations = ["CriticalAlertSystem","addAlert","updateImpact","addAlert","getTopKAlerts","dismissAlert","getTopKAlerts","updateImpact"] params = [[3],["AlertA",10,10],["AlertA",5],["AlertB",20,20],[],["AlertA"],[],["AlertC",10]]

Output:

[null,true,true,true,["AlertB","AlertA"],true,["AlertB"],false]

Note:

  1. Init system with K=3.
  2. Add AlertA (crit 20). Top 3: {AlertA:20}
  3. updateImpact AlertA to 5 -> AlertA crit 10+5=15. Top 3: {AlertA:15}
  4. Add AlertB (crit 40). Top 3: {AlertB:40, AlertA:15}
  5. getTopKAlerts() -> AlertB (40), AlertA (15). Output: ["AlertB", "AlertA"]
  6. dismissAlert AlertA. Top 3: {AlertB:40}
  7. getTopKAlerts() -> AlertB (40). Output: ["AlertB"]
  8. updateImpact AlertC (non-existent). Returns false.

Constraints

Constraints & assumptions

  • 1 <= k <= 10^4
  • 0 <= priority, impactScore, newImpactScore <= 10^9
  • alertId consists of alphanumeric characters.
  • The total number of addAlert, updateImpact, dismissAlert, and getTopKAlerts operations will not exceed 10^5.
  • The sum of priority and impactScore will not exceed 2 * 10^9.
  • You should aim for O(log K) amortized time complexity for addAlert, updateImpact, and dismissAlert operations. getTopKAlerts should ideally be O(K log K) in the worst case.

What interviewers evaluate

  • Correctness and Robustness: The solution correctly handles all operations and edge cases, including dynamic updates and dismissals.
  • Efficiency: Optimal use of data structures (Heaps, Hash Maps) to achieve the specified time complexities.
  • Data Structure Design: Effective implementation of a custom data structure to manage dynamic priorities and removals.
  • Code Quality: Clean, well-structured, readable code with appropriate comments.

Loading editor...