Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

You only have free questions left (including this one).

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 function rand5 that generates a random integer from 1 to 5. Use it to write a function 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 function 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.

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

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

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Reset editor

Powered by qualified.io

. . .