Linkedin Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
The basic idea of the fisher yates is this:
|1 2 3 4 5
Do a swap of 1 and random(1,2,3,4 5) = 3
3|2 1 4 5
Do a swap of 2 ad random(1, 2, 4, 5) = 4
3 4 | 1 2 5
Notice how after something it swapped, it is no longer available for swap.
Therefore on the first pass there was a 1/n chance of any one element being picked to swap. And on the second we never look at that element again so there is a 1/(n-1) chance of picking any single element on the second pass.
so on the n'th pass there is a 1/1 chance of picking that element.
Therefore each permutation has the probabily of 1/(n!) which is perfectly "random".
Here is C++ solution.
I assume the rand() function guarantee the uniform distribution of the random numbers.
#include<time.h>
#include<iostream>
#include<chrono>
#include<random>
#include<thread>
using namespace std;
void swap(int *A, int s, int d)
{
int tmp= A[s];
A[s] = A[d];
A[d] = tmp;
}
void shuffle(int* A, int len)
{
for (int i = len-1; i >0; i--)
{
int next = rand()% (i+1);
swap(A, next, i);
}
}
int main()
{
int A[10] = {1,2,3,4,5,6,7,8,9,10};
srand(time(NULL));
for (int j = 0; j < 20; j++)
{
shuffle(A, 10);
for (int i = 0; i < 10; i++)
cout<<A[i] << ", ";
cout<<endl;
}
return 1;
}
Fisher Yates Shuffle :
for ( i=0; i < A.length -1 ; i++ ) { j = randInt(A, i, A.length -1); swap(A, i, j) }The -1 on the A.length is not needed, but notice the final iteration if you exclude the -1 does nothing extra vs. the version above (swaps the final element with itself deterministically).
- RecruitingForSandvineCanada June 15, 2015