Generate Unique Random Numbers
Learn this problem
GoogleINTERNONSITE INTERVIEWProblem statement
Build the inclusive array [a, a + 1, ..., b], shuffle it in place with the Fisher-Yates algorithm, and return its first n values. The returned values must therefore be distinct and each must lie between a and b, inclusive.
To make the judged output reproducible, use this exact pseudorandom-number rule. Let state = seed. For every Fisher-Yates iteration from i = b - a down to 1, first set state = (1103515245 * state + 12345) mod 2^31, then set j = state mod (i + 1) and swap positions i and j. Return the first n shuffled values.
The running time must be deterministic with respect to the size of the inclusive range.
Function
generateUniqueNumbers(a: int, b: int, n: int, seed: int) → int[]Examples
Example 1
a = 1b = 5n = 3seed = 7return = [1,3,4]The seeded Fisher-Yates swaps produce the shuffled prefix [1, 3, 4]. All three values are distinct and lie in the inclusive range.
Example 2
a = 10b = 13n = 4seed = 0return = [10,12,13,11]Because n equals the range size, the full seeded permutation is returned.
Example 3
a = -2b = 2n = 1seed = 42return = [-1]Only the first element of the seeded permutation is requested.
Constraints
-10^6 <= a <= b <= 10^61 <= b - a + 1 <= 2000001 <= n <= b - a + 10 <= seed <= 2147483647