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

• ``````import random
class Solution(object):

"""
@param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
"""

def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
index = random.randint(0, pos)
if index == 0:
pos += 1
return reservoir.val

# Your Solution object will be instantiated and called as such:
# 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

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