Sample answer to interview question: Given an unknown number of items one at a time, choose one at random using O(1) space

sequence_select.py

#!/usr/bin/env python

from random import random

class seq_selector:
    """
    Given an arbitrary and unknown length sequence of objects recieved
    one at a time, this module provides a random selection from the
    sequence using O(1) space.

    TODO: make thread safe?
    """

    def __init__(self):
        self.current = None
        self.count = 0.0

    def get_selection(self):
        """ returns current random selection """
        return self.current

    def clear(self):
        """ 
        Clears the selector and resets everything
        """
        self.current = None
        self.count = 0.0

    def feed(self, item):
        """
        register next item in sequence
        returns selection (changed or otherwise)
        """
        self.count += 1.0
        if random() < (1.0 / self.count):
            self.current = item

        return self.current



if __name__ == '__main__':
    """
    Runs a test of seq_selector
    """
    from matplotlib import pylab
    import numpy

    rng = 256    #length of seq
    cnt = 1000  #num trials
    
    seq = range(rng)
    seqr = seq_selector()
    res = []

    for _ in xrange(cnt):
        seqr.clear()
        for i in seq:
            seqr.feed(i)
        res.append(seqr.get_selection())

    n, bins, p = pylab.hist(res, rng)

    print 'Mean should be about:', 1.0*cnt/rng
    m = numpy.mean(n)
    print 'Mean is:', m
    print 'Std. Dev:', numpy.std(n)
    print 'Greatest outlier: +-', max(abs(numpy.max(n)-m), abs(numpy.min(n)-m))
    
    pylab.plot(bins, numpy.ones(len(bins))*cnt/rng, 'r', linewidth=2)
    pylab.show()