2 ms·
> "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 ra
by munificent 16y ago
> "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?