Interview Questions

174. Given an array arr of size M containing distinct integers .......

Microsoft Interview Questions and Answers


(Continued from previous question...)

174. Given an array arr of size M containing distinct integers .......

Question:
Given an array arr of size M containing distinct integers, randomly select N distinct integers and output them. You are given the rand() function and N < M.


maybe an answer:


1. Store the index of the last element of the array (say in 'last').
2. Let x = rand()%M. x will be in [0,M-1] range. Output arr[x] and replace arr[x] with arr[last]. Do last--.
3. Repeat this step for N times, each time applying the mod operation with dividend one less than in the previous step i.e. rand()%(M-1), rand()%(M-2) and so on.
4. Time: O(N). Space: O(1).
5. In the above algorithm, you will be changing the array contents. If you want to maintain the array in the same state, you can keep track of all the changes you are making to the array and undo them after you printout the N values. This is better than making a copy of the array when M is large.


maybe an answer2:


M=arr.size();
while(N>0){
indx = rand()%M;
swap(arr[indx],arr[M-1]);
--N;-M;
} //the last N elements are the selected distinct integers//Time: O(N), Space : O(1)

(Continued on next question...)

Other Interview Questions