Find Pattern in Infinite Stream I

Find Pattern in Infinite Stream I

What is this problem about?

The Find Pattern in Infinite Stream I interview question is an interactive string matching problem. You are given a Stream object with a next() method that returns the next bit (0 or 1) in a sequence. You are also given a target binary pattern. Your goal is to find the index of the first bit in the stream where the pattern matches the most recently received bits.

Why is this asked in interviews?

Uber asks this to test your knowledge of Rolling Hashes and Sliding Windows. Since the stream is "infinite," you cannot store all the bits you've seen. You must maintain a "window" of the last $M$ bits (where $M$ is pattern length) and efficiently check for a match after every new bit. This evaluations your understanding of the Hash Function interview pattern.

Algorithmic pattern used

This problem uses Rabin-Karp (Rolling Hash) or a Deque/Queue.

1. Window Size: $M = pattern.length$.
2. Pre-calculate Pattern Hash: Calculate the numeric value or a modular hash of the target pattern.
3. Rolling Hash: As you call stream.next():
   • "Push" the new bit into your current window hash: (hash << 1) | newBit.
   • "Pop" the bit that fell out of the window: hash &= mask (where mask is $2^M - 1$).
4. Comparison: If the rolling hash equals the pattern hash, you've found the match.

Example explanation

Pattern: [1, 0, 1], Stream: 0, 1, 1, 0, 1, ...

1. Bits seen: 0, 1, 1. Hash: 3 (binary 011). No match.
2. Next bit: 0. New window: 1, 1, 0. Hash: 6 (binary 110). No match.
3. Next bit: 1. New window: 1, 0, 1. Hash: 5 (binary 101). MATCH! Return the index of the start of this window.

Common mistakes candidates make

• Storing History: Trying to save the entire stream in a list, which violates the "infinite" nature and memory constraints.
• Hash Collisions: If the pattern is long, a simple bit-shift might exceed integer limits. Using modular arithmetic (true Rabin-Karp) is safer.
• Off-by-one: Incorrectly calculating the starting index of the pattern relative to the number of next() calls.

Interview preparation tip

Master the Sliding Window bitmask trick: (current << 1 | next) & ((1 << windowSize) - 1). This is the most efficient way to maintain a rolling window of bits in $O(1)$ time per update.