This site features a collection of common technical interview questions gathered by a group of programmers who have been through, and given, lots of technical interviews. There is an emphasis on C++ and game programming technical interviews, but most of the questions are relevant to any technical interview.
The Shuffle

Come up with an algorithm to shuffle a deck of cards. Discuss how uniform a distribution your solution would achieve, and how you could potentially improve upon it.


1 Comment so far
Leave a comment

Let X1, X2…. XN (In this case N=52) be the set of N numbers to be shuffled.

1. Set j to N
2. Generate a random number R. (uniformly distributed between 0 and 1)
3. Set k to (jR+1). k is now a random integer, between 1 and j.
4. Exchange Xk and Xj
5. Decrease j by 1.
6. If j > 1, return to step 2.

void KnuthShuffle(int* pArr)
{
int rand;
for(int i=51;i>=0;i–)
{
rand=GenRand(0,i);
swap(pArr[i], pArr[rand]);
}
}

GenRand(int min, int max) generates a random number between min and max.



Leave a comment
If you are including code in your comment, place it within a <div class='code'></div> tag for better formatting.


Do you have a technical interview question you would like to submit? Some tips you would like to pass on? Just want to say hi? Feel free to contact us