Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

You only have free questions left.

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You have a method rand5 that generates a random integer from 1 to 5. Use it to write a method rand7 that generates a random integer from 1 to 7.

rand5 returns each integer with equal probability. rand7 must also return each integer with equal probability.

Simply running rand5 twice, adding the results, and taking a modulus won't give us an equal probability for each possible result.

Not convinced? Count the number of ways to get each possible result from 1..7.

Your method will have worst-case infinite runtime, because sometimes it will need to "try again."

However, at each "try" you only need to make two calls to rand5. If you're making 3 calls, you can do better.

We can get away with worst-case space. Does your answer have a non-constant space cost? If you're using recursion (and your language doesn't have tail-call optimization), you're potentially incurring a worst-case infinite space cost in the call stack.

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.

Worst-case time (we might keep re-rolling forever) and space.

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.

What's next?

Powered by qualified.io

. . .