Skip to content

Instantly share code, notes, and snippets.

@santhalakshminarayana
Created September 15, 2019 18:53
Show Gist options
  • Save santhalakshminarayana/4095134cf1d0aeca7869c52a9b0d9048 to your computer and use it in GitHub Desktop.
Save santhalakshminarayana/4095134cf1d0aeca7869c52a9b0d9048 to your computer and use it in GitHub Desktop.
Given a stream of elements too large to store in memory, pick a random element from the stream with uniform probability.
import random
def pick_random(l):
'''
l(list) : imagine stream is passed as list
in loop
'''
count=1
x=l[0]
print(x)
for i in l[1:]:
count+=1
el=random.randrange(0,count)
if el is count-1:
x=i
print(x)
'''
Input:
------
pick_random(l=[4,2,5,2,1,2])
output:
-------
4
2
5
5
1
1
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment