## Amazon Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
2
of 2 vote

here is nice post on this question
campuscoke.blogspot.in/2014/12/shuffle-card-algorithm.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

for i <- 1 to n
swap ( a [i], a[random(i,n)]
Can be proved that prdouces a uniform random permutation.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How do we define this random function???

Comment hidden because of low score. Click to expand.
0
of 0 vote

Quite 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;

Comment hidden because of low score. Click to expand.
0

real random numbers, rand() is pseudo random

Comment hidden because of low score. Click to expand.
0
of 0 vote

nikhil: random(i, n) would just generate a random number between i and n.

But how to prove it is "uniform" random?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using frontback split and then merge the two lists such that the elements in the two lists appear in the final list alternatively. You can repeat this for [n/4]+1 times.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}
}

Comment hidden because of low score. Click to expand.
0

Better algorithm than others....

Comment hidden because of low score. Click to expand.
0
of 0 vote

for (i = 0... N-1) {
int n = rand(N-i);
swap(deck[i], deck[n+i])
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

to shuffle a card of say spade A,1,2,3,...,10,J,Q,K,
represent them as values from 1 to 13 and sort them using insertion sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

The compiler and library people are good at this sort of thing. Why second guess them? Trying to write your own rand() function sounds like an anti-pattern.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Sorry, I don't consider that the smart answer...

There are plenty of card games that work quite well despite not being truly random in the Mathematical sense.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

Comment hidden because of low score. Click to expand.
0

this is not seem to work and body can say after the iteration what card has arranged in what position... So not allowed

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, Forgot to mention. The above program is according to knuth's algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Shuffle()
{

vector<int> vi;
for(int i = 0; i < 10; i++)
vi.push_back(i);

random_shuffle(vi.begin(),vi.end());

vector<int>::iterator it;
for(it=vi.begin(); it != vi.end(); ++it)
cout << *it << ",";
cout << endl;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````for( i=51;i>=0;i-- )
{
int r = rand()%(i+1);
swap( &card[i] , &card[r] );

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.