# Tech Interview Exam Question: Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

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

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

```
/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
Note that the head is guaranteed to be not null, so it contains at least one node.
*/
};

/**
* Returns a random node's value.
* @return {number}
*/
Solution.prototype.getRandom = function() {

var total = 1;
while(p.next !== null){
p = p.next;
total++;
}

var index =  Math.floor(Math.random() * Math.floor(total))
for(var i=0;i<index;i++){
p = p.next;
}

return p.val;

};

/**
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(head)
* var param_1 = obj.getRandom()
*/

```

Random Set- Phone Interview
CompletedJune 1, 2019 7:41 AM
Time Spent: 38 minutes 29 seconds
Time Allotted: 1 hour 30 minutes
In order to provide you a more accurate assessment, we are waiting for more users to take this interview.
Email me when my report is ready
Find Pivot Index
EASY
741 / 741 Testcases Passed
Details