Smallest missing ID stream processing
Filed under Google
Free read 3 of 3Confirm 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
Confirm the range of IDs and whether IDs can be duplicates or negative numbers.
Use a boolean array or hash set to store seen numbers and iterate from 0 upwards to find the first missing ID.
Use a min-heap combined with a tracking variable, or a disjoint-set / range-merging structure to keep track of missing intervals efficiently.
Handle duplicate incoming IDs, missing starting from 0, and continuous sequential streams.
Solution
O(1) amortized time per ingest, O(N) space
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.