Design an Ordered Stream

Design an Ordered Stream

1. What is this problem about?

The Design an Ordered Stream interview question asks you to build a system that receives packets of data (ID and value) out of order but must output them in a specific sequence. You maintain a pointer starting at 1. Every time a new packet arrives, you store it. If the packet's ID matches the current pointer, you return that value along with any subsequent values that have already arrived and are now in order.

2. Why is this asked in interviews?

Companies like Meta and Google ask the Design an Ordered Stream coding problem to evaluate your understanding of Data Stream interview patterns. It mimics real-world scenarios like TCP packet reassembly or video streaming, where segments arrive sporadically but must be processed chronologically. It tests your ability to manage state and pointers within an array.

3. Algorithmic pattern used

This problem follows the Pointer and Array/Map Simulation pattern.

• Use an array (or Hash Map) of size $N+1$ to store values as they arrive.
• Maintain a ptr variable initialized to 1.
• In the insert method:
  1. Store the value at stream[id].
  2. If id == ptr, start a loop to collect all consecutive non-null values starting from ptr.
  3. Update ptr to the next missing ID and return the collected list.

4. Example explanation

Stream size: 5.

1. insert(3, "ccccc"): Pointer is at 1. stream[3] is now "ccccc". Return [].
2. insert(1, "aaaaa"): Pointer is at 1. id == ptr.
   • Collect stream[1] ("aaaaa").
   • Pointer moves to 2. stream[2] is empty. Stop.
   • Return ["aaaaa"].
3. insert(2, "bbbbb"): Pointer is at 2. id == ptr.
   • Collect stream[2] ("bbbbb").
   • Pointer moves to 3. stream[3] is "ccccc".
   • Collect "ccccc". Pointer moves to 4. stream[4] is empty. Stop.
   • Return ["bbbbb", "ccccc"].

5. Common mistakes candidates make

• Off-by-one: Using 0-indexing for the pointer when the problem IDs are 1-indexed.
• Redundant loops: Resetting the pointer back to 1 every time, instead of keeping it at the "next expected" position.
• Efficiency: Returning a new list/array in each call—ensure you only return the elements that just became part of the ordered sequence.

6. Interview preparation tip

Think of the pointer as a "frontier." Data behind the pointer is already emitted; data at the pointer is the next bottleneck. This mental model helps in all sorts of "Reordering Buffer" problems common in systems engineering.