CareerCup

What do you mean by: O(3n/2) scales worse than O(n)?

Pretty good answer.
It is an actual function and it returns two values.

- What happens when an empty array is passed? []
- How does the caller know which value is max and which is min in the returned Tuple? Can you think of a way to make it more clear?
- How would you do this if it input was an array of floats?

You can use fewer compares than comparing each value twice (once to max and once to min). Technically, I think the function is O(n) but the *comparisons* can be O(3n/2). This is because Big O simplifies (3n/2) down to just n for conversation purposes.

There is also a better way than using a MAX_INT/MIN_INT constants... You'll need to find it to solve for the "make a function that works for floats".

variables but I'm not a fan of those.
@- ninhnnsoc I meant there is an anwer above that clains 3n/2 is better than n.

@trophygeek
Answering the questions:
I return a Tuple<int, int> as it is a coding interview question and as simple as possible is better.
To make it more clear I would document it like i did bellow.

But another ways could be use "out" could be create a struct or class that return both values but it is a bit of an overkill for a simple function in an interview.

I knew about doing only one comparison but I fixed so I I though about it and I said what the heck it was late and I was tired.

Implementing this with an array of floats is out of scope but I did here is an implementation for anything that can be compared.



In terms of the 3n/2 coparissons theme:
You are right about the 3n/2 comparisons worst/average/best cases remain the same on YOUR solution but in the linear solution has a worst case is 2n, best case 1n and in average it is 3n/2 which is a trade off depending any statistical hint of the stream.

I was looking at the first solution by @Skur that did go sort of twice and did all kind of extra operations which they did not make any sense to me.


----
Here is the fix for the question that you had above:

/// <summary>
        /// Finds the minimun and maximun of an array if the array is empty it will return null.
        /// </summary>
        /// <param name="A">
        /// Array with the <paramref name="T"/></param>
        /// <typeparam name="T">IComparable type</typeparam>
        /// <returns>
        /// <see cref="Tuple<T, T>"/> where Item1 is the minimun and Item2 is the maximun values of the array.
        /// If the array is empty the it will return null
        /// </returns>
        public static Tuple<T, T> FindMinimunMax<T>(T[] A) 
            where T:IComparable
        {
            if (A == null || A.Length == 0)
                return null;

            T max = A[0];
            T min = A[0];

            foreach (T a in A)
            {
                if (max.CompareTo(a) > 0)
                {
                    max = a;
                }
                else if(min.CompareTo(a) < 0)
                {
                    min = a;
                }
            }

            return new Tuple<T, T>(min, max);
        }

This is the solution I would go with as well. It's the most complete and simple, with O(n) runtime and O(n) comparisons. Just a minor fix to it: reverse the >0 and <0 in your CompareTo() function calls.

Some Code:

public void findMinAndMax(int[] arr) {
	
	
	for (int i = 0; (i + 1) < arr.length; i+=2) {

		if (arr[i] > arr[i + 1]) {

			switchElements(arr, i, i + 1);
		}
	}

	int minIndex, maxIndex, minimum, maximum;

	minIndex = 0;
	maxIndex = 1;



	for (int i = 0; i < arr.length; i += 2) {

		if (minIndex < arr.length && arr[minIndex] < minimum ) {

			minimum = arr[minIndex];
		}

		if (maxIndex < arr.length && arr[maxIndex] > maximum ) {

			maximum = arr[maxIndex];
		}

		minIndex++;
		maxIndex++:
	}

}

public void switchElements(int[] arr, int e1, int e2) {
	
	int temp = arr[e2];
	arr[e2] = arr[e1];
	arr[e1] = temp; 
}

Well done!

For the code: I think we can just check for min and max along the way when comparing 2 consecutive elements. No need to switch them into odd/even positions. Also need to handle the case when the size is odd/even.

Some code:

if (n%2) A[n] = A[n-1];

mi = INF;
ma = -INF;

for(int i = 0; i<n; i++){
	if (A[i]<A[i+1]){
		mi = min (mi, A[i]);
		ma = max (ma, A[i+1]);
	}else{
		mi = min (mi, A[i+1]);
		ma = max (ma, A[i]);
	};
}

This take about 3n/2 comparisons because for each 2 elements, it takes 3 comparisons.

Sorry, the increment of for-loop must be 2 each time:

if (n%2) A[n] = A[n-1];
mi = INF;
ma = -INF;

for(int i = 0; i<n; i+=2){
	if (A[i]<A[i+1]){
		mi = min (mi, A[i]);
		ma = max (ma, A[i+1]);
	}else{
		mi = min (mi, A[i+1]);
		ma = max (ma, A[i]);
	};
}

(Just realized that the edit function of career cup is off now)

This is just crazy adding unnecessary operations going twice through the array the order of growth still is O(n) but it is way less efficient offering O(3n/2) which is > O(n)

This is a very simple going through the array and track the min and max as there is no statistics about the array you can't have other strategy than read the entire array once to determine the min and max.

If this would be finding the nth element it would be a bit more complicated problem but it is less code.

@Perez: The author, Skor, gives an algorithm with asymptotic time complexity of O(n), where the constant factor is c = 3/2.

Can you give an O(n) algorithm with smaller constant factor c?

Comparisons really does not matter what matters are operations.

Even though there there are 3n/2 comparisons there are 13n/2 operations.

All these operations divided by two(2) as the for loop jumps by 2:
4 for getting the value using the index
2 for (i + 1)
3 comparisons
2 assignments
3 operations in the for loop

This are 7n operations.


While in a linear approach there would have comparisons order of 1n, 3n/2, 2n for best, average, worst respectively.

Taking the worst case:

There are:
2 indexing operations
2 comparisons
1 assignment
3 operations in the for loop

Which is 8n operations which on operation more than 7n of the operations of the 3n/2 comparisons solution.
The 3n/2 algorithm does 87.5% comparison compared to the linear approach.

How about the average case number operations assuming 1/3 of the numbers will be in between min and max:
6 indexing operations
1/3 assignment
3 operations in the for loop

The average case takes 69% operations of what the 3n/2 comparison solution would take.

7n => 7
23n/6 => 4.833..


I personally would take that trade off of the linear approach based on average case performance.

In real world scenario I've tested both and the linear approach was never beaten against the 3n/2 comparison one.

The closest in in milliseconds I saw was:
Populate Array: 448.0256
-199999999, 199999940 Linear Took: 95.0055
-199999999, 199999940 3n/2 Took: 97.0055

In average I saw:
Populate Array: 445.0254
-199999995, 199999995 Linear Took: 84.0048
-199999995, 199999995 3n/2 Took: 104.0059

Feel free to verify this by yourself using C# you can download LINQPad.

void Main()
{
	DateTime start;
	DateTime end;
	int[] array = new int[10000000];
	
	Random rand = new Random();
	start = DateTime.Now;
	for(int i = array.Length-1; i >= 0; i--)
	{
		array[array.Length - i -1] = rand.Next(-20*array.Length, array.Length*20);
	}
	end = DateTime.Now;
	
	Console.WriteLine("Populate Array: " + (end - start).TotalMilliseconds);
	
	Tuple<int, int> result;
	try
	{
		start = DateTime.Now;
		 result = FindMinimunMax(array);
		 end = DateTime.Now;
		Console.WriteLine(result.Item1 + ", " + result.Item2 + "\t Linear \t Took: " + (end - start).TotalMilliseconds);
		
		
		
	     start = DateTime.Now;
		 result = FindMinimunMax3n2(array);
		end = DateTime.Now;
		Console.WriteLine(result.Item1 + ", " + result.Item2 + "\t 3n/2 \t\t Took: " + (end - start).TotalMilliseconds);
		
	}
	catch(Exception e)
	{
		Console.WriteLine(e.ToString());
	}
}

public static Tuple<int, int> FindMinimunMax(int[] A) 
{
  if(A == null || A.Length == 0)
      throw new ArgumentNullException();

  int max = A[0];
  int min = A[0];

  for(int i = 0;  i < A.Length; i++)
  {
      if (max < A[i] )
      {
          max = A[i];
      }
      else if(min > A[i])
      {
          min = A[i];
      }
  }

  return new Tuple<int, int>(min, max);
}
			
public static Tuple<int,int> FindMinimunMax3n2(int[] A)
{
	int mi = int.MaxValue;
	int ma = int.MinValue;

	for(int i = 0; i<A.Length; i+=2){
		if (A[i]<A[i+1]){
			mi = Math.Min(mi, A[i]);
			ma = Math.Max(ma, A[i+1]);
		}else{
			mi = Math.Min(mi, A[i+1]);
			ma = Math.Max(ma, A[i]);
		}
	}
	
	return new Tuple<int, int>(mi, ma);
}

Just made the process High Priority I finally saw it beating twice.

These are the best cases for 3n/2 been 96% the linear:
Populate Array: 443.0253
-199999924, 199999855 Linear Took: 108.0062
-199999924, 199999855 3n/2 Took: 104.006

Populate Array: 449.0257
-199999970, 199999980 Linear Took: 100.0057
-199999970, 199999980 3n/2 Took: 97.0056

This is the Average linear is 90% of 3n/2 faster:
Populate Array: 422.0241
-199999921, 199999945 Linear Took: 92.0053
-199999921, 199999945 3n/2 Took: 102.0058

This are two example of the best cases linear is %69 the 3n/2:
Populate Array: 482.0276
-199999966, 199999981 Linear Took: 81.0046
-199999966, 199999981 3n/2 Took: 117.0067

Populate Array: 397.0227
-199999958, 199999975 Linear Took: 78.0044
-199999958, 199999975 3n/2 Took: 113.0065

@Perez: You assume all operations are equally fast.
How about comparing strings?

Statistic on my machine over 100 runs:

Generated 1000000 strings of length 2: 87 [ms]
3n/2 comparisons: 40.44 [ms]
2n   comparisons: 47.92 [ms]

Code for benchmarking in C++:

#include <iostream>
#include <sys/time.h>
#include <stdlib.h>     /* srand, rand */

using namespace std;

long int milisecond(struct timeval tp){
    long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
    return ms;
};

const int   N   = 1000000;
const int   LEN = 2;

string      A[N+10];
string      MIN, MAX;

void generateRandom(){
    srand (time(NULL));
    for(int i=0;i<N; i++){
        for(int j=0;j<LEN;j++)
            A[i] = (rand()%26) + 'A';
    };
};


void FindMinimunMax(){
    string max = A[0];
    string min = A[0];

    for(int i = 0;  i < N; i++){
      if (max < A[i] ){
          max = A[i];
      }else if(min > A[i]){
          min = A[i];
      }
    }
    MIN = min, MAX = max;
}


void findMinMax3n2(){
    if (N%2) A[N] = A[N-1];

    string mi = A[0];
    string ma = A[0];
    int i = 0;
    for(; i<N; i+=2){
        if (A[i]<A[i+1]){
            mi = mi>A[i]?A[i]:mi;
            ma = ma<A[i+1]?A[i+1]:ma;
        }else{
            mi = mi>A[i+1]?A[i+1]:mi;
            ma = ma<A[i]?A[i]:ma;
        };
    }
    MIN = mi, MAX = ma;
}


int main()
{
    struct timeval start, end;
    gettimeofday(&start,NULL);
    generateRandom();
    gettimeofday(&end,NULL);
    cout<<"Generated "<<N<<" strings of length "<<LEN<<": "<<milisecond(end)-milisecond(start)<<" [ms]"<<endl;

    int nRuns = 100;

    gettimeofday(&start,NULL);
    for(int i=0;i<nRuns;i++)
        findMinMax3n2();
    gettimeofday(&end,NULL);
    cout<<"3n/2 comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;

    gettimeofday(&start,NULL);
    for(int i=0;i<nRuns;i++)
        FindMinimunMax();
    gettimeofday(&end,NULL);
    cout<<"2n   comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;

    return 0;
}

Sorry, there's typo in the above code.
Wrong one:

A[i] = (rand()%26) + 'A';

Correct one:

A[i] += (rand()%26) + 'A';

Statistics:

Generated 1000000 strings of length 2: 116 [ms]
3n/2 comparisons: 40.14 [ms]
2n   comparisons: 47.61 [ms]

(I would like to request careercup to bring back the edit button)

Seems like the 3n/2-comparison algorithm beats 2n-comparison algorithm for data type of double and string. This is reasonable since comparing double/string is costlier than comparing int.

Statistic:

Generated 1000000 numbers/(strings of length 2): 116 [ms]
3n/2 comparisons: 37.73 [ms]
2n   comparisons: 47.64 [ms]

Code (again):

#include <iostream>
#include <sys/time.h>
#include <stdlib.h>     /* srand, rand */


using namespace std;

long int milisecond(struct timeval tp){
    long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000;
    return ms;
};

typedef string myType;
//typedef double  myType;
//typedef int     myType;

const int   N   = 1000000;
const int   LEN = 2;

myType      A[N+10];
myType      MIN, MAX;

void generateRandom(){
    srand (time(NULL));
    for(int i=0;i<N; i++){
        //string:
        for(int j=0;j<LEN;j++)
            A[i] += (rand()%26) + 'A';
        //double:
        //A[i] = rand()%N /N;
        //int:
        //A[i] = rand()%N;
    };
};


void FindMinimunMax(){
    myType max = A[0];
    myType min = A[0];

    for(int i = 0;  i < N; i++){
      if (max < A[i] ){
          max = A[i];
      }else if(min > A[i]){
          min = A[i];
      }
    }
    MIN = min, MAX = max;
}


void findMinMax3n2(){
    if (N%2) A[N] = A[N-1];

    myType mi = A[0];
    myType ma = A[0];
    int i = 0;
    for(; i<N; i+=2){
        if (A[i]<A[i+1]){
            if (mi>A[i])    mi = A[i];
            if (ma<A[i+1])  ma = A[i+1];
        }else{
            if (mi>A[i+1])  mi = A[i+1];
            if (ma<A[i])    ma = A[i];
        };
    }
    MIN = mi, MAX = ma;
}


int main()
{
    struct timeval start, end;
    gettimeofday(&start,NULL);
    generateRandom();
    gettimeofday(&end,NULL);
    cout<<"Generated "<<N<<" numbers/(strings of length "<<LEN<<"): "<<milisecond(end)-milisecond(start)<<" [ms]"<<endl;

    int nRuns = 100;

    gettimeofday(&start,NULL);
    for(int i=0;i<nRuns;i++)
        findMinMax3n2();
    gettimeofday(&end,NULL);
    cout<<"3n/2 comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;

    gettimeofday(&start,NULL);
    for(int i=0;i<nRuns;i++)
        FindMinimunMax();
    gettimeofday(&end,NULL);
    cout<<"2n   comparisons: "<<(0.0+milisecond(end)-milisecond(start)) / nRuns<<" [ms]"<<endl;

    return 0;
}

My bad, the above double generation fails. Must +0.0 before dividing.
After correcting that, I see only string comparison is costly.

In this case the string comparisons requires more operations thus in this 3n/2 would be a better choice for string comparisons or anything more complex than integers.

This is because the comparison become the bottom-neck so less comparisons mean less operations.

But for original problem which compares integers my argument still stands as a comparison is a single operation.

@Perez: Your solution using if (){} else if(){} is also very fast!

Sorting is O(nlogn) which growths larger than plain O(n)

There's a lot to like about this answer. Max & min use the first value in the array, the function returns both values.

You can skip arr[0] and start at arr[1].

This is an old question. Don't think it's used anymore.

However, it actually has a lot of subtleties. The beauty of it is that it seems trivial and there is a wide skill range of correct answers. Every programmer should be able to solve it in the simplest case; however, advanced programmers can go deeper.

I've only seen a couple of people get the advanced 3N/2 solution correctly. And nobody has offered a C++ template or C# generics version yet. (The original question is posed as "array of numbers".)