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, self.head.next, 1 while node: if random.randint(0, index) is 0: result = node node = node.next index += 1 return result.val
I tried the same code with
if random.random() <= (1/index): result = node
and it doesn't work, any ideas?
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
Ah that makes sense! Also, I forgot to convert the fraction into a float
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.