Some interesting interview Q&A around “randomness”

1 How to sample a random Element from an infinite stream?

For an average developed this is a insane question! or at-least it was for me!!!

If we know the length of the stream we can use in-build or numpy random function to generate a number.

import numpy as np
np.random.randint(0, len(stream_data)) 
import random
random.randint(0, len(stream_data))

What is random probability ? Its picking an element an element from N numbers i.e 1/N

How to sample from a stream where we don’t know the N ? Interesting right!

It’s true we don’t know the what N is actually, however can we exploit the formula 1/N by replacing N with i, where i is the current index of the element in the stream?

• Case 1: When there is only one element in the stream

def select_rand(big_stream):
    rand_element = None
    for i, e in enumerate(big_stream):
        if i == 0: # could have been if(len(big_Stream)==0),hold on!
           rand_element = e
    return rand_element

• Case 2: Consider stream length greater than 1 i.e the length varying from (1, i+1), starting from the index 1 to i+1. +1 since enumerate start from 0 and we wanted to consider the last element also for sampling

— Ok good! but how to sample a random element from given index i ? Lets see what is the probability of getting 1 in the range of [1, i+1]?

1/i+1

random.randint(1, i+1) == 1 

1 is selected because the length of the stream starts from index 1, use this property to select the element.

import random

def select_rand(big_stream):
    rand_element = None

    for i, e in enumerate(big_stream):
        if i == 0:
            rand_element = e
        if random.randint(1, i + 1) == 1:
            rand_element = e
    return rand_element

In more technical terms:

For i = 0, we would've picked uniformly from [0, 0].

For i > 0, before the loop began, any element K in [0, i - 1] had 1 / i chance of being chosen as the random element. We want K to have 1 / (i + 1) chance of being chosen after the iteration. This is the case since the chance of having being chosen already but not getting swapped with the ith element is 1 / i * (1 - (1 / (i + 1))) which is 1 / i * i / (i + 1) or 1 / (i + 1)

This is solved using loop invariant the dailycodingproblem.com mail says :), I have no idea what that means! Good one to get subscribed to.

2 Using a function rand5() that returns an integer from 1 to 5 (inclusive) with uniform probability, implement a function rand7() that returns an integer from 1 to 7 (inclusive)

import numpy as np
from collections import Counter
N = 1000
Counter(np.random.randint(1,6,N) + np.random.randint(1,6,N)//2)
# Counter({1: 392, 7: 847, 3: 2007, 2: 1209, 6: 1570, 5: 1973, 4: 2002})