382-linked-list-random-node

Try it on leetcode

Description

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 integer array nums.
• 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 choosen.

 

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(Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # @Problem Statement:
    #   Given a Singly LinkedList return a RandomNode
    #
    # @Input: Head Node
    # @Output: Random Node
    #
    # @sample Input:
    #   1.[1,2,3] get Random -> 3 ,2,1,1,2,3
    #       All of them with equal probabaility
    #
    # @constraints:
    #   * N = [1,10^4]
    #   * -10^4 <= N.val <= 10^4
    #   * Atmost 10^4 calls
    #
    # @Solutions:
    #   1. Using array of node values:
    #       Idea:
    #           * init() -> stores linkedList in a array
    #           * getrandom -> return random sample from array
    #
    #       Complexity Analysis:
    #           * Time Complexity:init() -> O(n)
    #                           getrandom() -> O(1)
    #           * Space Complexity: O(n)
    #       code:
    #          def __init__(self, head: Optional[ListNode]):
    #               self.arr = []
    #
    #               while head:
    #                   self.arr.append(head.val)
    #                   head = head.next
    #               self.n = len(self.arr)
    #
    #           def getRandom(self) -> int:
    #               randIn = int(random.random()*self.n)
    #
    #               return self.arr[randIn]
    #   --------------------------------------------------
    #  2.By Maintaing Reservior Array:
    #       At Start We store the Reservior array of size k
    #       with elements from the input
    #       To ensure equal probability of picking elements from the array
    #       i.e k/n for all elements we should pick random values within
    #       k  for values outside k  we can discard it
    #
    #       Complexity Analysis:
    #           * Time Complexity:init() -> O(1)
    #                           getrandom() -> O(n)
    #           * Space Complexity: O(1)
    def __init__(self, head: Optional[ListNode]):
        self.headNode = head

    def getRandom(self) -> int:
        k = 1
        chosen_val = 0
        cur = self.headNode

        while cur:
            if random.random() < 1 / k:
                chosen_val = cur.val
            cur = cur.next
            k += 1
        return chosen_val


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()