Taro Logo

Linked List Random Node

#70 Most AskedMedium
26 views
Topics:
Linked ListsGreedy Algorithms

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:

  • The number of nodes in the linked list will be in the range [1, 104].
  • -104 <= Node.val <= 104
  • At most 104 calls will be made to getRandom.

Follow up:

  • What if the linked list is extremely large and its length is unknown to you?
  • Could you solve this efficiently without using extra space?

Solution


Clarifying Questions

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:

  1. Can the linked list be empty? If so, what should I return?
  2. What is the range of values within the linked list nodes?
  3. Is the linked list size known beforehand or do I need to determine it?
  4. Is it acceptable to modify the linked list during the random selection process (e.g., for shuffling or temporary storage)?
  5. Is a uniform random selection required, meaning each node has an equal probability of being selected?

Brute Force Solution

Approach

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:

  1. First, we go through the entire chain and count how many items there are.
  2. Then, we pick a random number between one and the total number of items we counted.
  3. Starting from the beginning of the chain again, we move through the items one by one until we reach the item that matches the random number we picked.
  4. We then return that item as our randomly selected item.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – The solution involves iterating through the linked list twice. The first iteration counts the number of nodes, which takes O(n) time, where n is the number of nodes in the linked list. The second iteration traverses the list again to reach the randomly selected node, which also takes at most O(n) time. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).
Space Complexity
O(1) – The provided solution involves iterating through the linked list twice. During the first pass to count the nodes, a counter variable is used, which takes constant space. In the second pass to find the random node, another counter is used, also taking constant space. No additional data structures that scale with the input size N (the number of nodes in the linked list) are created. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The 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:

  1. Start at the beginning of the linked list and choose the first node as our current random choice.
  2. Move to the next node in the list.
  3. Decide whether to replace our current choice with this new node. The probability of replacing it should get smaller the further along the list we traverse.
  4. Continue moving through the list, deciding whether to replace the current choice at each node.
  5. When you reach the end of the list, the node you've currently chosen is the final random selection. It's been chosen fairly because each node had an equal chance to be the final choice.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the linked list once, visiting each node to determine if it should replace the current random selection. The number of nodes in the linked list is represented by n. Each node visit involves a constant time operation (random number generation and comparison). Therefore, the time complexity is directly proportional to the number of nodes in the linked list, resulting in O(n) time complexity.
Space Complexity
O(1) – The algorithm uses a single variable to store the current random choice. No other data structures are created or used. The space required does not depend on the size of the linked list, N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Empty list (head is null)
How to Handle:
Return null or throw an exception since there are no nodes to select from.
List with only one node
How to Handle:
Return the value of the only node, as it's the only possible choice.
Very large list (potential memory issues)
How to Handle:
Use reservoir sampling to select a node in O(1) space and O(n) time.
List with integer overflow potential in length calculation
How to Handle:
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
How to Handle:
Assume a good random number generator or implement a fallback with error handling.
Node values are not unique
How to Handle:
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
How to Handle:
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
How to Handle:
This is a theoretical limitation of the random number generator, so ensuring a high-quality random number generator is used is key.
0/141 completed