PracticeData Structures

Beacon Desk: Keep the Strongest Alerts

MediumData Structurestraversalinvariantscomparison Time not estimated Not started

Context

A monitoring desk receives short alert messages from many text-based system logs. Each message has a numeric severity score supplied by the logging service. The desk wants to keep only the most severe alerts while processing the feed once, rather than fully sorting every message.

Problem

Implement a function that selects up to k alert messages with the greatest severity scores. The messages array and scores array are aligned: the score at an index belongs to the message at that index. A larger score ranks higher. If scores tie, the message appearing earlier in the input ranks higher. Return the selected messages in their original input order, not in score order. If k is zero or the input has no messages, return an empty list. If k is greater than the number of messages, return every message. Use a bounded min-heap so that the retained selection never contains more than k candidates while scanning the aligned records.

Examples

Example 1
Input: k = 2messages = ["disk nearly full", "login failure", "backup delayed", "api timeout"]severity_scores = [70, 95, 95, 40]
Output: ["login failure", "backup delayed"]
Explanation: Example 1 returns the two messages with score 95, with the earlier input message listed first because the scores tie.
Example 2
Input: k = 6messages = ["CPU warning", "User logout!", "Cache miss", "Service recovered"]severity_scores = [88, 12, 64, 99]
Output: ["CPU warning", "User logout!", "Cache miss", "Service recovered"]
Explanation: Example 2 returns every message because k is greater than the four-message input length.
Example 3
Input: k = 0messages = ["notice: update complete", "minor latency"]severity_scores = [20, 20]
Output: []
Explanation: Example 3 returns an empty list because k is zero.

Constraints

  • 0 <= len(messages) <= 100000
  • 1 <= len(messages[i]) <= 240 for every i
  • len(messages) <= len(severity_scores) <= len(messages)
  • -1000000000000 <= severity_scores[i] <= 1000000000000 for every i
  • 0 <= k <= len(messages) + 100
  • Each score corresponds to the message at the same index.
  • Messages are nonempty text strings
  • their contents may include spaces, punctuation, and mixed characters.
  • Types: messages is str[], severity_scores is int[], k is int; result is str[]

Function signature

def select_strongest_alerts(messages: list[str], severity_scores: list[int], k: int) -> list[str]
messages list[str]
Text alert records, aligned with the severity scores.
severity_scores list[int]
Numeric severity for each message at the same index.
k int
Maximum number of alerts to retain; may exceed the number of messages.
returns list[str]
The highest-ranked messages, preserving input order. Ties are resolved in favor of the earlier input position.

Adapted from MBPP problem task_585 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Notes

  • The returned order is chronological input order rather than descending severity.
  • A tied score is ranked by smaller original index.
Approved · x001-abs_449_v114 execution-verified tests
Code
Saved
Checking environment…Python SandboxLn 1, Col 1