1}. Write a random sampler to sample from this multi-dimensional space. Specifically, each time when the sampler is invoked, the sampler returns a tuple of length. 1}. In additional, the new sample must never collide with any sample generated in the history, until the whole space is exhausted.Cuber QQ had just learned usages of random library. He thought of this problem as a piece of cake, and wrote the following code. . However, the interviewer looked at this code and quickly pointed out that he did not think of the cases where the samples could collide. That is, when you call texttt{sample} repeated, it will possibly yield duplicated samples. To convince Cuber QQ of this flaw, he tested Cuber QQ's program on a test data, which calls texttt{sample} by. m times. The tester will count the number of violations of the "never collide" principle.m calls of sample return a list of arrays of length
Cuber QQ has recently been interviewed for a job position. The interviewer challenged him with the following problem.
Given a multi-dimensional space with
n
n independent dimensions, the
i
i-th (
1 le i le n
1≤i≤n) of which has
a_i
a
i
possible values
{0,1,ldots,a_i-1}
{0,1,…,a
i
−1}. Write a random sampler to sample from this multi-dimensional space. Specifically, each time when the sampler is invoked, the sampler returns a tuple of length
n
n,
(x_1,x_2,ldots,x_n)
(x
1
,x
2
,…,x
n
), where
x_i in {0,1,ldots,a_i-1}
x
i
∈{0,1,…,a
i
−1}. In additional, the new sample must never collide with any sample generated in the history, until the whole space is exhausted.
Cuber QQ had just learned usages of random library. He thought of this problem as a piece of cake, and wrote the following code. (It's a pseudo-code, in Python style.)
def sample(a: list[int]) -> list[int]:
return [randint(0, a[i] - 1) for i in range(len(a))]
However, the interviewer looked at this code and quickly pointed out that he did not think of the cases where the samples could collide. That is, when you call texttt{sample(a)} repeated, it will possibly yield duplicated samples. To convince Cuber QQ of this flaw, he tested Cuber QQ's program on a test data, which calls texttt{sample} by
m
m times. The tester will count the number of violations of the "never collide" principle.
Specifically, the
m
m calls of sample return a list of arrays of length
m
m, where the
i
i-th element is denoted as
o_{i,1}, o_{i,2}, ldots, o_{i,n}
o
i,1
,o
i,2
,…,o
i,n
(
1 le i le m
1≤i≤m,
0 le o_{i,j} < a_j
0≤o
i,j
标签： HBC243980BobinWonderlandHacking Interview Solution题解
