Python reservoir sampling solution (when the length of linked list changes dynamically)


  • 10
    N

    The problem is a little ambiguous. In the interview, you should ask clearly whether the list length is unknown but static or it is unknown and dynamically changing. In the first case, you can simply precompute the length and generate random indices based on that. It is faster than the reservior sampling solution.

    If the list length changes dynamically, reservior sampling is a good choice. If you are not familiar with it, check here.

    class Solution(object):
    
        def __init__(self, head):
            self.head = head
    
        def getRandom(self):
            result, node, index = self.head, self.head.next, 1
            while node:
                if random.randint(0, index) is 0:
                    result = node
                node = node.next
                index += 1
            return result.val
    

  • 0
    B

    I tried the same code with

    if random.random() <= (1/index):
        result = node
    
    

    and it doesn't work, any ideas?


  • 1
    N

    @bdevnani3

    The idea is good. But there are two minor things here.
    First, the index is from 0 to index inclusive. So it should be 1 / (index + 1).
    Second, since random returns number in [0, 1), where 1 is excluded, we should use the < instead of <=.


  • 0
    B

    @newman2

    Ah that makes sense! Also, I forgot to convert the fraction into a float


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.