FastPrepShuffle With Given Random Draws
Problems/Shuffle With Given Random Draws

Shuffle With Given Random Draws

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a review of a Microsoft software engineering internship. The review describes a shuffle function that must make every ordering of an integer array equally likely on each call, and gives no rules beyond that. The round is not named. The review describes a day of three interviews.

A random answer cannot be checked, so here the randomness is passed in. You get nums (up to 3000 values) and one draw per position (whole numbers from 0 to 10^9). The k-th draw picks the next element as the draw modulo the number of elements left, counted among the unchosen elements in their original order. With uniform draws every ordering is equally likely. The editorial also covers the in-place Fisher-Yates shuffle, which uses the draws differently and is not what is tested.

Our version is about 60% the same as the reported question.

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^9 and 0 <= 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 Explore and Student SWE: 12 Experiences (Part 6 of 6)

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)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] shuffleWithDraws(int[] nums, int[] draws) {
        // Write your code here.
    }
}
Checking account…