Skip to content

Instantly share code, notes, and snippets.

@zdavkeos
Created October 30, 2011 22:40
Show Gist options
  • Save zdavkeos/1326551 to your computer and use it in GitHub Desktop.
Save zdavkeos/1326551 to your computer and use it in GitHub Desktop.
Sample answer to interview question: Given an unknown number of items one at a time, choose one at random using O(1) space
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment