Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

Just No more free questions left!

Upgrade Now

I figured out how to get rich: online poker.

I suspect the online poker game I'm playing shuffles cards by doing a single riffle.

To prove this, let's write a function to tell us if a full deck of cards shuffled_deck is a single riffle of two other halves half1 and half2.

We'll represent a stack of cards as a list of integers in the range 1..52 (since there are 52 distinct cards in a deck).

Why do I care? A single riffle is not a completely random shuffle. If I'm right, I can make more informed bets and get rich and finally prove to my ex that I am not a "loser with an unhealthy cake obsession" (even though it's too late now because she let me go and she's never getting me back).

Watch out for index out of bounds errors! Will your function ever try to grab the 0th item from an empty list, or the nth item from a list with n elements (where the last index would be n-1)?

We can do this in time and additional space.

Did you come up with a recursive solution? Keep in mind that you may be incurring a hidden space cost (probably ) in the call stack! You can avoid this using an iterative approach.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

You must log in with one click to view the rest.

Once you're logged in, you'll get free full access to this and 4 other questions.

time and additional space.

Becky if you're reading this I didn't really mean what I said in the problem statement. It's just that things have been hard lately and anyway if you'll just give me another chance I promise it won't be like last time. I'm a wreck without you. Like a collapsed soufflé. Please Becky.

  1. This assumes shuffled_deck contains all 52 cards. What if we can't trust this (e.g. some cards are being secretly removed by the shuffle)?
  2. This assumes each number in shuffled_deck is unique. How can we adapt this to rifling lists of random integers with potential repeats?
  3. Our solution returns True if you just cut the deck—take one half and put it on top of the other. While that technically meets the definition of a riffle, what if you wanted to ensure that some mixing of the two halves occurred?

If you read the whole breakdown section, you might have noticed that we started with a recursive function that looked simple but turned out to cost time and space because each recursive step created its own new "slice" of the input list. If you missed that part, go back and take a look.

Be careful of the hidden time and space costs of list slicing! Consider tracking list indices "by hand" instead (as we do in our final solution).

What's next?

Powered by

. . .