We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Pattern in Infinite Stream II

Number: 3352

Difficulty: Hard

Paid? Yes

Companies: Uber

Problem Description

Given a binary pattern array and an object representing an infinite stream of bits (with a next() function to fetch the next bit), determine the first starting index at which the bits from the stream match the pattern. The problem guarantees that the match will occur within the first 10^5 bits of the stream.

Key Insights

  • We cannot store the entire stream but only need to maintain a sliding window of the last pattern length bits.
  • Using a rolling hash (Rabin-Karp style) is ideal because the bit values are only 0 or 1. The window can be represented as an integer.
  • With a bitmask, we can efficiently update the window hash when a new bit is read.
  • Since the stream is infinite and the match is guaranteed early, the algorithm stops once the pattern is found.
  • No extra space is required (alphabet size is just 2), making the algorithm efficient in both time and space.

Space and Time Complexity

Time Complexity: O(n) where n is the number of bits read until the pattern is found (guaranteed to be <= 10^5). Space Complexity: O(1) since we only maintain a few integer variables (current hash and mask).

Solution

The approach uses a rolling hash. First, compute the integer value of the pattern as patternHash. Then, use a sliding window over the stream: shift the current window hash left by 1, mask it to maintain only the last pattern length bits, and add the new bit from the stream. When the window size equals the pattern length, compare its hash to patternHash. Return the starting index (which is the current index minus pattern length + 1) when a match is found.

Data Structures and Algorithms:

  • A sliding window (using a rolling integer variable) to keep track of the last pattern.length bits.
  • Bitmasking to ensure that only the relevant bits are considered.
  • Checking the equality of the hash to decide if the pattern is found. (Optionally, for collision safety, you could verify the actual bits, but with binary digits and proper masking, it is usually sufficient.)

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with detailed inline comments.

# Python implementation

class InfiniteStream:
    # Dummy implementation for context.
    def __init__(self, stream):
        self.stream = stream
        self.index = 0

    def next(self):
        bit = self.stream[self.index]
        self.index += 1
        return bit

def findPattern(stream, pattern):
    pattern_len = len(pattern)
    
    # Compute the integer representation of the pattern bits.
    pattern_hash = 0
    for bit in pattern:
        pattern_hash = (pattern_hash << 1) | bit

    # Create a mask to keep only pattern_len bits.
    mask = (1 << pattern_len) - 1
    current_window = 0
    
    index = 0
    while True:
        # Read next bit from the stream.
        bit = stream.next()
        # Update the rolling window: shift left by 1, add new bit,
        # and apply mask to discard bits beyond pattern_len.
        current_window = ((current_window << 1) | bit) & mask
        
        # Only start checking once we've filled the window.
        if index >= pattern_len - 1:
            if current_window == pattern_hash:
                # Return the starting index of the pattern match.
                return index - pattern_len + 1
        index += 1

# Example usage:
if __name__ == "__main__":
    # Example test: pattern = [1, 1, 0, 1] in stream = [1, 0, 1, 1, 0, 1, 1, 0, 1, ...]
    stream_data = [1, 0, 1, 1, 0, 1, 1, 0, 1]  # For demonstration
    stream = InfiniteStream(stream_data)
    pattern = [1, 1, 0, 1]
    print(findPattern(stream, pattern))  # Expected output: 2
← Back to All Questions