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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design an Ordered Stream

Number: 1775

Difficulty: Easy

Paid? No

Companies: Bloomberg

Problem Description

Design a stream that receives n (idKey, value) pairs in an arbitrary order and returns the values in increasing order of their IDs. After each insertion, the stream should output the largest possible chunk of consecutive values starting from the smallest unseen id.

Key Insights

  • Maintain a data structure (like an array) of size n+1 to store the values by their id.
  • Use a pointer to track the first missing id in the stream.
  • On each insertion, update the stream and return a chunk by iterating from the pointer until a missing value is encountered.
  • The overall concatenation of returned chunks forms the ordered list.

Space and Time Complexity

Time Complexity: O(n) overall for n insertions in the worst-case scenario where each insertion does constant work on average, but a single call might do O(n) in case of a long consecutive chunk. Space Complexity: O(n) for storing the stream values.

Solution

The solution uses an array (or list) to store the values at the indices corresponding to the given idKey's. A pointer (or index variable) is maintained to track the next expected id. When inserting a value, the value is placed at the correct index, and then a while loop collects all consecutive values starting from the pointer. This chunk is returned and the pointer is updated to the new position for subsequent insertions. This strategy ensures that the returned chunks are always the largest possible consecutive segments.

Code Solutions

# Python implementation
class OrderedStream:
    def __init__(self, n: int):
        # Initialize a list with n+1 elements (1-indexed) and a pointer to track the next id
        self.stream = [None] * (n + 1)
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> [str]:
        # Insert the value at the correct position
        self.stream[idKey] = value
        result = []
        # Append items from the current pointer while they are available
        while self.ptr < len(self.stream) and self.stream[self.ptr]:
            result.append(self.stream[self.ptr])
            self.ptr += 1
        return result

# Example usage:
# os = OrderedStream(5)
# print(os.insert(3, "ccccc"))  # Output: []
# print(os.insert(1, "aaaaa"))  # Output: ["aaaaa"]
# print(os.insert(2, "bbbbb"))  # Output: ["bbbbb", "ccccc"]
# print(os.insert(5, "eeeee"))  # Output: []
# print(os.insert(4, "ddddd"))  # Output: ["ddddd", "eeeee"]
← Back to All Questions