Taro Logo

Find Consecutive Integers from a Data Stream

Medium
Intel logo
Intel
2 views
Topics:
ArraysTwo PointersSliding Windows

For a stream of integers, implement a data structure that checks if the last k integers parsed in the stream are equal to value.

Implement the DataStream class:

  • DataStream(int value, int k) Initializes the object with an empty integer stream and the two integers value and k.
  • boolean consec(int num) Adds num to the stream of integers. Returns true if the last k integers are equal to value, and false otherwise. If there are less than k integers, the condition does not hold true, so returns false.

Example 1:

Input
["DataStream", "consec", "consec", "consec", "consec"]
[[4, 3], [4], [4], [4], [3]]
Output
[null, false, false, true, false]

Explanation
DataStream dataStream = new DataStream(4, 3); //value = 4, k = 3 
dataStream.consec(4); // Only 1 integer is parsed, so returns False. 
dataStream.consec(4); // Only 2 integers are parsed.
                      // Since 2 is less than k, returns False. 
dataStream.consec(4); // The 3 integers parsed are all equal to value, so returns True. 
dataStream.consec(3); // The last k integers parsed in the stream are [4,4,3].
                      // Since 3 is not equal to value, it returns False.

Constraints:

  • 1 <= value, num <= 109
  • 1 <= k <= 105
  • At most 105 calls will be made to consec.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on the values of k and value, and the range of integers in the stream?
  2. What should happen if k is larger than the number of elements received so far in the stream?
  3. Can k be zero or negative? If so, what should the function return?
  4. How frequently will the stream receive new integers, and what is the expected number of queries to check for k consecutive values?
  5. Is the stream persistent, or do I need to handle memory management as old values fall outside the last k integers?

Brute Force Solution

Approach

The brute force approach to this problem is all about checking every single possibility. We essentially keep track of a fixed number of recent numbers from the stream. For each new number added, we go back and check if any consecutive sequence within those recent numbers sums up to our target value.

Here's how the algorithm would work step-by-step:

  1. First, keep a record of the most recent numbers we've seen, up to a maximum amount that we care about.
  2. When a new number comes in, add it to our record of recent numbers.
  3. Now, starting from the beginning of our recorded recent numbers, check if that first number matches the required number that we're looking for.
  4. Then, check if the first two numbers, taken together and in order, match the required number.
  5. Next, check the first three numbers and so on, continuing to add the next number and adding the total to see if we have a match.
  6. Do this for every possible sequence from the start to the end of our list.
  7. Then, we do this starting from the second element, third element, all the way until the end of the list.
  8. If any of these sums matches what we're looking for, then we know that the stream has had those consecutive numbers.

Code Implementation

class ConsecutiveIntegers:
    def __init__(self, required_number):
        self.required_number = required_number
        self.recent_numbers = []

    def add_number(self, number):
        self.recent_numbers.append(number)

    def check(self):
        number_of_recent_numbers = len(self.recent_numbers)

        # Iterate through possible start indices
        for start_index in range(number_of_recent_numbers):

            current_sum = 0

            # Iterate through possible sequence lengths
            for sequence_length in range(start_index, number_of_recent_numbers):

                current_sum += self.recent_numbers[sequence_length]

                # Check if the current sum equals the required number
                if current_sum == self.required_number:
                    return True

        # No consecutive integers found
        return False

Big(O) Analysis

Time Complexity
O(k²)The described brute force approach maintains a record of the k most recent numbers. When a new number arrives, the algorithm iterates through all possible consecutive subsequences within these k recent numbers. The outer loop starts from each index (0 to k-1), and the inner loop extends the subsequence from that starting index to the end of the k recent numbers. Therefore, in the worst case, the algorithm performs approximately k * (k+1) / 2 operations which simplifies to O(k²), where k is the maximum number of recent elements being stored.
Space Complexity
O(N)The provided solution stores up to N recent numbers from the data stream. This is explicitly mentioned in step 1: 'keep a record of the most recent numbers we've seen, up to a maximum amount that we care about'. This record of recent numbers is an auxiliary data structure that grows linearly with the maximum number of recent elements tracked. Therefore, the space complexity is O(N), where N is the maximum number of recent elements stored.

Optimal Solution

Approach

The goal is to efficiently check if a stream of numbers contains a specific sequence of consecutive integers. Instead of storing the entire stream, we'll keep track of only the numbers we need to form the sequence.

Here's how the algorithm would work step-by-step:

  1. First, remember the length of the sequence of consecutive integers that we are looking for.
  2. As numbers arrive in the stream, store only the ones that fall within the range that could form our sequence, based on the value of the last number in the sequence.
  3. When enough numbers have arrived such that the data structure is full, check if these stored numbers form the desired sequence.
  4. If the sequence is present, return true. Otherwise return false.
  5. When new numbers arrive in the stream, remove the oldest number from the data structure and add the new number.
  6. Continue checking as new numbers arrive.

Code Implementation

class ConsecutiveIntegers:

    def __init__(self, sequence_length: int):
        self.sequence_length = sequence_length
        self.numbers_received = []

    def insert(self, number: int) -> bool:
        if len(self.numbers_received) < self.sequence_length:
            self.numbers_received.append(number)
        else:
            self.numbers_received.pop(0)
            self.numbers_received.append(number)

        # Ensure we have enough numbers to check for consecutiveness.
        if len(self.numbers_received) == self.sequence_length:
            sorted_numbers = sorted(self.numbers_received)

            # After sorting, check for consecutiveness.
            for i in range(1, self.sequence_length):
                if sorted_numbers[i] != sorted_numbers[i - 1] + 1:
                    return False

            return True
        else:
            return False

Big(O) Analysis

Time Complexity
O(k)The addNum operation involves checking if the new number falls within the expected range, which is O(1). Storing the number in the data structure takes O(1) time. When the data structure is full, checking if the stored numbers form the consecutive sequence involves iterating through at most k numbers, where k is the sequence length. Removing the oldest number is O(1) if a suitable data structure like a queue is used. Therefore, the overall time complexity for each addNum operation is dominated by the sequence check, which is O(k).
Space Complexity
O(K)The primary auxiliary space usage stems from storing the numbers that could form the consecutive sequence. According to the description, we store only the numbers within the range necessary to potentially form the sequence of length K. Therefore, the space required is proportional to the length of the consecutive sequence we're looking for, which is K. This results in a space complexity of O(K) because the extra space scales linearly with the length of the sequence.

Edge Cases

CaseHow to Handle
k is zeroReturn true if k is zero, as zero consecutive elements are trivially equal.
k is negativeThrow an IllegalArgumentException as k should be a non-negative integer.
The stream is empty at the beginning (no numbers added)Maintain an internal count of elements and return false if less than k elements have been added.
k is larger than the number of elements currently in the streamReturn false since there are not k consecutive elements to check.
value is nullHandle null value appropriately, possibly checking for null before comparisons or throwing a NullPointerException, depending on the language and desired behavior.
Large stream with many elements and frequent calls to checkOptimize for space and time efficiency by using a data structure like a queue/deque to maintain the last k elements and avoid recalculating the last k elements every time.
Integer overflow when storing the stream or checking for equality (if value is very large)Use appropriate data types (e.g., long) or consider using a BigInteger class if necessary to handle potentially large values and prevent overflow.
The value changes in the middle of the K elementsOur solution checks only the last k elements, and should naturally produce correct result.