[LeetCode] 384. Shuffle an Array

Problem : https://leetcode.com/problems/shuffle-an-array/

class Solution:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.nums
        

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        
        shuffled = self.nums[:]
        N = len(shuffled)
        
        for i in range(N):
            j = random.randint(i, N-1)
            shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
            
        return shuffled


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

[LeetCode] 382. Linked List Random Node

 Problem : https://leetcode.com/problems/linked-list-random-node/

The naive way is calculating the length of the list first, then randomize the position in the list. But how to get the random node when it is expensive to get the list length. For example, assume the list is saved on remote server and the operation 'getNext' is very expensive. How to collect get the random node with minimal cost?

The answer is Reservoir sampling.

To make the problem more generically, let's say we need to sample k elements.

Suppose we have an element at the position of i ( i > k ), when we reach the element, the chance to select this element is  k / i.

Later on, we can select another element to replace the ith element.  For i+1 element, the change for it is not be selected is  1 - 1 / (i+1) = i / (i+1). 

So if ith element will eventually be selected, its chance is:

(the probability of ith element be selected ) * (  the probability of i+1th element not be selected to replace ith element) 

= (k / i ) *  (1 - 1 / (i+1)) 

= (k/i) * (i / i+1) 

= k / (i+1).    

def reservoirSample(S, R, K):
    """
    S : the items to sample
    R : the selected sample items
    K : number of the needed sample items
    """
	
    # fill the reservoir array
    for i in range(K):
        R[i] = S[i]
        
    # replace elements with gradually decreasing probability
    for i in range(K, len(S)):
        j = random.randint(0, i)
        if j <= k:
            R[j] = S[i]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    ListNode head;
    Random random = new Random();
    
    public Solution(ListNode head) {
        this.head = head;    
    }
    
    public int getRandom() {
        
        ListNode p = this.head;
        
        int result = p.val;
        int count = 1;
        p = p.next;
        
        while (p != null) {
            count += 1;
            
            if (random.nextInt(count) == 0) {
                result = p.val;
            }
            p = p.next;
        }
        
        return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

Edited on 1/7/2022. Replaced with reservoir sample solution.