Amazon Microsoft Interview Question
Software Engineer / DevelopersQuite easy off the bat,
Lets say you have to shuffle an array of type 'Card[]' with valid indices running from 0 to N-1.
for(int i = 0; i < N; i++) {
int j = (rand()%(N-i)) + i;
swap(&array[i], &array[j]); // void swap(Card*, Card*); swaps them
}
This guarantees you're equally likely to put any of the N Cards in the first position, equally likely to put any of the N - 1 remaining Cards in the next, so on and so forth... Therefore all permutations are uniformly likely.
Of course, RAND_MAX (usually about 2^15) must be fairly large compared to N. Otherwise, you should use
int j = (int)( rand() / (RAND_MAX + 1.0) * (N - i)) + i;
execute random function modulo number of songs
the return value will be the song to be played.
in case of getting already scheduled sone, re-execute the function or add 1 in a cyclic way(maximum, number of songs) until you reach not sceduled song.
add the song element to a list when picked
Save the already picked somg in an array of BOOL that its indexes are the song number. TRUE for picked song. that array will allow you to check whether the random result song already picked or not
From searchimg the net:
there are 2 basic algorithms for doing that (by Dunald Knuth)
1. Assign random number to each card and then to sort the cards in order of their random number
2. Switching cards (from up to buttom) with another card from random position in the part of the pack that has not yet been passed through
for the 1st algorith there are n! possible execution path and the execution complexity is O(nlgn) when using heap sort
for the 2nd algoruthm there are (n power n) different possible execution paths and o(n) excution complexity
According to the 1st algorithm:
1. execute random function for n times and check for recurrent number
2. check that separate executions does not give similiar numbers (=close number, sequencial number, exponential set)
3. check that there is no way (fomula) to predict on the next numbers by using previous number
for 2nd algorithm
1. compare the initial cards order with the new carrds order
2. compare few cards set and check whethear there is a connection between them (intersection, sequencial order)
for sure, there are more tests. Does anyone have something to add?
There is a famous algorithm called the Knuth Suffle algorithm which solves this problem in O(n) time.
Let X1, X2,....Xn be the N cards to be suffled.
1. Set j = N
2. Generate random number R uniformly distributed between 0 and 1.
3. Set k = j*R + 1
4. Swap(Xk,Xj)
5. j = j-1
6. If j > 1, go to step 2
Number each card 1 to 52, so after each shuffle we'll get a number sequence from the cards say {23,5,52,....total 52 terms}.
No we can calculate a the hash value of the sequence with radix=52
Example: {10.....29,2,37}
h=(52^51*10 + ...+ 52^2*29 + 52^1*2 + 52^0*37) mod 52
Now comparing h values will give an idea about randomness of sequences.
Different h value will ensure different sequences, where as same h values do NOT necessarily mean same sequence, but chances are very high.
Got this idea from "Rabin-Karp Algorithm" for string pattern search.
Note that any value for radix will work where as radix=52 will give best result for less collision (different sequence giving same h value)
I think the radix should be much higher than 52. Using only 52 possible hash values means that the probability that there is a collision in 53 runs of the program is 1.
My idea, though space consuming, was to have a 52x52 array of ints, storing in (i,j) the number of times ith card was placed in j. Then after N runs, we can see how many if (i,j) deviate from ideal value of N/52.
void Shuffle(Card cards[])
{
srand((unsigned) time(NULL));
for (int i = 0; i < 51; i++) {
int j = rand() % (52 - i);
if ( i != j ) {
swap(cards, i, j);
}
}
}
list<SONG> shuffle(const list<SONG>& li){
vector<const SONG*> vi;
list<SONG>::const_iterator cit;
for(cit=li.begin();cit!=li.end();++cit)
vi.push_back(*cit);
for(int i=0;i<vi.size();++i){
int j=(rand()%(vi.size()-i))+i;
swap(vi[i],vi[j]);
}
list<SONG> res;
for(int i=0;i<vi.size();++i)
res.push_back(*vi[i]);
return res;
}
you use rand() which may not be something they interviewer want.
We can do use time, for instance the seconds or ms to find out some random numbers.
no code necessary, the smart answer is, computers cannot truly randomize a pack of cards because it does not have the concept of "luck" factored into its mathimatical calculations.
We can shuffle in a better way as follows:
1. divide the stack of cards into two equal halvs.
2. then merge the two stack as 1 card from first stack and then second card from second stack one by one
3. Follow the above 2 steps some no. of times say 3/4/5..
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define N 52
int main()
{
int a[N + 1];
int temp;
float R;
int j = N;
int k;
struct timeval tv;
gettimeofday(&tv, NULL);
for(j = 1; j <= N; j++)
a[j] = j;
for(j = N; j > 1; j--)
{
srand((unsigned)tv.tv_usec + j);
R = (rand() / (RAND_MAX + 1.0));
k = j * R + 1;
//swap
temp = a[k];
a[k] = a[j];
a[j] = temp;
}
for(j = 1; j <= N; j++)
printf("a[j] = %d\n", a[j]);
printf("\n");
return 1;
}
public void ShuffleCards()
{
int[] Cards = new int[52];
for (int i = 0; i < 52; i++)
{
Cards[i] = i + 1;
}
for (int i = 0; i < 52; i++)
{
Console.WriteLine(Cards[i].ToString());
}
Console.WriteLine("Shuffled Cards");
int intTemp;
int intRand;
Random objRandom = new Random();
for (int i = 0; i < 52; i++)
{
intRand = objRandom.Next(52);
intTemp = Cards[i];
Cards[i] = Cards[intRand];
Cards[intRand] = intTemp;
}
for (int i = 0; i < 52; i++)
{
Console.WriteLine(Cards[i].ToString());
}
}
While shuffling, a total randomization is not preffered. We should try to simulate the shuffling as done by humans. simulate cutting at various depths. And splitting the deck in 2, then merging them taking one from each, but ocaasionally picking 2(or 3) together. This way u can carry out the shuffling for as much randomization as required, depending on the requirements of the game.
here is nice post on this question
- Jack December 10, 2014campuscoke.blogspot.in/2014/12/shuffle-card-algorithm.html