#615 · Modules and random · Advanced · 120 XP · about 25 min
A sensor sends readings one after another, far too many to keep. You want k of them chosen at random so that every reading has the same chance of being picked, but you can look at each reading only once, and you do not know in advance how many will come.
Write sample_stream(stream, k) where stream is any iterable, such as a list, a range or a generator that can be read only once. Return a list of k items from it, chosen so that every group of k items is equally likely. If the stream has k items or fewer, return all of them. The items may be in any order.
Keep at most k items in memory at any time: that is the real challenge, because a real stream may not fit. Use the random module's shared functions, such as random.randint, and do not call random.seed.
sample_stream(range(100), 5) # returns 5 different numbers from 0 to 99 sample_stream([4, 8, 15], 5) # returns 4, 8 and 15 in some order sample_stream((n * n for n in range(10)), 3) # 3 of the squares 0, 1, 4 ... 81
0 <= k <= 1,000The tests check the size of the sample, that its items come from the stream, and that over thousands of runs every item is picked about equally often.
First solves only, ranked by stars and then time.