Find the "Best" item from this list.

Question

I recently asked this question in one of my telephone interviews.

"There is a list of elements, and you should find the" best "element from the list. The elements are comparable to each other, but the comparison is not transitional . For example. If A> B and B> C, then A should not be greater than C.

You should return the best item as an answer, which is better than any other item in the list. It is possible that there is no such element. In this case, return null. "

My decision:

Attempt 1:

The simple solution is O (n ^ 2) . Comparison of each element with another element.

The interviewer was not satisfied.

Attempt 2:

Start comparing the first item with the second item and on. For any element "E", if A> E, mark E (maybe using another array / list / etc.) And do not consider E for further comparison. This is because there is at least one element that is better than E, so E is definitely not the answer.

The complexity is still O (n ^ 2) with some improvement over the previous attempt.

He was still not satisfied. Can anyone come up with some better solution?

Answer 1

Sure. You have N items. Compare the first two. One of them is “worse” than the other. Drop it. Compare the “best” of the two with the next item. Continue this first pass through the list until only one item remains. This step is O (N).

One element that survived the first pass should now be compared with each element from the original list, except for those with which it was already compared. If it "loses" even once, you return that there is no "better" element. If this “wins” each comparison at this point, you return this item. This step is also O (N).

This algorithm is O (N + N) = O (N) in the worst case and O (N + 0) == O (N) in the best case. We can also prove that this is the best possible difficulty, because checking the solution is also O (N), and it might not be harder to get a solution than checking it.