Katkat
Back

Write a generator for substring pattern matches

AppleMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of string pattern matching and generator/iterator design, testing skills in handling overlapping matches, streaming output, and worst-case time complexity considerations.

Problem

Write a generator that scans a string and emits a value whenever a substring matches a given pattern.

Input

  • A string s
  • A string pattern (non-empty)

Output

Return a generator/iterator that yields True once for each occurrence of pattern in s, scanning from left to right. Matches may overlap.

Examples

  • s = "aaaa", pattern = "aa" → yields True 3 times (matches at indices 0, 1, 2)
  • s = "abc", pattern = "d" → yields nothing

Constraints

  • 0 <= len(s) <= 10^6
  • 1 <= len(pattern) <= 10^5

Notes

  • The solution should avoid quadratic time in the worst case.