Efficient Log Parsing Script | Dataford Interview Questions

Citadel's observability pipeline receives log data that may be too large to load into memory. Given an iterable of log lines and a collection of error patterns, count every occurrence of each pattern in one streaming pass.

Matches may overlap, and a pattern cannot span two log lines. For example, "AAAA" contains three occurrences of "AA". Return a dictionary containing every requested pattern, including patterns with zero matches.

Formal Specification

Implement count_error_patterns(lines, patterns).

lines is an iterable of strings. It may be a generator, so do not assume it can be indexed or reread.
patterns is a list of distinct, non-empty strings.
Return a dictionary mapping each pattern to its total number of occurrences across all lines.
Matching is case-sensitive and counts overlapping occurrences.

Use an algorithm that avoids scanning every pattern independently for every line.

Constraints

1 <= len(patterns) <= 10^4
The total number of characters in all patterns is at most 2 * 10^5
The total number of characters across all input lines is at most 10^7
Every pattern is non-empty and patterns are distinct
Input lines and patterns contain printable ASCII characters

Function Signature

def count_error_patterns(lines, patterns):

Your question is Efficient Log Parsing Script. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem