News for hackers. Stuff that matters.
Re:Help wanted: Google hiring in 2011 by tung on Tuesday January 25, 2011 @08:14PM (#2141682)
> "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage."

My shot: pick some random number, go through that many linked list items and return the item you're at. Only needs to store the current item pointer and the random number. Maybe I'm missing something simple, though to be fair, it's a lot harder to answer these kinds of questions when you're under the scrutiny of an interview.

Re:Help wanted: Google hiring in 2011 by nostrademons on Wednesday January 26, 2011 @01:55AM (#2142432)
That's not quite random, because you're selecting items with probability 1/RAND_MAX. The elements beyond RAND_MAX will never be selected.