Stream Pattern Detection Function | Dataford Interview Questions

Nuna's healthcare data pipelines process event tokens as a stream. Given an iterable of string tokens and a non-empty pattern, return the zero-based starting index of every occurrence of the pattern in the stream, including overlapping matches.

Your function must process the stream in one pass and must not convert the entire iterable to a list. This requirement matters because the stream may be much larger than available memory.

Formal Specification

Implement find_pattern(events, pattern).

events is an iterable of strings. It may be a list, generator, or other single-pass iterator.
pattern is a non-empty list of strings.
Return a list of integer indices where pattern begins in events.
Matches may overlap, and the returned indices must be in ascending order.

Constraints

1 <= len(pattern) <= 10^5
The stream contains at most 10^7 tokens, but may be a generator
Each token is a string of length at most 100
The pattern is non-empty
Matches may overlap

Function Signature

def find_pattern(events, pattern):

Your question is Stream Pattern Detection Function. 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