# Can this solution be considered random (beats 87%)

• 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):

while iter.next is not None:
iter = iter.next

def getRandom(self):
skip = randint(0, 11)
while skip > 0:
skip -= 1
self.iter = self.iter.next
return self.iter.val
``````

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

• @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."

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

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