Programming Technical Interview Questions
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
Game Programming, General Programming Questions, Mathematical Questions

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.

By Sundar on 07.12.07 5:52 am | Permalink

RSS feed for comments on this post.


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