News for hackers. Stuff that matters.
Re:Help wanted: Google hiring in 2011 by dadkins on Wednesday January 26, 2011 @09:19AM (#2143329)
Sure it is.

Base case: In a one item list, the first element is selected with probability 1.

Induction: Assume we've picked an element uniformly at random from the first n elements. When we encounter the n+1'th element, we pick it with probability 1/(n+1). Thus, we now have a uniformly random sample from the first n+1 elements.

Re:Help wanted: Google hiring in 2011 by astrofinch on Thursday January 27, 2011 @02:28AM (#2146984)
Sorry, I misunderstood your algorithm description. I thought the word "pick" meant "return this item as your answer". I guess your intended meaning should have been clear from your code (Scala?).