An Encounter with a Programming Interview Problem

From the NexTag Java Development Jobs Page:

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);

Please send the result of shuffles(1002,101) along with your program and your resume to 'resume' at nextag.com.

I saw mention of this over on reddit.com. It couldn't have come at a better time. I'd just read a provocative essay on programming's mediocracy: Beating the Average makes the point that programmers are terrible at judging their own skills. We all think we're good enough, and our environment does not promote the kind of objective competition and ranking that would shake us out of our complacency.

There's a name for this: The Lake Wobegon Effect. (This is related to the Blub Paradox, of course). How do we break out of this comfort zone? One way is by solving puzzles and problems where our solution is ranked against others. With that in mind, I decided to try this puzzle over lunch today.

My code runs in sixteen milliseconds or so on JDK 1.5/Eclipse in a garden-variety PC. After googling around, I discovered that the first version of my code could have been tighter and faster. That's terrific: I actually learned something by not being the best and the brightest today.

But worries me is this: how do I know whether my code could be even better? The Blub paradox dooms me to thinking I've got the answer, when perhaps I could be even better than I am. (If my code could be better, please comment or email. I want to hear from you!)

My tip is to seek out problems like this from time to time. Don't settle for thinking up the approach in your head and considering the actual coding to be an insignificant exercise in typing. Go ahead and write clean, debugged code, preferably with a time limit to put some pressure on yourself.

(By the way, some people argue that this type of problem has little to do with Enterprise stacks and all the other cruft of a daytime gig. This is a thinly veiled excuse for not trying, and roughly equivalent to an NFL linebacker refusing to do the bench press because an actual football game is more complicated than simply pushing an iron weight over his head while lying flat on his back.)

Labels: jobs

  ¶ 2:35 PM