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;
}
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:
Or maybe I'm missing something here?