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

- Jack December 10, 2014 | Flag Reply
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.

- SP July 16, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How do we define this random function???

- nikhil February 15, 2006 | Flag Reply
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;

- Susan April 22, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

real random numbers, rand() is pseudo random

- J.C. March 02, 2007 | Flag
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?

- cd April 30, 2006 | Flag Reply
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.

- Kevin May 12, 2006 | Flag Reply
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

- Eila June 04, 2006 | Flag Reply
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

- Eila June 13, 2006 | Flag Reply
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?

- Eila June 13, 2006 | Flag Reply
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

- Ashwin August 06, 2006 | Flag Reply
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)

- kg January 16, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Matchless February 21, 2007 | Flag
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);
}
}
}

- Anonymous January 26, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better algorithm than others....

- saurabh saxena(vit) February 09, 2012 | Flag
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])
}

- Swati January 26, 2007 | Flag Reply
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.

- shawshank January 26, 2007 | Flag Reply
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;
}

- zzz100 February 26, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- J.C. March 02, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jack November 14, 2007 | Flag
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.

- Anonymous March 05, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Jack November 14, 2007 | Flag
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..

- Anonymous May 11, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vas November 14, 2007 | Flag
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;
}

- Sidharth August 07, 2007 | Flag Reply
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.

- Sidharth August 07, 2007 | Flag Reply
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());
}
}

- AK November 16, 2007 | Flag Reply
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;

}

- Jayanth Holla April 16, 2008 | Flag Reply
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.

- ankit April 21, 2008 | Flag Reply
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] );

    }

- Anonymous October 27, 2010 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More