3

Hi all: I've gotten this question like four times interviewing in silicon valley. What is the correct solution?

Shuffling a deck of cards. The problem description is as follows:

You are given a deck containing n cards. While holding the deck:

  1. Take the top card off the deck and set it on the table
  2. Take the next card off the top and put it on the bottom of the deck in your hand.
  3. Continue steps 1 and 2 until all cards are on the table. This is a round.
  4. Pick up the deck from the table and repeat steps 1-3 until the deck is in the original order.

Write a program to determine how many rounds it will take to put a deck back into the original order.

What is this particular question called? Does it have a name?

3
  • 1
    A trivial, inefficient (but correct) solution is to write a program that repeatedly performs the shuffle operation until the order is restored. Feb 2, 2017 at 5:31
  • Maybe I'm not reading your problem correctly but it doesn't sound like the deck is being shuffled at all. The difference between the 'table' and 'hand' is unclear. Feb 2, 2017 at 18:51
  • 1
    @JoelCornett: It's most likely to be a very efficient solution since it takes you two minutes to write the code, and the computer a millisecond to give you the solution. If it takes longer, then you know the problem was harder.
    – gnasher729
    Feb 2, 2017 at 19:21

1 Answer 1

5

It's a Cyclic Group problem

The number of rounds needed to restore the deck to its original state is equal to the least-common-multiple (LCM) of the lengths of the rotation groups.

See Cyclic Groups.

Also, see

This answer

This post

This answer

This one too

Yeah, pretty common.

2
  • Does this have any real world applications?
    – david25272
    Feb 3, 2017 at 5:37
  • @david25272 The Collatz conjecture (AKA the 3n+1 problem) can be rephrased as "are there any cyclic groups in the space induced by the 2 Collatz operations other than (1,2,4)?" Feb 3, 2017 at 6:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.