Find Pattern in Infinite Stream II

Find Pattern in Infinite Stream II

What is this problem about?

The Find Pattern in Infinite Stream II interview question is the "Hard" version of the stream matching task. The pattern can be much longer ($10^5$ bits), making a simple integer-based rolling hash insufficient due to bit-depth limits. You need a robust string-matching algorithm that can process bits one by one as they arrive from an infinite source.

Why is this asked in interviews?

Uber uses this to evaluate a candidate's knowledge of advanced string matching algorithms like KMP (Knuth-Morris-Pratt). KMP is uniquely suited for streams because it uses a "failure function" (partial match table) to determine the next state based only on the current character and the current state, without ever needing to "look back" at previous bits. It tests high-level String Matching interview patterns.

Algorithmic pattern used

This problem is solved using the KMP Algorithm (State Machine).

1. Preprocessing: Build the LPS (Longest Proper Prefix which is also a Suffix) array for the target pattern.
2. Stream Processing:
   • Maintain a patternPointer initialized to 0.
   • For each bit from stream.next():
     • If the bit matches pattern[patternPointer], increment the pointer.
     • If it doesn't, use the LPS array to "jump" the pointer back to the next best possible prefix match.
     • If patternPointer reaches the end of the pattern, return the current stream index.

Example explanation

Pattern: 1011

1. Bits: 1, 0, 1. pointer is at 3.
2. Next bit: 0. pattern[3] is 1. Mismatch!
3. LPS logic: The suffix "101" has a prefix "1". Jump pointer to index 1 (after the first '1') and check the new bit '0' against pattern[1].
4. pattern[1] is 0. Match! pointer moves to 2. This avoids re-reading the stream and keeps the processing $O(1)$ per bit.

Common mistakes candidates make

• Rolling Hash limitations: Trying to use Rabin-Karp without a large prime or double-hashing, leading to collisions on long patterns.
• LPS Construction: Errors in the logic for building the KMP table ($O(M)$).
• Interactive Logic: Forgetting that you can only call next() once per bit; you cannot "rewind" the stream.

Interview preparation tip

KMP is one of the most feared string algorithms. If you can explain how the "Partial Match Table" allows the search to continue without backtracking, you show a deep understanding of state machines and algorithm efficiency. This is a top-tier String interview pattern.