Design an Ordered Stream Lab

Easy
1
25.0% Acceptance

In this lab, you'll design an ordered stream capable of receiving 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 will have the same idKey. The stream should return 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 sorted values.

You need to implement the OrderedStream class with the following methods:

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

Examples:

const 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.

Once you have implemented the OrderedStream class and its methods, you will be required to complete a set of challenges to test your solution. Don't forget to export the OrderedStream class from your solution file.

Note: This lab uses ESM import/export. Make sure to use ESM syntax for all imports and exports in your code.