
Funny. I was asked that question (worded differently) in an interview at Google Belo Horizonte. I gave this same algorithm, but instead of if (randFloat(0.0, 1.0) < 1.0 / count) I used if (randInt(0, count) == 0), where randInt(0, n) returns a random integer (uniformly) in the range [0..n). As far as I can tell, it's exactly the same algorithm (even slightly better as there are no floating point operations), but the interviewer kept saying that it was not the right answer. First I showed him an empirical proof (using an example with a few items) and then I showed an inductive proof, but he just said I was wrong and it was time to move for the next question. Weird. Anyone can tell me what's wrong with it?
edit  in the question I was given there was no boolean property that had to be satisfied, just a collection of items (of course, the size of the collection was unknown and the algorithm had to be O(n) in time and O(k) in space AND we could only iterate once through the collection). 