Introduction

In this blog post, we will explore how to solve the LeetCode problem "382" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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?

Explanation

• Reservoir Sampling: Use reservoir sampling to select a random node. This algorithm iterates through the linked list and maintains a "reservoir" of size 1 (in this case, just the selected node). For each node, there's a 1/i chance of replacing the current reservoir, where i is the index of the current node.
  • Iterative Traversal: Iterate through the linked list only once in the getRandom function, avoiding the need to store the entire list or its length beforehand.
  • Constant Extra Space: This approach uses constant extra space.

• Time Complexity: O(n), where n is the number of nodes in the linked list for getRandom(). O(1) for initialization. Space Complexity: O(1).

Code

    import random

# Definition for singly-linked list.
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:
        """
        Returns a random node's value.
        """
        reservoir = None
        count = 0
        curr = self.head

        while curr:
            count += 1
            if random.random() < (1 / count):
                reservoir = curr.val
            curr = curr.next

        return reservoir