LeetCode 2020 Dec 2 Linked List Random Node

Question: We are given a list of nodes, we have to return a random node. We should make sure each node have same probability. Meaning any number in that list can be returned at any time; we should not constantly return same number.

The Question in Leetcode

For this we will be trying the simple version of Reservoir Sampling. In general Reervoir sampling is used when we have huge list of elements lets say its size is (N) and from that we have to find the (K) random elements. For this problem we will be having K=1.

Pseudo Code

• First we will be initializing the head pointer.
• Then we will be setting the currentNode to the head node and number of elements as 1.
• In case the head node is null; our response will be always 0.

Consider for case where the list has only one node like [198]

• For the first time in case the head node is not null, then we will be finding the random value using Math.random() in-built java function. It will give us the value like 0.3234 this value we will check whether is lesser than 1.0 / currentIndex (or current number of nodes) which will be equal to 1; and 0.3234 < 1.0 is True so the value is set in the response (interger variable which holds the value to be sent).
• Next after setting the node value, we will be moving the current (variable holding the current ListNode) as current.next;
• Now when we are iterating the while loop; current != null will be false.
• So when we are having only one node, then always that response is sent.

Consider for case where the list has two nodes like [198,392]

• Like before the first time the first node will be set and moved to next node. And we will also increase the currentIndex by 1 (so now its 2).
• Now if we are checking whether current != null, it will be true.
• Now again we will use Math.random() function to get the random value it can be something like 0.8923 or even 0.1234 or 0.546. Now the currentIndex will have become 2.

Case 1: Math.random() returns value as 0.8923 now 1.0/2 = 0.5; Now if we compared 0.8923 < 0.5 then it will be false; so nothing happens we move on to next node.

Case 2: Math.random() return value as 0.1234; now 1.0/2 = 0.5; Now if we compared 0.1234 < 0.5 then it will be true; now we will set this currentNode value to response variable.

So when we have 2 nodes, we can have the probability like either first node value will come or second node value will come.

Likewise it will go if we are having N nodes.

Java Code

private ListNode head;
    public Solution(ListNode head) {
        this.head = head;
    }

 public int getRandom() {
        int response = 0;
        int currentIndex = 1;
        ListNode current = this.head;
        while(current != null){

                if(Math.random() < (1.0/currentIndex)){
                response = current.val;
                }

                current = current.next;
                currentIndex = currentIndex +1;
        }

        return response;
    }