Can this solution be considered random (beats 87%)


  • 0
    M

    So the idea is, to make a loop in the linked list by linking the tail and the head of the list.
    We also declare another pointer to the head of the list called iter.
    Each time the getRandom() method is called we generate a random integer using Pythons randint() in a given range (here I chose 11) and we move our iter pointer the amount of fields ahead (keeping in mind that the list has a cycle).

    The question is, can this be considered a random approach, that fulfills the requirements of a uniform chance for each node to being picked? We have two sources of randomness - the starting point (which is equal to the last random value) and the amount of nodes that we will skip.

    I am looking for a more theoretical explanation.

    @edit I guess the skip value we get from randint() should be in the range (0, N) in order to give each value a chance of being selected.

    from random import randint
    
    class Solution(object):
    
        def __init__(self, head):
            self.head = head
            self.iter = head
            
            iter = head
            while iter.next is not None:
                iter = iter.next
            iter.next = head
            
    
        def getRandom(self):
            skip = randint(0, 11)
            while skip > 0:
                skip -= 1
                self.iter = self.iter.next
            return self.iter.val
    

  • 0
    A

    @mu99in Theoretically this is not random, since all nodes numbered after N*11 could never appear before the Nth getRandom() call.


  • 0
    M

    @ayuanx thanks for the answer, I addressed the situation you mentioned in the edit
    " I guess the skip value we get from randint() should be in the range (0, N) in order to give each value a chance of being selected."


  • 0
    A

    @ayuanx but the question doesn't ask for a truly random selection, it asks for 'equally probable', those aren't the same things.


Log in to reply
 

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