Shuffle and Reset an Array
Updated
Problem statement
Construct a shuffler from original, an array of n distinct integers. Store an independent copy of that original order, then process operations.
Each operation returns one full array snapshot:
[0]is RESET. Restore the original order and return a new copy of it.[1, j_(n-1), j_(n-2), ..., j_1]is SHUFFLE. Start a new working copy of the stored original. Fori = n-1, n-2, ..., 1, swap positionsiandj_i. Return the resulting array.
The first field is the operation tag. A SHUFFLE row contains exactly n fields, with 0 <= j_i <= i. In a row called operation, the draw for step i is operation[n-i]. When n = 1, SHUFFLE is simply [1] and has no draws.
The input records random choices so execution can be checked exactly. Read these choices rather than calling another random generator. Each field records one draw; reading that field again does not draw another number. A fixed legal record may contain repeated or all-zero choices.
In the random model, draw each j_i independently and uniformly from 0 through i, inclusive. Independent choice vectors across SHUFFLE calls also give independent shuffles. Under this model, every permutation of the distinct original values is equally likely.
In this practice version, every SHUFFLE starts from the stored original order, including consecutive SHUFFLE requests. RESET consumes no random choices. Return snapshots in operation order. Construction alone produces no snapshot, so no operations means an empty result.
Do not change original, any operation row or an earlier result. Every returned snapshot must be a separate array, independent of the inputs and other snapshots. Each function call constructs a fresh shuffler.
Discussion follow-up
Prove that independent uniform choices make all n! permutations equally likely. Showing only that each value has equal probability at each position is not enough. Explain the time and space costs of Fisher-Yates, including the copies required by this interface.
Function
shuffleAndReset(original: int[], operations: int[][]) → int[][]Examples
Example 1
original = [10,20,30]operations = [[1,0,0],[0],[1,2,1]]return = [[20,30,10],[10,20,30],[10,20,30]]The first SHUFFLE swaps positions 2 and 0, giving [30,20,10], then positions 1 and 0, giving [20,30,10]. RESET returns [10,20,30]. The last SHUFFLE uses self-swaps at both steps, so it also returns the original order.
Example 2
original = [1,2,3,4]operations = [[1,0,0,0],[1,3,2,1],[0]]return = [[2,3,4,1],[1,2,3,4],[1,2,3,4]]The all-zero choices give [1,2,3,4] → [4,2,3,1] → [3,2,4,1] → [2,3,4,1]. The next SHUFFLE starts again from the stored original and uses only self-swaps, returning [1,2,3,4]. RESET returns another independent copy of that original order.
Example 3
original = [-5]operations = [[1],[0],[1]]return = [[-5],[-5],[-5]]With one value, SHUFFLE has no swaps and no recorded draws. Each operation returns a separate snapshot containing -5.
Constraints
1 <= original.length <= 50.- Every integer in
originalis between-10^6and10^6, inclusive. - All values in
originalare distinct. 0 <= operations.length <= 12.- Each operation row contains between 1 and 50 integers, inclusive.
- Every integer in
operationsis between 0 and 49, inclusive. - A RESET row is exactly
[0]. A SHUFFLE row starts with 1, has exactlyn = original.lengthfields, and recordsj_iat fieldn-iwith0 <= j_i <= ifori = n-1, ..., 1.
More Akuna Capital Phone Screen questions
- Match Orders by Price and Arrival TimeOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Biased Coin: Probability of Exactly h HeadsPHONE SCREEN · Seen Nov 2026
- Positive Nth Root with Gradient DescentPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Sep 2026
- Maximum Value in a Binary TreePHONE SCREEN · Seen Sep 2026
- Tiered Expiring Item StorePHONE SCREEN · Seen Aug 2026
- Statistics for the Latest K ValuesPHONE SCREEN · Seen Nov 2025
- Remove Duplicates While Preserving OrderPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2025
- Sliding Window MaximumPHONE SCREEN · Seen Oct 2025
- Evaluate a PolynomialPHONE SCREEN · Seen Oct 2025
Similar questions at other companies
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Evenly Schedule Vehicle InspectionsAmazon · PHONE SCREEN
- Implement Cross-Entropy LossOpenAI · PHONE SCREENOpenAI interview questions
- Cumulative No-Intercept Regression BetasCitadel · PHONE SCREENCitadel interview questions
- Add Signed Character ArraysByteDance · PHONE SCREENByteDance interview questions
- Automation Pipeline, Part 2: Stage WorkersPlaid · PHONE SCREENPlaid interview questions
- Reservoir Sampling with Recorded DrawsGoogle · PHONE SCREENGoogle interview questions
- Attention With Absolute Index BiasNVIDIA · PHONE SCREENNVIDIA interview questions
- K-Means Delivery ZonesDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Token Bucket Request DecisionsDatadog · PHONE SCREENDatadog interview questions
Interview reports that mention this question
Akuna Capital interview experiences
- Akuna Capital Quant Trader and QR Interviews: 5 Experiences
- Akuna Capital JQR CodePair Rounds: 8 Experiences (Part 6 of 6)
- Akuna Capital QR Probability Phones: 14 Experiences (Part 5 of 6)
- Akuna Capital QR-ML Interviews: 11 Experiences (Part 4 of 6)
- Akuna Capital QR Coding Interviews: 17 Experiences (Part 2 of 6)