3 ms·
"Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage." I assume they meant arbitrarily long instead of
by dadkins 16y ago
"Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage."
I assume they meant arbitrarily long instead of infinitely long. In which case, I just wrote that code today:
val := nil
for i, x in range a {
if rand.Intn(i+1) == 0 {
val = x
}
}
- astrofinch 16y agoThe probability that a given list item will be selected is not uniform.
- dadkins 16y agoSure 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.
- astrofinch 16y agoSorry, 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?).