algoadvance

You are given a stream of n tuples representing (id, value). Each id is unique and in the range from 1 to n, and the stream is not presented in any particular order. Implement the OrderedStream class:

• OrderedStream(int n) Initializes the object with n integers.

• List<String> insert(int id, String value) Inserts the pair (id, value) into the stream, then returns the largest possible list of ordered values that can be returned from the stream, starting from the current position.

Clarifying Questions

1. Is the id in the range always from 1 to n? Yes, the id is always in the range from 1 to n.

2. Should the return list always start from the current position and continue in sequence until a missing id is found? Yes, the returned list should start from the current position and continue until a gap (missing id) is encountered.

3. What should happen if an id that is already inserted is received again? You can assume that ids are always inserted only once and they are unique.

Strategy

To implement this, we will:

1. Use a list to store the values corresponding to each id.
2. Keep track of the smallest current position that we have not returned yet.
3. When inserting, update the list at the appropriate index.
4. Return the longest contiguous sublist starting from the current position.

Code

class OrderedStream:

    def __init__(self, n: int):
        self.stream = [None] * n  # Initialize a list of None with size n
        self.ptr = 0  # Start with the first position

    def insert(self, id: int, value: str) -> List[str]:
        self.stream[id - 1] = value  # Place the value at its correct position
        result = []
        
        # Check from the current position to see what can be returned
        while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
            result.append(self.stream[self.ptr])
            self.ptr += 1
            
        return result

Time Complexity

• Initialization: O(n) since we are creating a list of size n.
• Insertion: O(m) where m is the number of contiguous elements starting from ptr that are not None.

Given that each insert operation could potentially examine up to all n elements in the worst case (when all are filled in sequence), each insertion could be O(n) in the worst case. Therefore, we aim to make the insert operation O(m) where m refers to the number of contiguous elements from ptr.

In typical scenarios, the average time complexity for inserting and returning the ordered elements will likely be lower due to the contiguous chunks.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?