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?

closed as primarily opinion-based by gnat, Andres F., user22815, Bart van Ingen Schenau, amon Feb 3 '17 at 12:11

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    A trivial, inefficient (but correct) solution is to write a program that repeatedly performs the shuffle operation until the order is restored. – Joel Cornett Feb 2 '17 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. – whatsisname Feb 2 '17 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 '17 at 19:21
6

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.

  • Does this have any real world applications? – david25272 Feb 3 '17 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)?" – Joel Cornett Feb 3 '17 at 6:59

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