Implements the random reservoir sampling algorithm of Vitter. Reservoir Sampling is an algorithm designed to take K samples from a stream of samples of unknown size in linear time. This is a solution to the following interview question: "You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describ…

sampling.py

from random import randint

class Sampler:
    def __init__(self, maxSamples=30):  # maxSamples set to 30 by default for better console output
        self.samples = []
        self.counter = 0
        self.maxSamples = maxSamples

    def sample(self, sample):        
        if(self.counter < self.maxSamples):
            self.samples.append(sample)
        else:
            index = randint(0, self.counter)
            if(index < self.maxSamples):
                self.samples[index] = sample
                
        self.counter = self.counter + 1