It is an interesting question from an Interview, I failed it.

An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ (random order).

We have a comparator $C$, but it has a probability $p$ to return correct results.

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $[A_{i_1}, A_{i_2}, ..., A_{i_n}]$ (It could be wrong).

Now given a number $m$ ($m < n$), the question is as follows:

What is Expectation of size $S$ of Intersection between $\{A_1, A_2, ..., A_m\}$ and $\{A_{i_1}, A_{i_2}, ..., A_{i_n}\},$ in other words, what is $E[S]$?

Any relationship among $m$, $n$ and $p$ ?

If we use different sorting algorithm, how will $E[S]$ change ?

My idea is as follows:

When $m=n$, $E[S] = n$, surely. When $m=n-1$, $E[S] = n-1+P(A_n$ in $A_{i_n})$. I don't know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.

  • 1
    $\begingroup$ Since [A1,...,An] are in random order, I think that E[S] does not depend on p, e.g. P(A1=Ai1) = 1/n. See my answer + comments here: stackoverflow.com/questions/29876160/… $\endgroup$ – coproc Apr 27 '15 at 9:24
  • $\begingroup$ Side reading on that subject: Beyond Efficiency, CACM. $\endgroup$ – lhf May 20 '16 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.