Design an Ordered Stream - Practice Coding Problems

Design an Ordered Stream - Problem

There is a stream of n pairs (idKey, value) 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.

Input & Output

Example 1 — Basic Stream Operations

$ Input: n = 5, operations = [[3,"ccccc"],[1,"aaaaa"],[2,"bbbbb"],[5,"eeeee"],[4,"ddddd"]]

› Output: [[],["aaaaa"],["aaaaa","bbbbb","ccccc"],[],["ddddd","eeeee"]]

💡 Note: Insert (3,"ccccc"): ptr=1, arr[1] is empty, return []. Insert (1,"aaaaa"): ptr=1, arr[1]="aaaaa", return ["aaaaa"], ptr=2. Insert (2,"bbbbb"): ptr=2, found consecutive values at positions 2,3, return ["bbbbb","ccccc"], ptr=4.

Example 2 — Sequential Order

$ Input: n = 3, operations = [[1,"first"],[2,"second"],[3,"third"]]

› Output: [["first"],["second"],["third"]]

💡 Note: Each insert returns exactly one value since they arrive in order: ptr advances one position each time.

Example 3 — Reverse Order

$ Input: n = 3, operations = [[3,"third"],[2,"second"],[1,"first"]]

› Output: [[],[],["first","second","third"]]

💡 Note: First two inserts return [] since ptr=1 is not filled. When (1,"first") arrives, all consecutive values 1,2,3 are returned.

Constraints

1 ≤ n ≤ 1000
1 ≤ idKey ≤ n
value.length == 5
value consists only of lowercase letters
Each call to insert will have a unique idKey

Visualization

Tap to expand

Understanding the Visualization

Stream Setup

Create stream of size n=5, pointer starts at position 1

Insert Operations

Insert (id,value) pairs in arbitrary order

Return Chunks

Return largest consecutive chunk from current pointer position

Key Takeaway

🎯 Key Insight: Use array for direct access and pointer to efficiently detect consecutive chunks

Asked in

G Google 25 a Amazon 18

The key insight is to use an array for O(1) direct access by ID and maintain a pointer to track the next expected position. When inserting, place the value at arr[idKey], then advance the pointer while consecutive values exist, returning all found values as a chunk. Best approach uses array-based direct access: Time O(n) total for all operations, Space O(n) for storage array.

Common Approaches

Approach	Time	Space	Notes
✓ Array-Based Direct Access	O(n)	O(n)	Use array indexing for O(1) access and pointer for current position
Brute Force with List Search	O(n²)	O(n)	Store all values and search for consecutive ones each time

Array-Based Direct Access — Algorithm Steps

Create array of size n+1 where arr[id] = value
Use pointer to track next expected ID
After each insert, advance pointer while consecutive values exist

Visualization

Tap to expand

Step-by-Step Walkthrough

Direct Insert

Place value at arr[id] position

Pointer Check

Check if arr[ptr] exists and advance

Consecutive Chunk

Collect all consecutive values from pointer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char arr[1001][100]; // 1-indexed array
    int ptr; // Next expected position
    int n;
} OrderedStream;

OrderedStream* createOrderedStream(int n) {
    OrderedStream* os = malloc(sizeof(OrderedStream));
    os->ptr = 1;
    os->n = n;
    for (int i = 0; i <= n; i++) {
        os->arr[i][0] = '\0'; // Empty string
    }
    return os;
}

char** insert(OrderedStream* os, int idKey, char* value, int* returnSize) {
    strcpy(os->arr[idKey], value);
    
    char** result = malloc(1000 * sizeof(char*));
    *returnSize = 0;
    
    // Collect consecutive values starting from ptr
    while (os->ptr <= os->n && os->arr[os->ptr][0] != '\0') {
        result[*returnSize] = malloc(100 * sizeof(char));
        strcpy(result[*returnSize], os->arr[os->ptr]);
        (*returnSize)++;
        os->ptr++;
    }
    
    return result;
}

int main() {
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each insert is O(1), but returning consecutive chunk can be O(n) in worst case

✓ Linear Growth

Space Complexity

O(n)

Array of size n to store all values

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array-Based Direct Access — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler