There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Conditions :
- Use random number function rand() that returns a number between 0 and 1.
- It must be done in O(N) time
Solution:
1. Take 2 arrays R[K] and Num[K]
2. For each element in sorted array read one by one and do :
1. Generate a random number r.
2. If R is not full, insert r into R and element into Num array else replace r with highest random number in R and insert current element into corresponding index in Num array (Note that we want to keep the least K random numbers and corresponding elements in list)
3. Print Num[]
Complexities :
Time : O(N)
Space : O(K)
void random\_selection(int\[\] input, int N, int K){
int number\[K\];
double random\[K\];
int count = 0;
for(int i=0; i<N; i++){
double r = rand();
if(r < number\[count-1\]){
index = insert(random, K, &count, r);
number\[index\] = input\[index\];
}
}
for(int i=0; i<K; i++){
printf("%d ", number\[i\]);
}
}
int insert(double \*list, int K, int \*count, double entry){
if(\*count == K-1){
(\*count)--;
}
int i = \*count;
while(\*(list+i) > entry){
\*(list + i + 1) = \*(list + 1);
i--;
}
\*(list + i + 1) = entry;
(\*count)++;
return i+1;
}