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.Example 1:
Input ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3] Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
[1, 104].-104 <= Node.val <= 104104 calls will be made to getRandom.Follow up:
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The problem requires us to pick one item from a connected chain of items at random. A simple approach is to first figure out all the items in the chain and then pick one at random from that collection.
Here's how the algorithm would work step-by-step:
import random
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next_node = next_node
class Solution:
def __init__(self, head: ListNode):
self.head = head
def getRandom(self) -> int:
list_length = 0
current_node = self.head
# Calculating the total number of nodes in the linked list
while current_node:
list_length += 1
current_node = current_node.next_node
random_index = random.randint(1, list_length)
current_node = self.head
node_index = 1
# Iterate to the randomly selected node
while node_index < random_index:
current_node = current_node.next_node
node_index += 1
# Now we've reached the target, return the value
return current_node.valueThe goal is to pick one node from a linked list completely at random. Since we don't know the length of the list ahead of time, we'll use a trick where our choice improves as we see more of the list, guaranteeing a fair selection.
Here's how the algorithm would work step-by-step:
import random
class ListNode:
def __init__(self, value=0, next_node=None):
self.value = value
self.next_node = next_node
class LinkedListRandomNode:
def __init__(self, head: ListNode):
self.head = head
def get_random(self) -> int:
current_node = self.head
random_node_value = current_node.value
node_count = 1
while current_node.next_node:
current_node = current_node.next_node
node_count += 1
# Probability of picking current
# node decreases as list grows
if random.random() < (1 / node_count):
random_node_value = current_node.value
return random_node_value| Case | How to Handle |
|---|---|
| Empty list (head is null) | Return null or throw an exception since there are no nodes to select from. |
| List with only one node | Return the value of the only node, as it's the only possible choice. |
| Very large list (potential memory issues) | Use reservoir sampling to select a node in O(1) space and O(n) time. |
| List with integer overflow potential in length calculation | Use a counter variable that does not overflow, like long, or avoid explicit length calculation by iterating only once using reservoir sampling. |
| Random number generator failure | Assume a good random number generator or implement a fallback with error handling. |
| Node values are not unique | The problem states values are unique, but if not, the algorithm would return one of the nodes with that value randomly. |
| Head node becomes null during iteration | The loop condition must check for null before accessing head.next to prevent a null pointer exception. |
| The random number generator consistently returns the same number | This is a theoretical limitation of the random number generator, so ensuring a high-quality random number generator is used is key. |