From a stream of events, return a random element. The class definition is

class StreamObserber()
    def observer(x):
    def sample(): # return an random element x

Solution Exploration

Code

V0 - Store all the elements

import random  


class StreamObserver:  

    def __init__(self):  
        self.n = 0  
        self.elements = []  

    def observe(self, x):  
        self.n += 1  
        self.elements.append(x)  

    def sample(self):  
        r = random.randint(0, self.n - 1)  
        return self.elements[r]

V1 - Limit the list size

class StreamObserverV1:  
 """  
 Optimize for memory, use a fixed size queue and discard the oldest element    when we have reached the maximum size.  
 """  
 def __init__(self):  
        self.elements = []  
        self.max_size = 10  

 def observe(self, x):  
        if len(self.elements) >= self.max_size:  
            self.elements.pop(0)  
            self.elements.append(x)  

  def sample(self):  
       r = random.randint(0, len(self.elements) - 1)  
       return self.elements[r]

V2 - Just Store that One Element

class StreamObserverV2:  

    def __init__(self) -> None:  
        self.elm = None  
        self.n = 0  

   def observe(self, x):  
        self.n += 1  
        prob = 1 / (self.n)  
        randomProb = random.uniform(0, 1)  
        if randomProb < prob:  
            self.elm = x  
        else:  
            pass  

   def sample(self):  
         return self.elm

Questions

How to test the implementation, it is randomized

• Push in 1 to 100 numbers, and sample for 10 times should have got at-least one less than 10 ?