Two Stream Selection Questions

February 6, 2015

Today’s exercise provides two questions involving selection from a stream. Both require a solution that takes O(n) time and O(1) space.

First: Given a stream of unknown length, select a random item from the stream, with all items selected with equal probability. For instance, given the stream {A, D, F, A, G} the selection would return A with probability 40% and D, F or G with probability 20%.

Second: Given a stream of unknown length, each item in the stream paired with a weight, select a random item from the stream with all items selected with probability according to their weights. For instance, given the stream {1 A, 2 D, 5 F, 3 A, 9 G} the selection would return A with probability 20%, D with probability 10%, F with probability 25%, and G with probability 45%.

Your task is to write the two programs that select items from streams. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2 Responses to “Two Stream Selection Questions”

  1. Mike said
    from itertools import repeat
    from random import uniform
    
    def random_pick(items, weights=repeat(1.0)):
        """Provides a weighted selection from items, wherein the probability of being selected is the
            item_weight/total_weights.  The optional weights can be ints, floats, or Fractions.
            """
        total_weight = 0.0
    
        for item, weight in zip(items, weights):
            total_weight += weight
            if uniform(0.0, total_weight) < weight:
                choice = item
    
        return choice
    

    Examples:
    >>> items = (‘red’, ‘blue’, ‘green’)
    >>> Counter(random_pick(items) for _ in range(1000))
    Counter({‘green’: 353, ‘red’: 324, ‘blue’: 323})

    >>> weights = (0.5, 1.0, 1.5)
    >>> Counter(random_pick(items, weights) for _ in range(1000))
    Counter({‘green’: 519, ‘blue’: 317, ‘red’: 164})

    >>> from fractions import *
    >>> weights = (Fraction(1,2), Fraction(1,3), Fraction(1,6))
    >>> Counter(random_pick(items, weights) for _ in range(1000))
    Counter({‘red’: 504, ‘blue’: 344, ‘green’: 152})

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: