Shuffle With Given Random Draws
Updated
Problem statement
A shuffle returns the elements of an array in a random order, where every ordering is equally likely. A random answer cannot be checked, so here the random numbers are given to you: draws[k] is the k-th random number the shuffle uses.
Build the result one element at a time. Keep the elements not chosen yet in their original order. For k = 0, 1, ..., n - 1, with left = n - k elements remaining, take the remaining element at index draws[k] % left (0-based), append it to the result, and remove it from the remaining elements. Return the result.
Equal values are separate elements. If every draws[k] were a uniform random number, every ordering would come out with the same probability.
Function
shuffleWithDraws(nums: int[], draws: int[]) → int[]Examples
Example 1
nums = [10,20,30,40]draws = [6,0,5,9]return = [30,10,40,20]Draw 6: 4 elements are left, 6 % 4 = 2, so take index 2 of [10, 20, 30, 40], which is 30. Draw 0: 0 % 3 = 0 takes 10 from [10, 20, 40]. Draw 5: 5 % 2 = 1 takes 40 from [20, 40]. Draw 9: 9 % 1 = 0 takes the last element, 20. The result is [30, 10, 40, 20].
Example 2
nums = [7,7,3]draws = [1,1,0]return = [7,3,7]Draw 1: 1 % 3 = 1 takes the second 7 from [7, 7, 3]. Draw 1: 1 % 2 = 1 takes 3 from [7, 3]. Draw 0 takes the remaining 7. Equal values are still separate elements.
Constraints
1 <= n == nums.length == draws.length <= 3000-10^9 <= nums[i] <= 10^9and0 <= draws[k] <= 10^9
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Accumulate Numeric Value ObjectsSquarepoint Capital · ONSITE INTERVIEWSquarepoint Capital interview questions
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Customer Bootstrap APIDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Round-Robin Iterator over IteratorsBridge · ONSITE INTERVIEWBridge interview questions
- Design Hit CounterNutanix · ONSITE INTERVIEWNutanix interview questions
- Design Browser HistoryBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Random Pick with Weight Using Recorded DrawsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Top K Largest Values from a StreamThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Maximize the Even-Odd Index Product GapInfosys · ONSITE INTERVIEWInfosys interview questions
Interview reports that mention this question
Microsoft interview experiences
- Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
- Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
- Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
- Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
- Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)