โ† Google questions

Smallest missing ID stream processing

Filed under Google

Free read 3 of 3

Confirm the range of IDs and whether IDs can be duplicates or negative numbers.

The question

Design and implement two functions for stream processing: one to ingest incoming IDs and another to output the smallest ID that has not yet been received from the stream.

Constraints

  • IDs are positive integers.
  • Stream can be potentially infinite, requiring efficient data structures for insertions and queries.
  • Both ingestion and query operations should ideally execute in sub-linear time.

Examples

Input
ingest(1), ingest(2), get_smallest(), ingest(0), get_smallest()
Output
0
Why
Tracking received IDs allows identifying the smallest non-negative integer missing from the stream.

Approach

  1. Confirm the range of IDs and whether IDs can be duplicates or negative numbers.

Solution

O(1) amortized time per ingest, O(N) space

Python
class SmallestMissingStream:
    def __init__(self):
        self.seen = set()
        self.smallest = 0

    def ingest(self, val: int) -> None:
        self.seen.add(val)
        while self.smallest in self.seen:
            self.smallest += 1

    def get_smallest(self) -> int:
        return self.smallest

Tips

  • What they are testing: Test with duplicate IDs, out-of-order streams, and very large ID values to check for memory limits.
  • Common mistake: Using a sorted array or simple list where insertions take linear time, leading to poor performance on large streams.

Follow-ups

  • In-depth discussion on optimizations, data structures, and alternative approaches.

Related Google questions

Collected from public candidate posts and coding forums. Updated Nov 2026.