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're in!
**

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

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

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

func rand5() -> Int {
return rand7() % 5 + 1
}

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

rand7 | rand5 |
---|---|

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.

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.

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

We'll never post on your wall or message your friends.

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

We'll never post on your wall or message your friends.

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:

func rand5() -> Int {
let roll = rand7()
return roll <= 5 ? roll : rand5()
}

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.

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

We'll never post on your wall or message your friends.

Reset editor

Powered by qualified.io

{"id":11798096,"username":"2019-04-22_15:12:43__yp)19","email":null,"date_joined":"2019-04-22T15:12:43.694551+00:00","first_name":"","last_name":"","full_name":"","short_name":"friend","is_anonymous":true,"is_on_last_question":false,"percent_done":0,"num_questions_done":0,"num_questions_remaining":46,"is_full_access":false,"is_student":false,"first_payment_date":null,"last_payment_date":null,"num_free_questions_left":3,"terms_has_agreed_to_latest":false,"preferred_content_language":"","preferred_editor_language":"","is_staff":false,"auth_providers_human_readable_list":"","num_auth_providers":0,"auth_email":""}

. . .