1656. Design an Ordered Stream
Model: qwen2.5-coder:14b
Topics: Array,Design
FAANG asked: 0
Acceptance rate: 82.1%
Problem Breakdown
The problem requires designing an OrderedStream class that manages a stream of (idKey, value) pairs and returns values in increasing order of their IDs. The class should support the following operations:
- Constructor (
__init__): Initializes the stream with a capacityn. - Insert Method (
insert): Inserts a pair(idKey, value)into the stream and returns the largest possible chunk of consecutive values starting from the smallest unprocessed ID.
Inputs:
n: The number of elements in the stream.idKey: An integer representing the position in the stream.value: A string associated with theidKey.
Outputs:
- A list of strings that are the largest possible chunk of consecutive values starting from the smallest unprocessed ID.
Implicit Constraints:
- The
idKeyis between 1 andn. - No two pairs have the same
idKey. - Each call to
insertwill be unique. - Exactly
ncalls will be made toinsert.
Intuition
A brute-force approach would involve maintaining an array of size n and iterating through it each time to find the largest chunk of consecutive values. This approach is inefficient because it requires scanning the entire array on every insertion, leading to a time complexity of O(n) per insertion.
The key insight is to use a pointer that keeps track of the smallest unprocessed ID. When inserting a new value, we check if it matches the current pointer. If it does, we move the pointer forward and collect all consecutive values starting from this point. This approach ensures that each insertion operation is efficient, with an amortized time complexity of O(1).
Approach
- Data Structure: Use an array to store the stream values and a pointer (
self.ptr) to keep track of the smallest unprocessed ID. - Initialization: Initialize the array with
Nonevalues and set the pointer to 0. - Insert Method:
- Insert the value at the position corresponding to
idKey. - If the current pointer matches the
idKey, collect all consecutive non-Nonevalues starting from this point. - Move the pointer forward until a
Nonevalue is encountered.
- Insert the value at the position corresponding to
Complexity Analysis
- Time Complexity: O(1) for each insertion operation on average. Although we might iterate through consecutive values, the total number of iterations across all insertions will be linear in terms of
n. - Space Complexity: O(n) for storing the stream values.
Solution
class OrderedStream:
def __init__(self, n: int):
self.stream = [None] * n # Initialize the stream with None values
self.ptr = 0 # Pointer to track the smallest unprocessed ID
def insert(self, idKey: int, value: str) -> List[str]:
self.stream[idKey - 1] = value # Insert the value at the correct position
start = self.ptr
# Collect all consecutive non-None values starting from the pointer
while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
self.ptr += 1
return self.stream[start:self.ptr]
Edge Cases Handled
- Initial Insertion: If the first insertion is at
idKey = 1, it will immediately return a chunk containing this value. - Non-Consecutive Inserts: If inserts are made out of order, the method will only return consecutive values starting from the smallest unprocessed ID.
- Full Stream Insertion: When all elements are inserted in order, each insertion will return the next consecutive chunk until the end of the stream.