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
105
calls will be made to consec
.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:
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:
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
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:
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
Case | How to Handle |
---|---|
k is zero | Return true if k is zero, as zero consecutive elements are trivially equal. |
k is negative | Throw 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 stream | Return false since there are not k consecutive elements to check. |
value is null | Handle 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 check | Optimize 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 elements | Our solution checks only the last k elements, and should naturally produce correct result. |