Google Interview Question
Software Engineer / DevelopersCountry: India
it's a shuffle deck question.
(1) prepare a vector filled with 1-n (the deck) in order
(2) for(int I=0;i<n;i++)
int ind=floor(random()*INT_MAX)%n; //that gives a random index in 0 to (n-1)
swap(deck[i],deck[ind]);
That's it. The code only uses the random API given in the question. There is no need to write a new random function.
@guangsumengmianxia
be carefull in an interview with these statement it shows some ignorance to important details even if your answer is very practical and fast.
But your shuffle has a problem the way you wrote it (I once thought it would be easier that way you wrote it and got suspicious, so I checked it a while ago and it wasn't good at all). If your variable "ind" was uniform, your swap will not lead to a uniform distribution, because the elements in front are more likely to be swapt multiple times. Essentially, the index 0 has probability 1/n to land at any place in the interval [0..n) at the first iteration (which is good). But, if it is swaped with any of the elements in [1..n) the element which originates from index 0, has another chance to go back to it's original position thus pulling the probability slightly towards staying at it's original position.
You can prove it or you can write a monte carlo to show it. I did both, the shuffle will not produce a random permutation (which is usually understood as every permutation has exactly the same probability to occure, which is 1/(n!)) although it is close to one.
2) doing the modulo will not be truely uniform except when n is a power of 2. While this is minor there are situations where it matters. So it's essential to be aware of and advantageous to know a way out.
yea, you are right, there is no need for a new random number generator, but for a function that uses the existing one and makes one whre you can define the interval. Be it in a function or just a line of code is really not the question here.
To do Uniform stuff, one needs to do these steps.
1. Get a function -> next_higher_permutation( array ) : available from here :
stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string
2. A random no generator to pick large integers from range [0,N)
3. A really large integer container for storing n! ( n factorial ).
Now, the algorithm.
1. Use [2] to generate a number between 0 and n! ( n factorial ) say it is N.
2. Start with the sorted permutation : [ 0,1,2,...n-1 ] as array and then apply
next_higher_permutation on the array N times.
that's a shuffle deck question
(1) fill an array deck[n] with numbers 1 to n;
(2) for(int I=0; I<n;i++){
int ind=floor(random()*INT_MAX)%n; //gives a random index from 0 to n-1
swap(deck[i],deck[ind]);
}
that's it. There is no need to rewrite a random function. You only need to use the API random() given in the question.
namespace RandomPermutation {
float getRandom() {
double randValue = rand();
return randValue / RAND_MAX;
}
int getRandomInt(int max) {
return getRandom() * max;
}
vector<int> getRandomPermutation(int n) {
vector<int> permutation(n,-1);
for (int i=0; i<n; i++) {
permutation[i] = i+1;
}
int temp;
for (int i=0; i<n; i++) {
int shuffleIndex = getRandomInt(n);
temp = permutation[i];
permutation[i] = permutation[shuffleIndex];
permutation[shuffleIndex] = temp;
}
return permutation;
}
}
I assume that we not rotating ' . ' but just a number around so if the input will be something like 0.123456789 ans we want to rotate 3 number the outcome will be. 0.123456789
1.023456789
1.203456789
2.103456789
2.013456789
0.213456789
As you can see we rotating only 3 numbers around ' . ' symbol and to tall permutation is n!.
public class NumPermutation {
static int chunk = 0;
static StringBuilder builder;
public static void main(String[] args) {
builder = new StringBuilder(getRandNumberAsString());
chunk = 3;
permutate(chunk);
}
public static String getRandNumberAsString(){
StringBuilder builder = new StringBuilder(String.valueOf(Math.random()));
builder.deleteCharAt(1);
return builder.toString();
}
public static void permutate(int size){
if (size == 1){
return;
}
for (int i = 0; i < size; i++) {
permutate(size - 1);
if (size == 2){
System.out.println(builder.charAt(0) + "." + builder.substring(1));
}
leftRotation(size);
}
}
public static void leftRotation(int size){
char tmp = builder.charAt(0);
char arr[] = builder.toString().toCharArray();
for (int i = 0; i < size; i++) {
arr[i] = arr[i + 1];
}
arr[size - 1] = tmp;
builder = new StringBuilder(String.valueOf(arr));
}
}
Assumption 1st natural numbers include 0: 0,1,2,3,4,5 would be a valid result if n = 6
1. we need a function to produce a random number between 0..k-1 interval: [0..k)
let's suppose we had this.
2. choose the element for the first position in the array with 1/n probability
3. choose the element for the second position the array with 1/(n-1) probability etc...
now let's think how can we create the random function that returns [0..k) from a random function that returns [0..1), at first glance, just multiply by k, right?
the question is, is the distribution 0..k-1 truely uniform if random [0..1) is uniform?
let's see:
everything between [0..1/k) maps to 0
between [1/k .. 2/k)) maps to 1
between [(k-1)/k .. k/k) maps to k-1
k/k = 1, it seems uniform at this point, but double is represented in binary and thus if k is not a power of 2 the number space cannot be seperated in exactly same sized spaces.
Let's for a moment think a double would be 8bit fixed point and k would be 3
[0..85)-> 0, p(0) = 85/255
[85..170) -> 1, p(1) = 85/255
[170..256) -> 2, p(2) = 86/255
this is not uniform. So it turns out above int random(int k) is not truely uniform either. How to get it uniform (if that little non-uniformity would matter)
first of all I would get rid of the double and just use the mantissa which is an integer, I think of about 54 bits on a 64 bit system for simplicity, how ever, let's assume it's 8 bits and scale it up later and let's suppose our k is 7
- floor((2^8) / 7) = 36
- 36 * 7 = 252
now create randomInt to extract the mantisa from the double and replace the calculation's constants
- Chris November 15, 2016appropriately. There is almost certainly a solution while keepting the double as well, maybe somebody could point it out.