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