Minimum And Maximum
July 4, 2014
We have today a two-part interview question:
First, write a program that takes an array of integers and returns the minimum and maximum elements of the array. Use as few comparisons as possible.
Second, write a program that takes an array of integers and returns the second minimum and maximum elements of the array; that is, the second-smallest element and the second-largest element. Again, use as few comparisons as possible.
Your task is to write the two programs described above, and state the number of comparisons each makes in the general case; be sure they are proof against malicious input. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
I see a different way to read “second-smallest (second-largest) element”: the smallest (largest) value after ignoring all occurrences of the actually smallest (largest). A catch is that one must not ignore the largest values when looking for the second-smallest, and vice versa (the first example below), and there must be occurrences of at least two values (the last example).
>>> xs = {3,1,3,1,3} ; min(xs - {min(xs)}), max(xs - {max(xs)}) (3, 1) >>> xs = {3,1,4,1,3} ; min(xs - {min(xs)}), max(xs - {max(xs)}) (3, 3) >>> xs = {3,1,4,1,5} ; min(xs - {min(xs)}), max(xs - {max(xs)}) (3, 4) >>> xs = {3,3,3,3,3} ; min(xs - {min(xs)}), max(xs - {max(xs)}) Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: min() arg is an empty sequenceImplementation as a linear scan of the sequence should be possible but more tedious.