Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

Archive for October 6th, 2006

Shuffling – Shuffle a deck of cards – Knuth Shuffle

Posted by tekpool on October 6, 2006

Q: Shuffling – Shuffle a deck of cards – Knuth Shuffle

Shuffling is a process where the order of elements in a data set is randomized to provide an element of chance. One of the most common applications of this is to shuffle a deck of cards.

Mathematically, the shuffling problem, is basically a problem of computing a random permutation of N objects, since shuffling a deck of cards is basically subjecting a deck of cards to a random permutation.

Card shuffling algorithms are used in computer games, casinos, etc. Before we delve into the algorithms, let’s look into what are really trying to solve here. These are the kind of things that an interviewer will be looking into apart from the algorithm itself. The choice of algorithm and data structure chosen for this, needs to be based on where, who and how this is going to be used.

As I just mentioned, this is something used in the gaming industry (Computers, Video Games, Casinos etc…). This purpose of this algorithm is to introduce an element of chance into the data set (deck of cards) and make it impossible for the user to find a pattern and predict the occurrence of un-dealt cards. The size of the data set is small (52 elements), and so the complexity of the algorithm is usually not of high concern. A O(n^2), v/s an O(n lg n) v/s an O(n) for example would be a few milliseconds. Of course, a real bad implementation with O(n^n) would certainly be of concern, although I guess it is going to be difficult to come up with a O(n^n) algorithm in the first place.

It is important to look at problems with this angle. Sometimes, it takes too much time and effort to come up with a faster algorithm, and it the end it could end up providing very less value. The keyword here cost/benefit ratio.

OK, so we’ve learnt that the complexity of the algorithm we choose is not of high priority. What else? Since this is something that will be used in a casino, we need to eliminate the element of predictability. We don’t want people to be able to predict what the next card in the deck might be, even with a low probability.

The problem itself involves randomization, and we are definitely going to deal with random numbers. Some random numbers, have bias on some of bits in a number, e,g rand() has a bias on the upper bits in a number. We want to be avoiding such generators.

There are few basic well known solutions to this problem, the first of this is an O(n lg n) algorithm. I won’t be writing code for this, but I will go over the algorithm. The solution involves simple assigning a random number to each card, and sorting them in order of their assigned number. There is a chance that two of the cards are assigned the same number. This check can be checked each time you assign a number, or even better this can be checked when you sort the cards and redo it all over again, or redo the same problem on the smaller set usually 2 cards, if you have got more than 2 cards, actually even 2 cards, then you’ve chosen a bad random number generator.

The more elegant and faster of the two algorithms is also known as the Knuth Shuffle, popularized by Donald Knuth, in his book , The Art of Computer Programming. The algorithm was originally published by R.A. Fisher and F. Yates [Statitiscal Tables (London 1938, Example 12], in ordinary language, and by R. Durstenfeld [CACM 7 (1964), 420] in computer language. Here’s the algorithm in ordinary language.

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.

For the mathematically oriented:

Traditional shuffling procedures turn out to be miserable inadequate. Reportedly, expert bridge players make use of this fact when deciding whether or not to finesse. At least seven “riffle shuffles” of a 52-card deck are needed to reach a distribution within 10% of uniform, and 14 random riffles are guaranteed to do so. [Aldous and Diaconis, AMM 93 (1986), 333-348] [Knuth, The Art of Computer Programming, Random Sampling and Shuffling]

Advertisements

Posted in Algorithms, C++, Data Structures, General, Microsoft, Progamming Languages | 10 Comments »

Prime Numbers: Finding the first N Primes – Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

Posted by tekpool on October 6, 2006

Q: Finding the first N Primes
Part 4 Sieve of Eratosthenes and Erdos Prime Number Theorm

We have been using regular Computer Science procedures for improving efficiency here. It’s time to borrow some good old Math theorms now. The first of the techniques, that I am going to use is the Sieve of Eratosthenes

This is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number you wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2 . It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3 . It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number).

Continue until you have crossed out all numbers divisible by sqrt(n), The numbers remaining are prime.

This idea can be used easily to find all primes below a given number. But, how do you use this to find the first N primes. Here’s a quick idea, Use Erdos Prime Number Theorm. You use this to find a Cap, which is the number until which you need to check to get N primes.

float FindPrimeCap(int x) 
{ 
    float flX = (float) x; 
    float flCap = 1.0f; 
    for(float f=2.0f; flCap

FindPrimeCap uses Erdos Prime Number Theorm. Since this is asymptotic, it is not accurate enough for small numbers.
However, timing this code showed that this method was faster than all of the previous method we discussed.
In fact more prime were found in lesser time, using this method compared to the previous ones.

In a later post, We will analye the performance of all the methods we have discussed so far

Posted in Algorithms, C++, General, Microsoft, Number Theory, Progamming Languages | 2 Comments »