Rand7 from Rand5 Draws
Updated
Problem statement
Build a uniform random integer from 1 through 7 using a stream of independent, uniform Rand5 draws, each from 1 through 5. Use rejection sampling: throw away values you cannot use.
Take the draws in consecutive pairs (a,b) that do not overlap. For each pair, compute v=5*(a-1)+(b-1). If v is from 21 through 24, reject the pair. Otherwise return 1+v%7 right away. Ignore a last draw that has no partner. Return -1 if no complete pair is accepted.
The stream is given up front, so the answer is the same every time. If the draws are independent and uniform, each of the 21 accepted pair values is equally likely, and each output comes from exactly three of them.
Function
rand7FromRand5Draws(draws: int[]) → intExamples
Example 1
draws = [5,5,2,3]return = 1The first pair is 5 and 5, so v is 24, and the pair is rejected. The second pair is 2 and 3, so v is 7, and 1+v%7 gives 1.
Constraints
0 <= draws.length <= 20000.1 <= draws[i] <= 5.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Integer BreakAmazon · ONSITE INTERVIEW
- Knight Probability in ChessboardGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Path Between Two Nodes of a Fibonacci TreeDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
- Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
- Calculate a Token-List ExpressionCollege Vine · ONSITE INTERVIEW
- Maximize the Even-Odd Index Product GapInfosys · ONSITE INTERVIEWInfosys interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)