Symantec Interview Question Software Engineer / Developers
=>Take a function rand() which returns value between [0, 1) uniformly or use function rand(n) = n*rand() which return value between 0- (n-1) using uniform probability distribution.
=>Now create a array A[0..n-1] = [0..n-1]
now rake an array R.
k = n;
for(i = 0; i < n; i++){
a = rand(k);
R.push(A[a]);
swap(A[a], A[k-1]);
k--;
}
return(R);
Verification:
1.) Yes, R contains values between 0-n-1;
2.) Yes, R has no repeated numbers
3.) R can be filled in O(n) so yes deterministic time.
4.) Correlation factor: Selection of one number should not affect the probability of selecting other number.
here correlation factor = 0;
for each location 0..n-1 the probability of putting any number is 1/n.
->At 0th index probability of putting a number say, x is: 1/n
->at 1st index probability of putting a number y is: (n-1)/n * 1/(n-1) = 1/n
->at 2nd index probability of putting a number z is: (n-1)/n *(n-2)/(n-1) * 1/(n-2) = 1/n
and so on. So selection of any number at any position is independent of any number being selected. So
they have independent and uniform probability.
import java.util.HashSet;
import java.util.Random;
public class RandNoDuplicates {
public static void main(String[] args) {
Random rand=new Random();
HashSet<Integer> set=new HashSet<Integer>();
Integer size = 5;
for (int i=0;i<size;++i)
{
Integer number=rand.nextInt(5);
//System.out.println(number);
Boolean isAddSuccess =set.add(number);
if(!isAddSuccess)
i--;
}
System.out.println(set);
}
}
The method is a hash function. The input is the number, the output is the index of the array.
- Anonymous November 11, 2009