Comparing code
I'd be interested to see how you did it (or others who tried as well.) My code is posted below. It took about an hour, and runs in 10ms on my 1.5GHz Pentium with 512MB RAM. On my 2.4 GHz, 512 MB Pentium at home, it takes less than one millisecond. (I have a background in mathematics, so most of my hour was not spent in determining algorithms but in typing and debugging.) Is your code significantly different?

public class Deck {

public static long shuffle(int nCards, int iCut) {
Deck deck = new Deck(nCards);
deck.shuffle(iCut);
return lcm(deck.getCycles());
}

public Deck(int count) {
if (count < 1) {
throw new IllegalArgumentException("Deck must contain at least " +
"one card. You entered " + count + ".");
}
this.count = count;
cards = new int[count];
for (int i = 0 ; i < count; i++) {
cards[i] = i;
}
}

public void shuffle(int cut) {
cut = cut % count;
int[] top = new int[cut];
System.arraycopy(cards, 0, top, 0, cut);
int[] bottom = new int[count - cut];
System.arraycopy(cards, cut, bottom, 0, count - cut);
int[] updated = new int[count];
int shared = Math.min(cut, count - cut);
int different = count - shared - shared;
int[] extras = new int[different];
if (cut > count - cut) {
System.arraycopy(top, 0, extras, 0, different);
} else {
System.arraycopy(bottom, 0, extras, 0, different);
}
for (int i = 0; i < shared; i++) {
updated[count - (2 * i) - 1] = top[cut - i - 1];
updated[count - (2 * i) - 2] = bottom[count - cut - i - 1];
}
System.arraycopy(extras, 0, updated, 0, different);
cards = updated;
}

public int[] getCycles() {
int[] cycles = new int[count];
for (int i = 0; i < count; i++) {
int index = i;
int result = 1;
while (cards[index] != i) {
result++;
index = cards[index];
}
cycles[i] = result;
}
return cycles;
}

public String toString() {
StringBuffer buffer = new StringBuffer();
buffer.append("Deck [");
buffer.append(cards[0]);
for (int i = 1; i < count; i++) {
buffer.append(", ");
buffer.append(cards[i]);
}
buffer.append("]");
return buffer.toString();
}

private static long gcd(long a, long b) {
if (a == 0 && b == 0) return 1;
if (a < 0) return gcd(-a, b);
if (b < 0) return gcd(a, -b);
if (a == 0) return b;
if (b == 0) return a;
if (a == b) return a;
if (b < a) return gcd(b, a);
return gcd(a, b % a);
}

private static long lcm(long a, long b) {
return Math.abs(a * b) / gcd(a, b);
}

private static long lcm(int[] values) {
long result = 1;
for (int i = 0; i < values.length; i++) {
result = lcm(result, values[i]);
}
return result;
}

private int[] cards;
private int count;

public static void main(String[] args) {
if (args.length != 2) {
System.out.println("Usage: java Deck nCards iCut");
System.exit(1);
}
int cards = 0;
int cut = 0;
try {
cards = Integer.parseInt(args[0]);
cut = Integer.parseInt(args[1]);
} catch (NumberFormatException nfe) {
System.out.println("Arguments must be numeric.");
System.exit(2);
}
long start = System.currentTimeMillis();
long result = shuffle(cards, cut);
long time = System.currentTimeMillis() - start;
System.out.println("A perfect shuffle on " + cards + " cards, cut " + cut
+ " deep, takes " + result + " iterations to restore"
+ " the deck.");
System.out.println("Calculation performed in " + time + "ms.");
}
}

The most interesting decision was to not reduce to a canonical set of cycles. There is a cycle length listed for each card in the shuffle. This can cause no problems, since multiple copies will wash out of the least common multiple ("lcm" and "gcd" refers to the gretest common divisor.)

I would be curious to see if there are significantly different approaches to this.

Thanks,

-- Scott Sauyet

Comparing code
My version is more efficient (my home machine is a P-3 866), but the two approaches are fairly equivalent.

Comparing code
Oh, just find the Next Tag Question and come to here.
The program can be further optimized, basically you don't have to re-calculate the cycle number in a shuffle loop. replace the code within the loop with this will be much faster for a bigger number say "A perfect shuffle on 100001 cards, cut 101 deep"
==========
if (cycles[i] != 0) { //calculated already
continue;
}
int index = i;
int result = 1;
while (cards[index] != i) {
result++;
index = cards[index];
}
cycles[i] = result;
//reset index
index = i;
//Set the Loop's cycle's result.
while (cards[index] != i) {
cycles[index] = result;
index = cards[index];
}
================

Comparing code
And there should be a math way to calculate how many shuffle loops it has and how big the groups are instead of using the brutal computing force. But then, it becomes a total math problem instead of a programming problem, which makes it a not so good interview question for Java Developers.

Comparing code
I am confused here.

for:
nCards=1002
iCut=101

I ran the code on this page (class Deck) and it computes the answer to be:
5812104600

whereas, my code computes it as:
152760

my code follows:

import java.util.*;

public class Shuffles {

long shuffles(int nc, int ic) {
int vs[] = new int[nc];
int tvs[] = new int[nc];

int i, j, k;
for(i=0;i

why this problem
Why is this problem related to an e-commerce application? It isn't. Good programmers can program anything, and this problem is designed to find good programmers.

I made this problem up about 20 years ago when a friend asked me something about shuffling cards at a time when I was looking for a problem to screen programmers. I have been using this problem to screen programmers at various companies ever since. Good programming often requires making a first pass design, and then stepping back and rethinking the problem to find the best solution. Very few simple problems require this, but the card shuffling problem is one. I assume everyone knows the little math required. What is really needed is the ability to visualize what is happening, and make an insight from that. And this kind of thinking is what programming is about.

I would like to continue using this problem to screen programmers, but unfortunately this page shows up in Google. I would greatly appreciate it if a "noindex" meta-tag were added to this page, as in:

Tried it in Haskell
If you want to see a tiny solution in the Haskell programming language, I have posted one here:

http://blog.moertel.com/articles/2006/03/23/the-perfect-shuffles-puzzle-solved-in-haskell

Cheers,
Tom

another, quite elegant solution
This one's nice:
http://blogsummaries.blogspot.com/