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

  • 10

    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,, 1
            while node:
                if random.randint(0, index) is 0:
                    result = node
                node =
                index += 1
            return result.val

  • 0

    I tried the same code with

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

    and it doesn't work, any ideas?

  • 1


    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


    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.