Design an Ordered Stream
Bloomberg LP● EasyNEW GRADOAPHONE SCREENONSITE INTERVIEWProblem statement
An ordered stream expects exactly n unique pairs whose IDs are the integers from 1 through n. The pairs arrive in arbitrary order.
The arrays ids and values describe the insert calls in time order: call i inserts (ids[i], values[i]). After each insertion, return the largest contiguous chunk of values beginning at the smallest ID that has not been returned yet. Return an empty chunk when that next ID is still missing.
Return one chunk for every insertion. Concatenating all returned chunks must produce the values in increasing ID order.
Function
orderedStreamChunks(n: int, ids: int[], values: String[]) → String[][]Examples
Example 1
n = 5ids = [3,1,2,5,4]values = ["ccccc","aaaaa","bbbbb","eeeee","ddddd"]return = [[],["aaaaa"],["bbbbb","ccccc"],[],["ddddd","eeeee"]]ID 3 arrives before IDs 1 and 2, so it waits. Inserting ID 1 emits one value; inserting ID 2 then emits both IDs 2 and 3. The same behavior later joins IDs 4 and 5.
Example 2
n = 1ids = [1]values = ["only"]return = [["only"]]The first and only expected ID arrives immediately.
Example 3
n = 4ids = [2,4,1,3]values = ["b","d","a","c"]return = [[],[],["a","b"],["c","d"]]The stream waits for ID 1, then emits IDs 1 and 2. The final insert fills ID 3 and releases the already stored ID 4.
Constraints
1 <= n <= 1000.ids.length == values.length == n.idsis a permutation of the integers from1throughn.1 <= values[i].length <= 100.- Each value contains lowercase English letters.