Random Numbers with Exceptions

[Question]
Write a function to generate random numbers in [0, N-1], excluding numbers in a given list. For example, N=10, the excluding list is {4, 6, 9}, then a random number is valid when it is not 4, or 6, or 9.

[Analysis]
This is another question that Reservior Sampling can be applied. The generator function will exclude the numbers in the range and give the equal possibility to the rest.

When there is only one number is excluded, the solution can be as simple as, generate one number from [0, N-2], if the generated number is equal to the excluded number, return N-1. This is a special case of Reservior Sampling.

[Solution]
int rand_except(int n, unordered_set<int>& exp) {
     int res=-1, count=0;
     for (int i=0; i<n; i++) {
          if (exp.count(i)>=0) continue;
          if ( rand()%(++count)==0 ) res = i;
     }
     return res;
}

Linked List Random Node -- LeetCode

[Question]

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.

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?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

[Analysis]
Another Reservior Sampling problem. The run time is at O(N) without additional space expense. See also the similar question Random Pick Index.

[Solution]
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* head;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head): head(head) {
    }
 
    /** Returns a random node's value. */
    int getRandom() {
        int res;
         for (int cnt=1,  ListNode* p = head;  p;  p=p->next, cnt++)
              if (rand()%cnt == 0) res = p->val;
     
        return res;
    }

};

Random Pick Index -- LeetCode

[Question]

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

[Analysis]
This is a typical Reservior Sampling problem. Usually, it is used to when data set is too large to feed into memory. The time complexity of pick() is O(N). The additional space is O(1).

[Solution]
class Solution {
    vector<int> n;
public:
    Solution(vector<int> nums): n(nums) {
    }
 
    int pick(int target) {
        int count=0, res=-1;
        for (int i=0; i<n.size(); i++) {
            if (n[i]!=target) continue;
            if (rand() % (++count) ==0) res=i;
        }
        return res;
    }

};