Interview Cake

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

ICKRand7 returns each integer with equal probability. ICKRand5 must also return each integer with equal probability.

Your first thought might be to simply take the result of ICKRand7 and take a modulus:

NSUInteger ICKRand5() { return ICKRand7() % 5 + 1; }

However, this won't give an equal probability for each possible result. We can write out each possible result from ICKRand7 (each of which is equally probable, per the problem statement) and see that some results for ICKRand5 are more likely because they are caused by more results from ICKRand7:

ICKRand7 ICKRand5
1 2
2 3
3 4
4 5
5 1
6 2
7 3

So we see that there are two ways to get 2 and 3, but only one way to get 1, 4, or 5. This makes 2 and 3 twice as likely as the others.

What about calling ICKRand7 five times, summing up the result, and then taking the modulus?

This is really close to uniform, but not quite. Since we're calling ICKRand7 five times, there are 7^5 = 16,807 possible results. That's not divisible by five, so some outcomes must be more likely than others. (If you're curious, 1 is the result 3,357 times; 2 and 5 are the result 3,360 times each; and 3 and 4 are the result 3,365 times.)

In fact, no matter how many times we run ICKRand7, we'll never get a number of outcomes that's divisible by five.

The answer takes worst-case infinite time. However, 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. But replacing your recursion with a loop avoids this.

Start your free trial!

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

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Start your free trial!

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

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

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

Note that if we weren't worried about the potential space cost (nor the potential stack overflow) of recursion, we could use an arguably-more-readable recursive approach with space cost:

NSUInteger ICKRand5() { NSUInteger result = ICKRand7(); return (result <= 5) ? result : ICKRand5(); }

This kind of math is generally outside the scope of a coding interview, but: if you know a bit of number theory you can prove that there exists no solution which is guaranteed to terminate. Hint: it follows from the fundamental theorem of arithmetic.

Start your free trial!

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

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Reset editor

Powered by qualified.io

. . .