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.

About these ads

Pages: 1 2

One Response to “Minimum And Maximum”

  1. Jussi Piitulainen said

    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 sequence
    

    Implementation as a linear scan of the sequence should be possible but more tedious.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: