Glad to see catching up with new interview questions, add my Python solution and proof


  • 0
    P
    import random
    class Solution(object):
    
        def __init__(self, head):
            """
            @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
            :type head: ListNode
            """
            self.head = head
    
        def getRandom(self):
            """
            Returns a random node's value.
            :rtype: int
            """
            reservoir, head, pos = self.head, self.head.next, 1
            while head:
                index = random.randint(0, pos)
                if index == 0:
                    reservoir = head
                head = head.next
                pos += 1
            return reservoir.val
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(head)
    # param_1 = obj.getRandom()
    

    Wish to see NP-complete problems, semaphore problems, and geometry problems as well!

    Proof:
    1.Probability of first k items still in reservoir finally is that of never getting chosen in the process:
    kth item...k+1th item......nth item
    k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n
    2.Probability of i'th item in reservoir finally is that of getting chosen at its round and never getting chosen later:
    k/i * i/(i + 1) * ... * (n-1)/n = k/n


Log in to reply
 

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