Log Pattern Detection

HardPython

Problem

Rubrik CDM operators need to identify recurring failures in cluster logs. Given log entries, return every error pattern that occurs at least threshold times within any inclusive time window of window seconds for the same component.

Each log entry is a string in the format timestamp|component|level|message. Only entries whose level is ERROR count. Normalize an error message by replacing every contiguous decimal number with <num>, so messages such as Snapshot failed for volume 17 and Snapshot failed for volume 18 belong to the same pattern.

Return a lexicographically sorted list of two-element lists: [component, normalized_message]. Return an empty list if no pattern qualifies.

Formal Specification

Input: logs, a list of valid strings, plus non-negative integer window and integer threshold.
Output: A list of [component, normalized_message] lists with no duplicates.
Timestamps may be unsorted. The time interval is inclusive, so entries at times t and t + window belong to the same window.

Constraints

1 <= len(logs) <= 100000
0 <= timestamp <= 10^9
0 <= window <= 10^9
2 <= threshold <= len(logs)
Each log entry is valid and contains exactly four pipe-delimited fields

Function Signature

def detect_error_patterns(logs, window, threshold):

Return a lexicographically sorted list of two-element lists: [component, normalized_message]. Return an empty list if no pattern qualifies.

Formal Specification

Input: logs, a list of valid strings, plus non-negative integer window and integer threshold.
Output: A list of [component, normalized_message] lists with no duplicates.
Timestamps may be unsorted. The time interval is inclusive, so entries at times t and t + window belong to the same window.