Linked List Random Node

Linked List Random Node

What is this problem about?

The "Linked List Random Node interview question" asks you to return a random node's value from a linked list. Every node must have an equal probability of being chosen. The catch? The list could be extremely large, and you might not know its length in advance. This "Linked List Random Node coding problem" is a classic application of a specific sampling algorithm.

Why is this asked in interviews?

Companies like Meta and Google ask this to test your knowledge of the "Reservoir Sampling interview pattern". It evaluates whether you can solve a problem with space constraints—specifically, finding a random element in a single pass without storing the entire list in memory.

Algorithmic pattern used

The Reservoir Sampling pattern is used here. You initialize your "result" with the value of the head node. As you iterate through the list at index i (starting from 0), you generate a random number between 0 and i. If that random number is 0, you replace your "result" with the current node's value. By the time you reach the end of the list, each node will have had a 1/n probability of being the final result.

Example explanation

List: 10 -> 20 -> 30

1. Index 0 (Node 10): Result = 10.
2. Index 1 (Node 20): Pick a random number in [0, 1]. If it's 0 (50% chance), Result = 20.
3. Index 2 (Node 30): Pick a random number in [0, 2]. If it's 0 (33% chance), Result = 30. Mathematically, the probability of any node being chosen is exactly 1/3.

Common mistakes candidates make

• O(n) space: Storing all nodes in an array and then picking a random index. This is fine if memory is unlimited, but usually, the interviewer wants a constant space solution.
• Incorrect probability: Using a logic that favors nodes at the beginning or end of the list.
• Inefficient length calculation: Traversing the list once to find the length and then again to pick a node. Reservoir sampling allows you to do it in one pass.

Interview preparation tip

Reservoir sampling is the standard answer for "random selection from a stream." Memorize the logic: for the i-th element, replace the current choice with probability 1/(i+1).