Stream Pattern Detection Function

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Stream Pattern Detection Function. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output