#1656

Design an Ordered Stream

newbie · 220 · lc easy +17 · 82.6% accepted · 572 likes · top 94%

Description

Design an OrderedStream for n (idKey, value) pairs that may arrive out of order. Implement:

- OrderedStream(int n) initializes the stream.

- String[] insert(int idKey, String value) inserts the pair and returns the largest consecutive run of values starting at the current internal pointer position.

Example 1:

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"]]

Example 2:

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.

Code

class OrderedStream:

    def __init__(self, n: int):
        

    def insert(self, idKey: int, value: str) -> List[str]:
        


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

class OrderedStream:

    def __init__(self, n: int):
        

    def insert(self, idKey: int, value: str) -> List[str]:
        


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)