Related link: http://www.nextag.com/serv/main/about/jobs/java.jsp
A friend sent me the following programming problem, which comes from the NextTag website.
Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:
static long shuffles(int nCards,int iCut);
On their site, they’re using this as a screening function for software developers. As they put it:
We are looking for Java developers to help build our e-commerce web application. Try out this Programming Problem and see if you can make it run within a few minutes or less.
I’m not certain I understand why this is related to an e-commerce application, but it’s an interesting challenge. Or, at least, I thought it was (Call me a dang-fool-coder, but sometimes I just like to hack away at problems).
After 4 hours, I’ve got it down to 31 milliseconds on the machine I’m using. I think that’s good enough.
The fun part, for me, was realizing just how computationally intensive this problem really is, and, consequently, how bad my initial guess at how to do solve it was. At the end of the day, a few cute tricks and a little bit of thought about prime factorizations solved the problem in ways that objects named “deck” and “shuffler” didn’t.
The hard question: is there a closed form solution for this problem?