382.Linked List Random Node

Tags: [math], [random]

Link: https://leetcode.com/problems/linked-list-random-node/\#/description

Given a singly linked list, return a random node's value from the linked list. Each node must have thesame probabilityof being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

Solution: Math, Random, Reservoir sampling

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):

    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        :type head: ListNode
        """
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        :rtype: int
        """
        curr = self.head
        counter = 0
        result = None
        while curr:
            counter += 1
            rand_num = random.randint(1, counter)
            if rand_num == counter:
                result = curr.val

            curr = curr.next

        return result

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

Revelation:

• Reservoir sampling: reference: http://blog.jobbole.com/42550/
• The main idea here is that: Think about we have a streaming of the numbers, such as 1, 2, 3, 4, 5, ... and we know the total number of these numbers is very very big. So space usage of the algorithm is our most concern. And we want an algorithm can randomly pick up a number from this number streaming.
• Think, there is only one number in this streaming, such as '1', so we just pick up it, the probability of picking up '1' is equal to 1. So the number of elements of the streaming is 1, and the probability of picking up this element is 1.
• Think, there are two numbers in this streaming, such as '1', '2'. Now '1' coming, and we have no choice, we must pick up it. And then '2' is coming, now we can decide to drop '1' and pick up '2' or not. The probability of dropping '1' and picking up '2' is 1/2. So we can randomly generate an integer [1, 2], if the random integer is equal to 2, then we drop '1' and pick up '2'. So the number of elements of the streaming is 2, and the probability of picking up either element is 1/2.
• Think, there are three numbers in the streaming, such as '1', '2', and '3'. Now '1' coming, and we have no choice, we must pick up it. And then '2' is coming, now we can decide to drop '1' and pick up '2' or not, the probability of dropping '1' and picking up '2' is 1/2, and similarly the probability of keeping '1' and dropping '2' is also 1/2, here we assume we keep the '1' and drop '2', whose probability is 1/2. Then '3' is coming, because we have dropped '2' and kept the '1', so now we need to decide to drop '1' and pick up '3' or not. Because there are totally 3 elements, so we know if finally we use '3' as the final result, which means drop '1' here and pick up '3', this probability should be 1/3. So we generate a random integer in the range[1, 3], and check whether this random int is equal to 3. Here we assume we kept '1' and drop '3'. At this moment, the probability of dropping '3' is (1 - 1/3) = 2/3. So we can calculate the probability that we finally use '1' as the final result should be equal to 1 * 1/2 * (1 - 1/3) = 1 * 1/2 * 2/3 = 1/3, from here we can see, the probability we pick up '1' in this streaming (number of elements = 3) is equal to 1/3, which is our goal.
• We can popularize this way to prove the streaming who has n elements. Think n - 1 elements have passed, now nth element is coming. Now we need decide to drop the result from n - 1 elements and pick nth as result or not. We assume the current result is randomly pick from n - 1 elements, so the probability of picking up the element as current result is 1/(n - 1). And the probability of dropping the current result and picking up nth as the result is 1/n, so if we pickup the nth as the result the probability 1/n. And if we kept the result chosen from n - 1 elements and drop the nth element, the probability = 1/(n - 1) * (1 - 1/n) = 1/(n - 1) * (n - 1)/n = 1/n, which proves the correctness of the above algorithm.

Note:

• Time complexity = O(n), n is the number of elements of the given linked list.
• Space complexity = O(1).