Pick one item uniformly from a stream
Asked at Jane Street, Two Sigma
Ticks stream past you one at a time. You do not know how many there will be, and you cannot store them all.
Return one item chosen uniformly at random from the whole stream, in a single pass, using only O(1) extra memory. Prove your method is uniform.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.