Shuffle an Array and Restore Its Original Order

# Shuffle an Array and Restore Its Original Order Implement a `Solution` object initialized with an integer array of distinct values: - `Solution(nums)`: initialize the object with the array. - `reset() -> list[int]`: restore the original configuration and return it. - `shuffle() -> list[int]`: return a random permutation of the original elements, with every permutation equally likely. The original configuration is the order supplied at construction. Preserve it across any sequence of `shuffle` and `reset` calls. A shuffle may return the original order or repeat an earlier result. ### Examples For `Solution([2, 5, 8])`, one possible call sequence is: ```text shuffle() -> [8, 2, 5] reset() -> [2, 5, 8] shuffle() -> [5, 8, 2] ``` The shuffled arrays are illustrative, not fixed expected outputs. Every one of the six permutations must have probability `1/6` on each shuffle. For `Solution([-3])`, both methods return `[-3]`. ### Constraints and assumptions - `1 <= len(nums) <= 50`. - `-1000000 <= nums[i] <= 1000000`. - All input values are unique. - At most `10000` calls in total are made to `reset` and `shuffle`. - The object must not mutate the caller's input array. Returned arrays must not expose mutable internal state that could change future resets or shuffles. - No random seed, fixed transcript, or particular random API is specified. State the assumptions behind the probability argument; the reference assumes independent, unbiased integer draws over a requested finite range. ### What a Strong Answer Covers - Preservation of every element exactly once in each result. - Equal probability for every permutation, including the original order. - Restoration of the original order after repeated calls and protection against array aliasing. - Initialization, reset, and shuffle time and storage costs. ### Follow-up Questions - How would you assess the shuffle distribution using a finite sample of results, and what conclusions could that sample support?