Stream the multiples of several numbers in increasing order

Produce an endless stream, in increasing order, of every positive integer that is a multiple of at least one of the given bases. Values are computed on demand: the caller asks for the next one, and nothing is precomputed or bounded in advance.

Interface

Unless you agree on a different interface with the interviewer, assume:

• multiples(bases: list[int]) -> Iterator[int] — a generator. Every value is a multiple of some base, values strictly increase, and a value that is a multiple of several bases appears once.

Example

g = multiples([3, 5])
[next(g) for _ in range(10)]  -> [3, 5, 6, 9, 10, 12, 15, 18, 20, 21]   # 15 once

g = multiples([4, 6])
[next(g) for _ in range(8)]   -> [4, 6, 8, 12, 16, 18, 20, 24]          # 12 and 24 once

Constraints

• 1 <= len(bases) <= 10^3; bases are positive integers and may repeat or divide one another.
• Producing each value should cost O(log k) for k bases, and memory should stay O(k) however far the caller reads.

Clarifying questions

• Should duplicates (a value that several bases divide) appear once?
• Can the bases contain 1, duplicates, or values that divide others?
• Is the caller going to read a fixed number of values, or keep going forever?
• Do you want a generator, or a class with next() and maybe peek()?

What a strong answer covers

• A min-heap holding the next multiple of each base: pop the smallest, push that base's next multiple, and skip a popped value equal to the last one returned.
• O(log k) per value and O(k) memory; why a sieve or a precomputed list doesn't fit an endless stream.
• Removing repeated bases and bases that are multiples of other bases up front.
• Tests against a brute force that checks each integer in turn.

Follow-ups

• Hamming numbers: the stream of products of the given primes (for [2, 3, 5]: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...). What changes, and how do you avoid duplicates?
• Jump straight to the n-th value without generating the ones before it (binary search with inclusion and exclusion for small k).
• Merge this stream with other sorted streams lazily.
• Make the generator resumable after a restart: what state do you persist?