{x}
blog image

Design an Ordered Stream

There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.

Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.

Implement the OrderedStream class:

  • OrderedStream(int n) Constructs the stream to take n values.
  • String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.

 

Example:

Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]

Explanation
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"].
OrderedStream os = new OrderedStream(5);
os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns [].
os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"].
os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"].
os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns [].
os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"].
// Concatentating all the chunks returned:
// [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]
// The resulting order is the same as the order above.

 

Constraints:

  • 1 <= n <= 1000
  • 1 <= id <= n
  • value.length == 5
  • value consists only of lowercase letters.
  • Each call to insert will have a unique id.
  • Exactly n calls will be made to insert.

Solution Explanation:

This problem involves designing an OrderedStream class that efficiently inserts (id, value) pairs and returns chunks of values in increasing order of their IDs. The solution uses an array to store the values, indexed by their IDs. A pointer tracks the next expected ID.

Approach:

  1. Constructor: The constructor initializes an array (data or vals) of size n (the maximum ID) to store the values. It also initializes a pointer (ptr) to 0, representing the index of the next expected ID. Elements are initialized to null or an empty string, indicating that no value has been inserted yet for that ID.

  2. Insert Function: The insert function takes an idKey and a value as input.

    • It first inserts the value into the data array at the index idKey - 1 (since IDs are 1-based).
    • It then creates an empty list or vector (ans) to store the chunk of values to be returned.
    • It enters a while loop that continues as long as the pointer ptr is within the bounds of the array and the element at data[ptr] is not null (or empty string). This condition ensures that there's a value at the expected next ID.
    • Inside the loop, it appends the value at data[ptr] to the ans list and increments the pointer ptr.
    • Finally, it returns the ans list, which contains the chunk of consecutively inserted values.

Time and Space Complexity:

  • Time Complexity:

    • The insert function has a time complexity of O(n) in the worst case, where n is the number of elements in the array. This worst-case scenario occurs when all the elements from ptr to the end of the array have been inserted. However, in most cases, the time complexity is closer to O(k), where k is the length of the chunk returned. This is because the while loop will only iterate through the already inserted elements.
    • The Constructor has O(n) time complexity because it initializes an array of size n.

  • Space Complexity:

    • The space complexity is O(n) because an array of size n is used to store the values. This space is used regardless of the number of insertions; it's determined by the input n.

Code Examples (with minor stylistic improvements):

The provided code examples in Python, Java, C++, Go, TypeScript, and Rust are all functionally correct and implement the described approach. They differ slightly in syntax and style, but the core logic remains the same. For clarity and conciseness, I won't repeat them here. Refer to the original response for the complete code snippets in each language.