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

If the goal of the question is to select a random item where all items have the same probability of being selected, it's impossible. If you're willing to ditch even distribution, then one answer is:

    value pickRandomItem(node* list) {
        /* Always return first item. */
        return list.value;
    }
Or maybe I'm missing something here?

There are no comments on this comment yet.