How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Apple during technical interviews.

Write a generator for substring pattern matches

Q: Write a generator for substring pattern matches

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.

Company: Apple

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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.

Quick Answer: 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.

Write a function that scans a string from left to right and returns a generator/iterator. The iterator must yield True exactly once for each occurrence of pattern in s. Matches may overlap. For example, in s = "aaaa" with pattern = "aa", the pattern occurs at indices 0, 1, and 2, so the iterator yields True three times. The implementation should avoid quadratic time in the worst case.

Constraints

0 <= len(s) <= 10^6
1 <= len(pattern) <= 10^5
Matches may overlap
The solution should run in O(len(s) + len(pattern)) time

Examples

Input: ("aaaa", "aa")

Expected Output: [True, True, True]

Explanation: The pattern "aa" occurs at starting indices 0, 1, and 2, including overlapping matches.

Input: ("abcdef", "gh")

Expected Output: []

Explanation: The pattern never appears in the string.

Input: ("abababa", "aba")

Expected Output: [True, True, True]

Explanation: The pattern "aba" occurs at starting indices 0, 2, and 4.

Input: ("short", "longpattern")

Expected Output: []

Explanation: A pattern longer than the text cannot match.

Input: ("", "a")

Expected Output: []

Explanation: An empty text contains no non-empty pattern occurrences.

Input: ("abc", "")

Expected Output: []

Explanation: By definition for this problem, an empty pattern produces no yielded values.

Hints

A naive check at every starting index can become quadratic when the string and pattern contain many repeated characters.
Consider preprocessing the pattern so that after a mismatch, you know how much of the current partial match can still be reused.

Quick Overview

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.