algoadvance

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.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the head of the singly linked list head.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

Note:

• The linked list is not empty and will contain at least one node.

Clarifying Questions

1. Is the length of the linked list known beforehand?
   • No, the length of the linked list is not provided. We may need to calculate it.
2. Can we assume the linked list will be static (no changes after initialization)?
   • Yes, after initialization, the linked list will not change.
3. What should the behavior be in the case of multiple calls to getRandom()?
   • Each call to getRandom() should return a node value chosen randomly, with each node having an equal probability of being chosen.

Strategy

To solve this problem efficiently, we can use Reservoir Sampling algorithm, which allows us to randomly select an element from a list of unknown length where each element has an equal probability of being selected.

Steps to implement:

1. Initialization:
   • Store the head of the linked list to traverse it later.
2. getRandom Function:
   • Initialize result to None.
   • Initialize current to the head and set index n = 1.
   • Traverse the linked list:
     • For the current node, decide whether to select it or not with a probability of 1/n.
     • If selected, update result with the current node’s value.
     • Move to the next node and increment n.
   • Return the value of result.

Code

Here’s the implementation of the problem using the described strategy:

import random

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def __init__(self, head: ListNode):
        self.head = head

    def getRandom(self) -> int:
        # Initially, the result is the value at head
        result, current, n = None, self.head, 1
        
        while current:
            # Use random to decide whether to update the result
            if random.randint(1, n) == n:
                result = current.val
            current = current.next
            n += 1
        
        return result

Time Complexity

• Initialization (__init__ method): O(1) because we’re only storing the reference to the head of the linked list.
• getRandom method: O(N) where N is the number of nodes in the linked list, as we need to traverse the entire list to ensure each node has an equal probability of being selected.

This approach guarantees each node has an equal chance of being returned due to the properties of the reservoir sampling algorithm.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?