CareerCup

#include "stdafx.h"
#include <stdio.h>

int main() {
int A[] = {1,2,3,4,5};
int max1 = 0, max2 = 0;
for(int i = 0; i < 5;i++) {
if(A[i] > max1) {
max2 = max1;
max1 = A[i];
}
else if(A[i] > max2 && A[i] < max1) {
max2 = A[i];
}
}
printf("%d\n",max2);
}

This is a kth order statistics problem can be solved in O(n).
Rand-Select() algorithm works too.
There is a rather special case (since its just second largest) - brute force as below.

namespace QuickPorjects
{
	class Program
	{
    	static void Main(string[] args)
    	{
        	int[] arr = new int[] { 7,1,2,3,4,5,8 };

        	FindTwoLargest(arr);
    	}

    	private static void FindTwoLargest(int[] arr)
    	{
        	int max = int.MinValue;
        	int max_second = int.MinValue;
        	int i;
       	 
        	//max =  arr[0];

        	for (i = 0; i < arr.Length; i++)
        	{
            	if (arr[i] > max)
            	{
                	max_second = max;
                	max = arr[i];
            	}
            	else if (arr[i] > max_second)
            	{
                	max_second = arr[i];
            	}
        	}

        	Console.WriteLine(max + " 	" + max_second);
    	}
	}
}

Selection algorithm ..works in O(n) in avg case.

Revised algorithm:

- Iterate the array from left to right and from right to left to find the largest element in each direction.
- When checking for the largest element in this direction, ignore the largest element from the other direction.
- Find the smallest elment in these two largest elements.

int findSecondLargest(int A[], int N)
{	
	int left = 0;
	int right = N - 1;	

	for (int i = left, j = right; i < N && j >= 0; i++, j--)
	{
		if (A[left] < A[i] && i != right)
			left = i;		
		if (A[right] < A[j] && j != left)			
			right = j;				
	}
	if (A[left] < A[right])
		return A[left];
	else
		return A[right];
}

This can be solved in n +logn -2 comparision using tournament method

Build max-heap, remove the root and max heapify again. I guess this should take order n times.

To get the second largest
we can use bubble sort (2 times outer loop... N-2 is second largest element)
Or selection sort method as below.

#include <iostream>

using namespace std;

int main()
{
int a[] = {0,0,0,1,2,0};
int pos,temp;
int n = 6;

for (int i =0; i<2; i++)
{
pos = i;

for(int j= i+1; j<n; j++)
{
if(a[j] > a[pos])
{
pos = j;
}
}

if(pos != i)
{
temp = a[pos];
a[pos] = a[i];
a[i] = temp;
}
}

cout << "Second Largest: "<< a[1] << endl;
}

int 2ndLargest(int []a,int n)
{
int i,SL,L;
for(SL=L=a[0],i=1;i<n;i++)
if(a[i]>L)
{
SL=L;
L=a[i];
}
else
if(a[i]>SL)
SL=a[i];
return SL;

}
Complexity is = O(n-1)

- Divide the array into 2 subarrays. 
- Find the largest elements on each subarray.
- Find the smallest element from these two largest elements. That's the second largest element of the original array.

Running time: O(n)

int findSecondLargest(int A[], int N)
{	
	int left = 0;
	int right = N - 1;
	int mid = (N - 1) / 2;	

	for (int i = 0, j = right; i <= mid || j > mid; i++, j--)
	{
		if (i <= mid)
		{
			if (A[left] < A[i])			
				left = i;						
		}
		if (j > mid)
		{
			if (A[right] < A[j])			
				right = j;					
		}		
	}
	if (A[left] < A[right])
		return A[left];
	else
		return A[right];
}